I just feel like doing it, despite knowing that official one should come in less than a day after this blog post...
We might miss some proofs here and there (I only wrote this in half an hour, for quickie's sake), so we'd love to see your proofs contributing in the comments.
Special thanks to iristran911 for coding with me during the VC.
Tutorial
- Editorialist: iristran911
- Implementation: 287850159
Tutorial
- Editorialist: iristran911
- Implementation: 287850715
Tutorial
Tutorial
2033E - Sakurako, Kosuke, and the Permutation
- Editorialist: iristran911
- Implementation: 287851002
Tutorial
Tutorial
- Editorialist: AkiLotus + iristran911
- Implementation: 287854002
Tutorial
Could you give some hint for a dp solution of problem C
keep ur states as dp[i][0] -> answer if you swapped the ith index, dp[i][1] -> answer if u didnt swap the ith index
https://codeforces.me/contest/2033/submission/287721060
287823712 you can look at the solution and take an idea.
I used an online solution for G, with a bit of preprocessing.
First, note that one of the furthest nodes from a node can be found in the end of the tree's diameter. Instead of finding the diameter of the whole tree only, we need to find it for each subtree, rooted at the $$$k_i$$$th ancestor of $$$v_i$$$.
We can find one of the diameters of a subtree rooted at $$$x$$$ as the one that has longest distance between the end nodes from the following candidates:
Finding any diameter of every subtree takes $$$\mathcal{O}(n)$$$ time (although I just sorted the candidates to make it $$$\mathcal{O}(n\log{n})$$$ because I'm lazy). Now for each query, we just need to find the distance between $$$v_i$$$ and each of the two end nodes of a diameter of $$$ancestor(v_i, k_i)$$$, which takes $$$\mathcal{O}(\log{n})$$$ per query, after building the table in $$$\mathcal{O}(n\log{n})$$$ time.
Submission: 287804307
Woah, nice one. I keep wondering if an online solution is available, and here is that.
I mean another possible online solution is just spam persistent segment tree
Why would you do that for a div3... :,)
Well you were wondering about an online solution, i just pointed out yours is trivially extendable to be online
For online it can be solved using HLD, but with Time complexity $$$O(nlog^2n)$$$ :(
How??? Can you explain? I just finished reading about HLD but can't figure out how to apply it here
Hi, Can you explain a bit more please?? I was trying so hard by euler tour for subtree of Kth ancestor. Then I was stuck at how to find the subtree diameter for each node. Are there any resources for this?
There are two cases for node $$$x$$$'s diameter construction:
We can recursively propagate all necessary information to each node's parent. My solution implemented exactly this, so if you have any question about my implementation, please specify which part you have question on.
Could someone tell what is wrong with my solution for E? 287823722
Try this test:
Correct answer should be $$$1$$$, yet your code output $$$0$$$.
If you probe for cycle $$$2 \to 6 \to 2$$$, you actively skip the $$$[4, 5, 3]$$$ subarray by using variable
i
directly as a cycle check. I suggest adding a temporal variable for the cycle probing.Roland15
Oh... In my head I thought that from the cyclic behaviour i would go back to the original position...but I left out that part. Thanks I've been looking at the code for like an hour or so and couldn't notice.
Proof for claim 1 in Editorial of F
Consider the fibonacci sequence mod $$$k$$$. The sequence starts with $$$(0, 1)$$$. Assume at any point, there exists $$$(0, x)$$$ in the sequence.
Claim : $$$gcd(x, k) = 1$$$
Proof : Consider the sequence mod $$$gcd(x, k)$$$ instead. Then, we have $$$(0, 0)$$$ at the position where we had $$$(0, x)$$$. Backtracking, the entire sequence must be $$$0$$$. This implies that $$$gcd(x, k)$$$ divides $$$1$$$.
Now, consider the sequence contiuing from the point $$$(0, x)$$$. It continues like $$$(0, x, x, 2 \cdot x, 3 \cdot x, ....)$$$, i.e. it is $$$f_i \cdot x$$$.
Consider the next point where $$$f_i \cdot x \mod k = 0$$$.
$$$k | f_i \cdot x$$$ but $$$gcd(x, k) = 1$$$. Thus, $$$k | f_i$$$
Hence, we come to the conclusion.
How did you find the first index at which the fibonacci number is divisible by k?
As $$$K$$$ is relatively small (compared to the $$$Nth$$$ Fibonacci number which grows at a much much faster rate) it's easier to just find (calculate from scratch) the first Fibonacci number divisible by $$$K$$$.
In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats.
Sorry but how does $$$k|f_i$$$ at a point establish periodicity? Don't we have to show that $$$(0, 1)$$$ must repeat somewhere? Can you explain further please?
I dont care about periodicity of the entire sequence (even though it obviously must be so)
I only want to prove that the $$$0$$$ occurrences are periodic.
I considered the first occurrence of a $$$0$$$. Let it be at index $$$y$$$, i.e. $$$y$$$ must be first index such that $$$f_i \mod k = 0$$$. Let $$$x = f_{i + 1}$$$
Then, I claimed that $$$f_{y + j} = x \cdot f_j$$$ and $$$gcd(x, k) = 1$$$.
Now, if $$$f_{y + j} \mod k = 0$$$, it implies $$$k | x \cdot f_j$$$, implying $$$k | f_j$$$. And we know that the first index where $$$f_i \mod k = 0$$$ holds is $$$y$$$. Thus, the next occurrence of $$$0$$$ must be at $$$2 \cdot y$$$.
Right, that makes sense. this website also mentions that the zeros of fibonacci mod k is evenly spaced, as you just proved. And it seems that the period of a fibonacci sequence mod m is a multiple of the period of it's zero.
Hi, I hacked your D. Check for overflow next time, ha-ha.
Tsk, shame on me there. Thank you.
Indirectly mine too. I should have been a little more careful;-;
Just took a look, that one you WA'd on was definitely not my hack (closest one to mine should be test #14). Still, it's generic enough that I'd wonder why there wasn't one on the original testset.
Unless you are specifically trying to hack this solution, you will obviously not have the counter test. Constructing it once you know what to hack is easy, but knowing that people might make such a mistake is not.
I think I omitted a lot when I made my point here.
What I tried to say was that the first test (#9) causing WA for this kind of solutions looked like a very generic one (having all $$$n$$$ elements at $$$-100000$$$, seemingly?), thus I raised my concern. Shouldn't any regular testset have tests with full minima/maxima values by default somewhere?
Yeah, i am willing to bet it is not. It is just using $$$10^{5}$$$ to get to the overflow point fast. Since you did write a hack test, isnt yours similiar?
Also generally, there is not much point in having all $$$a_i$$$ be MAX value instead of RNG value (and neither is there value here), so claiming a rule of some sort is wrong.
Mine aimed a bit specifically (I chose all $$$2^{16}$$$ to ensure a $$$0$$$ would pop up somewhere). If that one was the first one popping up in a WA, I wouldn't question much.
Perhaps indeed at the end of test #9 there was something else instead of $$$-10^5$$$. If so, then it's on me assuming things in a whim; i.e., my bad.
Oh, I see. However, It could be observable that test cases are not rigid enough to mitigate the AC for solutions with generic overflow issues. (since it was my first encounter idk whether it happens regularly or not)
Thanks to the weak pretests in problem D. The chat gpt warriors got a heartbreak, lmao.
May
Map
warriors xD