Idea: FBI
Tutorial
Tutorial is loading...
Solution
def solve():
n = int(input())
x = 0
c = 1
while -n <= x <= n:
if c % 2 == 1:
x -= 2 * c - 1
else:
x += 2 * c - 1
c += 1
if c % 2 == 0:
print("Sakurako")
else:
print("Kosuke")
for tc in range(int(input())):
solve()
Idea: FBI
Tutorial
Tutorial is loading...
Solution
def solve():
n = int(input())
mn = dict()
for i in range(n):
a = [int(x) for x in input().split()]
for j in range(n):
mn[i - j] = min(a[j], mn.get(i - j, 0))
ans = 0
for value in mn.values():
ans -= value
print(ans)
t = int(input())
for _ in range(t):
solve()
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=n/2-1;i>=1;i--){
if(a[i]==a[i+1] || a[n-i+1]==a[n-i]){
swap(a[i],a[n-i+1]);
}
}
int re=0;
for(int i=1;i<n;i++){
re+=(a[i]==a[i+1]);
}
cout<<re<<endl;
}
}
Idea: FBI
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n+1];
map<int,int>mp;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int p_su[n+1];
p_su[0]=0;
int lst[n+1];
mp[0]=0;
for(int i=1;i<=n;i++){
p_su[i]=p_su[i-1]+a[i];
if(mp.find(p_su[i])==mp.end()){
lst[i]=-1;
}
else{
lst[i]=mp[p_su[i]];
}
mp[p_su[i]]=i;
}
int dp[n+1];
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++){
dp[i]=max(dp[i],dp[i-1]);
if(lst[i]!=-1){
dp[i]=max(dp[i],dp[lst[i]]+1);
}
}
cout<<*max_element(dp,dp+n+1)<<endl;
}
}
2033E - Sakurako, Kosuke, and the Permutation
Idea: FBI
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
cin>>t;
while(t--){
int n;
cin>>n;
int p[n+1];
for(int i=1;i<=n;i++){
cin>>p[i];
}
bool us[n+1];
memset(us,0,sizeof us);
int re=0;
for(int i=1;i<=n;i++){
if(!us[i]){
int cu=i;
int le=0;
while(us[cu]==0){
le++;
us[cu]=1;
cu=p[cu];
}
re+=(le-1)/2;
}
}
cout<<re<<'\n';
}
}
Idea: FBI
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define ssize(x) (int)(x.size())
#define ALL(x) (x).begin(), (x).end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rd(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const LL MOD = 1e9 + 7;
int bp(int a, int n) {
if (n == 0)
return 1;
if (n % 2 == 0)
return bp(1LL * a * a % MOD, n / 2);
else
return 1LL * bp(a, n - 1) * a % MOD;
}
int inv(int a) {
return bp(a, MOD - 2);
}
void solve() {
LL n, k;
cin >> n >> k;
n %= MOD;
if (k == 1) {
cout << n << "\n";
return;
}
vector<int> fib(3);
fib[0] = fib[1] = 1;
int cnt = 0;
for (int i = 2; i <= 10 * k; i++) {
fib[i % 3] = (fib[(i + 2) % 3] + fib[(i + 1) % 3]) % k;
if (fib[i % 3] == 0)
cnt++;
if (fib[i % 3] == 1 && fib[(i + 2) % 3] == 0) {
cout << 1LL * i * n % MOD * inv(cnt) % MOD << "\n";
return;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
//#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(time(nullptr));
const int inf = 1e9;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
void precalc(int v, int p, vector<vector<int>> &sl, vector<pair<int, int>> &maxd, vector<int> &h){
maxd[v] = {0, 0};
if (v != p) h[v] = h[p] + 1;
for(int u: sl[v]){
if (u == p) continue;
precalc(u, v, sl, maxd, h);
if (maxd[v].y < maxd[u].x + 1) {
maxd[v].y = maxd[u].x + 1;
}
if (maxd[v].y > maxd[v].x) {
swap(maxd[v].x, maxd[v].y);
}
}
}
void calc_binups(int v, int p, vector<vector<int>> &sl, vector<vector<pair<int, int>>> &binup, vector<pair<int, int>> &maxd, vector<int> &h){
binup[v][0] = {maxd[p].x, p};
if (maxd[p].x == maxd[v].x + 1) {
binup[v][0].x = maxd[p].y;
}
binup[v][0].x -= h[p];
for(int i = 1; i < 20; ++i){
binup[v][i].y = binup[binup[v][i - 1].y][i - 1].y;
binup[v][i].x = max(binup[v][i - 1].x, binup[binup[v][i - 1].y][i - 1].x);
}
for(int u: sl[v]){
if (u == p) continue;
calc_binups(u, v, sl, binup, maxd, h);
}
}
int get_ans(int v, int k, vector<vector<pair<int, int>>> &binup, vector<pair<int, int>> &maxd, vector<int> &h){
k = min(k, h[v]);
int res = maxd[v].x - h[v];
int ini = h[v];
for(int i = 19; i >= 0; --i){
if ((1 << i) <= k) {
res = max(res, binup[v][i].x);
v = binup[v][i].y;
k -= (1 << i);
}
}
return res + ini;
}
void solve(int tc){
int n;
cin >> n;
vector<vector<int>> sl(n);
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
sl[--u].emplace_back(--v);
sl[v].emplace_back(u);
}
vector<pair<int, int>> maxd(n);
vector<int> h(n);
precalc(0, 0, sl, maxd, h);
vector<vector<pair<int, int>>> binup(n, vector<pair<int, int>>(20));
calc_binups(0, 0, sl, binup, maxd, h);
int q;
cin >> q;
for(int _ = 0; _ < q; ++_){
int v, k;
cin >> v >> k;
cout << get_ans(v - 1, k, binup, maxd, h) << " ";
}
}
bool multi = true;
signed main() {
int t = 1;
if (multi)cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
awesome contest!
my rating change is showing up as 0 wtf? is this possible?
Yeah, this is possible. This just means that:
1) your performance wasnt' good enough for your rating to increase!
2) your performance wasnt' bad enough for your rating to decrease!
I noticed that except D, all problems that involve "Kosuke" refer to "Kosuke" as "Kosuke" but D refers to "Kosuke" as "Ko'U'suke".
This means nothing of course, just a funny observation.
Is it me, or this is a reference to Naruto. ?
hey there does this mean that if you don't solve any questions your rating would decrease
upper bound for the first appearance of $$$0$$$ on problem F is actually bounded by 2 * k.
https://jonkagstrom.com/articles/upper_bound_of_fibonacci_entry_points.pdf
I feel like proving that we don't miss any numbers divisible by k would be a nice touch. Proof: Let Fi be the first number divisible by k. Fm exists such that m>i, and m!=ni, n in the set of integers. Let us prove that it is not divisible by k. gcd(Fi,Fm) = F(gcd(i,m)). The gcd must be <= i since, i is less than m. Also, the gcd is not equal to i since m is not divisible by i. Thus, F(gcd(i,m)) is an element of the set of Fz, 0<=z<i. By premise, these numbers are not divisible by k, thus since the gcd of Fm and Fi is less than k, and Fi is divisible by k, Fm is not divisible by k. QED.
p.s: idk latex but someone can make this into latex and i will edit if anyone feels like it
Implementation for problem F...
There are some things that I have discussed and discovered after the contest for understanding F. The following points are in context of a fibonacci sequence mod $$$k$$$, where $$$k \geq 2$$$. Pisano period refers to the period of such a sequence.
The period is bounded by $$$6k$$$.
The zeros of fibonacci mod $$$k$$$ are evenly spaced as proved here thanks to Dominater069 and observed to first occur no later than $$$2k$$$ as mentioned here.
The Pisano period is either 1, 2 or 4 times the period of its zero. It is mentioned in wikipedia that "The number of occurrences of 0 per cycle is 1, 2, or 4." and since we have established that the all the zeros are evenly spaced, it implies that the Pisano period is either 1, 2 or 4 times the period of the zeros.
4th question can also be done by using map.
storing the prefix sum in map and making a counter variable . if current element sum matches map then increment the counter and delete the map. do this iteration for whole array.
at the end cout counter.
Yeah, I have done the same way.. it works incredible.
https://codeforces.me/contest/2033/submission/288275477
Thanks for editorial !
that was great
F is the best mathematical Question
In E, you can always reduce your cycle length by 2, if you swap two non adjacent elements in cycle.
Alternative binary lifting solution of problem G :
Note that for a query
v
,k
it is ideal to go up till thekth
parent ofv
as we can always come down later for free. Let this node, thekth
parent ofv
, beu
. Now we need to maximize dist(v
,i
) across all nodesi
in the subtree ofu
. We can use the fact that (one of) the maximal distance node(s) from any node in a tree is one of the endpoints of any diameter. So we just need to store the endpoints of (any) diameter for each subtree. This can be easily precomputed by considering both the cases for each node : 2 deepest leaves from 2 different children OR maximum diameter of a child node over all children. For implementation you can refer to 287739162What if the distance from
v
to an endpoint of another diameter of the subtree is maximal, not the particular diameter you choose for the subtree underkth
parent ofv
?2 deepest leaves from 2 different children OR maximum diameter of a child node over all children.
Here, how does the OR case exactly work?
Don't use x(first) or y(second) in tutorial which is your macro in Tutorial of G Vladosiya
can u attach this blog in contest materials, would be easier to find for users
can somebody give me an example why my greedy on problem C didn't work ( it worked well till line 189th appeared difference ),please. ~~~~~ a[n+1] = 0; for ( tn i = 1; i <= n / 2; i++ ){ if ( a[i] != a[n-i+1] ){ // ( tn means int ) swap(a[i],a[n-i+1]); if ( ( a[i] == a[i-1] ) || ( a[i] == a[i+1] ) || ( a[n-i] == a[n-i+1] ) || ( a[n-i+2] == a[n-i+1] ) ) swap( a[i] , a[n-i+1] ); } } tn ans = 0; for ( tn i = 1; i <= n; i++ ) ans += a[i] == a[i+1]; ~~~~~
why tle is there in my solution of E [](https://codeforces.me/contest/2033/submission/288074472)
Use unordered_map instead of map since you dont need to access the data in order and is (in average) faster than the regular one
Use an array instead of a map...
I'm having trouble with solving permutation exercises, especially those that involve math and greedy techniques. How can I improve my thinking in this area, and how can I approach exercises from easy to more challenging, such as problem E in this contest?
Me too.
For D, first I thought of something like finding subarray with sum 0. Generally, this questions include overlapping subarrays, but here it is mentioned that there should be no overlapping subarrays
So I do the exactly same as the solution of above question, one extra step will be I just clear the set whenever if find some prefix Sum in the map. that means there is an segment where sum becomes 0.
See Code
I don't know why my problem D is hacked. Is there an edge case?
did you use unordered_map or unordered_set instead of map or set? the hacker probably use stupid value in array to create serious hash collision to your default hash function in map/set, turning your solution to be O(n^2)
checked your answer, just simply change unordered_map to map and it will work
https://codeforces.me/contest/2033/submission/288658277
What's with the Sakurako and Kosuke names in the recent contests? Is it from an anime I don't know or just random Japanese names?
In E, why (le — 1) / 2 ?
Problem C if you iterate the array from 0 to n/2-1 this algorithm would fail, but if you iterate from n/2-1 to 0 it will work, I wonder why
When is it permissible to include mathematical conclusions in CF competitions? If the F round of a particular competition allows it, then you can certainly include a problem that tests advanced mathematical conclusions in Div1F.
Problem F. Why we can't replace the block
on the block
? I think they are equivalent.
Re. the solution for problem D(Kousuke's Assignment).
Why're we calling max_element() over the dp array in the end? I think simply printing dp[n] should be enough since we do: dp[i] = max(dp[i-1], dp[i])
https://codeforces.me/contest/2033/submission/290988370
Can someone help me to find my mistakes, it get WA on t2, https://codeforces.me/contest/2033/submission/291138972