AkiLotus's blog

By AkiLotus, history, 6 weeks ago, In English

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.

2033A - Sakurako and Kosuke

Tutorial

2033B - Sakurako and Water

Tutorial

2033C - Sakurako's Field Trip

Tutorial

2033D - Kousuke's Assignment

Tutorial

2033E - Sakurako, Kosuke, and the Permutation

Tutorial

2033F - Kosuke's Sloth

Tutorial

2033G - Sakurako and Chefir

Tutorial
  • Vote: I like it
  • +68
  • Vote: I do not like it

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

Could you give some hint for a dp solution of problem C

»
6 weeks ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

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:

  • Two deepest nodes, each one from different subtrees rooted at children of $$$x$$$, including $$$x$$$ itself.
  • The longest diameter of all subtrees rooted at children of $$$x$$$.

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

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

    Woah, nice one. I keep wondering if an online solution is available, and here is that.

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

      I mean another possible online solution is just spam persistent segment tree

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

        Why would you do that for a div3... :,)

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +31 Vote: I do not like it

          Well you were wondering about an online solution, i just pointed out yours is trivially extendable to be online

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      For online it can be solved using HLD, but with Time complexity $$$O(nlog^2n)$$$ :(

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

        How??? Can you explain? I just finished reading about HLD but can't figure out how to apply it here

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

    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?

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

      There are two cases for node $$$x$$$'s diameter construction:

      1. When the diameter passes through $$$x$$$: We need two furthest nodes from $$$x$$$, and since $$$x$$$ is the root of the subtree, the distance between $$$x$$$ and any of its descendant is the difference of their depths. Therefore, we only need to find two deepest nodes, where each of them are part of subtrees of different children of $$$x$$$. Say these nodes are $$$node1$$$ and $$$node2$$$ respectively, then the length of this diameter is $$$depth[node1] + depth[node2] - 2 \cdot depth[x]$$$.
      2. When the diameter can be constructed within a child's subtree: In this case, we just need to take all children's diameters and find one with the maximum length of diameter.

      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.

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

Could someone tell what is wrong with my solution for E? 287823722

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Try this test:

    1
    6
    1 6 4 5 3 2
    

    Correct answer should be $$$1$$$, yet your code output $$$0$$$.

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

      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.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

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.

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

    How did you find the first index at which the fibonacci number is divisible by k?

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

      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$$$.

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

    In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats.

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

    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?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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$$$.

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

        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.

»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Hi, I hacked your D. Check for overflow next time, ha-ha.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Tsk, shame on me there. Thank you.

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

    Indirectly mine too. I should have been a little more careful;-;

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

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

        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.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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?

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

            seemingly

            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.

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

              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.

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

        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)

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Thanks to the weak pretests in problem D. The chat gpt warriors got a heartbreak, lmao.