FBI's blog

Codeforces Round 981(Div. 3) Editorial
By FBI, history, 2 months ago, In English

2033A - Sakurako and Kosuke

Idea: FBI

Tutorial
Solution

2033B - Sakurako and Water

Idea: FBI

Tutorial
Solution

2033C - Sakurako's Field Trip

Idea: Vladosiya

Tutorial
Solution

2033D - Kousuke's Assignment

Idea: FBI

Tutorial
Solution

2033E - Sakurako, Kosuke, and the Permutation

Idea: FBI

Tutorial
Solution

2033F - Kosuke's Sloth

Idea: FBI

Tutorial
Solution

2033G - Sakurako and Chefir

Idea: Vladosiya

Tutorial
Solution
  • Vote: I like it
  • +52
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it -37 Vote: I do not like it

awesome contest!

→ Reply
»
2 months ago, # |
  Vote: I like it -17 Vote: I do not like it

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

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it +30 Vote: I do not like it

    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!

    → Reply
»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it me, or this is a reference to Naruto. ?

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey there does this mean that if you don't solve any questions your rating would decrease

    → Reply
»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Implementation for problem F...

→ Reply
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for editorial !

→ Reply
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

that was great

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

F is the best mathematical Question

→ Reply
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

In E, you can always reduce your cycle length by 2, if you swap two non adjacent elements in cycle.

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

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

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    So we just need to store the endpoints of (any) diameter for each subtree

    What 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 under kth parent of v?

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
2 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Don't use x(first) or y(second) in tutorial which is your macro in Tutorial of G Vladosiya

→ Reply
»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

can u attach this blog in contest materials, would be easier to find for users

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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]; ~~~~~

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why tle is there in my solution of E [](https://mirror.codeforces.com/contest/2033/submission/288074472)

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Use an array instead of a map...

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know why my problem D is hacked. Is there an edge case?

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In E, why (le — 1) / 2 ?

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/2033/submission/290988370

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it 
#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://mirror.codeforces.com/contest/2033/submission/291138972

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it 
Alternative Solution for G using Segment Tree and answering queries offline

SOLUTION

→ Reply