FBI's blog

By FBI, history, 13 days 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
  • +55
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it -37 Vote: I do not like it

awesome contest!

»
13 days ago, # |
  Vote: I like it -17 Vote: I do not like it

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

  • »
    »
    13 days 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!

»
13 days 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.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 days 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

»
13 days 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

»
13 days 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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Implementation for problem F...

»
13 days 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.

»
13 days 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.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for editorial !

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

that was great

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

F is the best mathematical Question

»
13 days 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.

»
13 days 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

  • »
    »
    12 days 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?

»
13 days 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

»
13 days 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

»
13 days 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]; ~~~~~

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days 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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Use an array instead of a map...

»
12 days 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?

»
11 days 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

»
11 days 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?

»
11 days 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?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 days 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

»
9 days 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.

»
117 minutes 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.