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.net/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
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
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.