awesome contest!

my rating change is showing up as 0 wtf? is this possible?

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.

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.

1. The period is bounded by $$$6k$$$.

2. 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.

3. 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.

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 the kth parent of v as we can always come down later for free. Let this node, the kth parent of v, be u. Now we need to maximize dist(v, i) across all nodes i in the subtree of u. 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 287739162

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)

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?

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?

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

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;
}

on the block

if (fib[i % 3] == 0)
    cout << 1LL * i * n % MOD << "\n";
    return;
}

? 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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define pb push_back

template<typename T>
T chmax(T a, T b) {
    return a > b ? a : b;
}
 
template<typename T>
T chmin(T a, T b) {
    return a > b ? b : a;
}

const ld pi = 3.14159265358979323846;
const int mod = (int)1e9 + 7;
const ll INF = 1e18;

const int N = (int)1e6 + 1, M = N * 2, depth = 21;

int s[N], f[N][2], p[N][depth];

struct LCA{
    vector<int> h, w, e, ne, dep;
    vector<vector<int>> fa;
    int n, idx;

    const int depth = 21;

    LCA(int _n){
        n = _n;
        idx = 0;

        dep.resize(n, (int)1e9);
        fa.resize(n);

        ne.resize(n * 2, 0);
        h.resize(n * 2, -1);
        e.resize(n * 2, 0);

        for(int i = 0; i < n; i++){
            fa[i] = vector<int>(depth + 1);
        }
    }

    void add(int u, int v) {
        e[idx] = v, ne[idx] = h[u], h[u] = idx++;
        e[idx] = u, ne[idx] = h[v], h[v] = idx++;
    }

    int lca(int u, int v){
        if(dep[u] < dep[v]) swap(u, v);

        for(int i = depth - 1; i >= 0; i--){
            if(dep[fa[u][i]] >= dep[v]){
                u = fa[u][i];
            }
        }
        if(u == v) return u;

        for(int i = depth - 1; i >= 0; i--){
            if (fa[u][i] != fa[v][i]){
                u = fa[u][i];
                v = fa[v][i];
            }
        }
        return fa[u][0];
    }

    void bfs(int rt) {
        dep[rt] = 1;
        dep[0] = 0;

        queue<int> q;
        q.push(rt);

        while(!q.empty()){
            int u = q.front();
            q.pop();

            for(int i = h[u]; i != -1; i = ne[i]){
                int j = e[i];
                if(dep[j] > dep[u] + 1){
                    dep[j] = dep[u] + 1;

                    q.push(j);
                    fa[j][0] = u;
                    
                    for(int k = 0; k < depth - 1; k++){
                        fa[j][k + 1] = fa[fa[j][k]][k];
                    }
                }
            }
        }
    }
};

void dfs1(int u, int fa, LCA &lca){
    s[u] = u;

    for(int i = lca.h[u]; i != -1; i = lca.ne[i]){
        int j = lca.e[i];
        if(j == fa) continue;

        dfs1(j, u, lca);

        if(f[j][0] + 1 >= f[u][0]){
            f[u][1] = f[u][0];
            f[u][0] = f[j][0] + 1;
            s[u] = s[j];
        }
        else if(f[j][0] + 1 > f[u][1]){
            f[u][1] = f[j][0] + 1;
        }
    }
}


void dfs2(int u, int fa, LCA &lca){
    for(int i = lca.h[u]; i != -1; i = lca.ne[i]){
        int j = lca.e[i];
        if(j == fa) continue;

        p[j][0] = chmax(p[j][0], f[u][lca.lca(s[u], j) != u] + 1);

        for(int k = 0; k < lca.depth - 1; k++){
            int t = lca.fa[j][k];
            p[j][k + 1] = chmax(p[j][k], f[t][lca.lca(s[t], j) != t] + lca.dep[j] - lca.dep[t]);
        }

        dfs2(j, u, lca);
    }
}

void solve(){
    //下面的最远距离预处理
    //上面的用倍增求最大值

    //对于每个点，存一个最长子节点链和次长子节点链
    //对于每次查询，答案就是 chmax(子节点最深，倍增范围节点子节点最深 + 跳跃距离)

    int n;
    cin >> n;

    LCA lca(n + 1);
    for(int i = 0; i <= n; i++){
        f[i][0] = f[i][1] = 0;
        s[i] = 0;

        for(int j = 0; j < depth; j++){
            p[i][j] = 0;
        }
    }

    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        lca.add(u, v);
    }

    dfs1(1, 1, lca);
    lca.bfs(1);
    dfs2(1, 1, lca);

    int q;
    cin >> q;

    for(int i = 0; i < q; i++){
        int u, k;
        cin >> u >> k;

        int qwq = f[u][0], v = u;
        for(int j = lca.depth - 1; j >= 0; j--){
            if ((1 << j) <= k) {
                qwq = chmax(qwq, p[u][j]);
                u = lca.fa[u][j];
                if(u == 0){
                    break;
                }
                k -= (1 << j);
            }
        }
        u = chmax(u, 1);
        qwq = chmax(qwq, f[u][lca.lca(s[u], v) != u] + lca.dep[v] - lca.dep[u]);
        cout << qwq << " ";
    } cout << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;

    while(t--){
        solve();
    }
    
    return 0;
}

Can someone help me to find my mistakes, it get WA on t2, https://codeforces.me/contest/2033/submission/291138972