Блог пользователя FBI

Автор FBI, история, 2 года назад, По-английски

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
Разбор задач Codeforces Round 981 (Div. 3)
  • Проголосовать: нравится
  • +52
  • Проголосовать: не нравится

»
2 года назад, скрыть # |
 
Проголосовать: нравится -37 Проголосовать: не нравится

awesome contest!

»
2 года назад, скрыть # |
 
Проголосовать: нравится -17 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Implementation for problem F...

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for editorial !

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

that was great

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

F is the best mathematical Question

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +14 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится -21 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

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.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Alternative Solution for G using Segment Tree and answering queries offline 

SOLUTION

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

using modular inverse for problem F isn't necessary...

»
19 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

I want to ask in my solution https://codeforces.me/contest/2033/submission/316379063 , I have written cout<<*max_element(dp.begin(),dp.end())<<endl;,this worked but why did cout<<dp[n] did not work. My earlier submissions failed because of this

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

D's solution is "signed integer overflow" on test 9.hhhh

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

kudos to some devious ass guy making my unordered_map explode in D lmao >:p xD