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

Автор AkiLotus, история, 5 недель назад, По-английски

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
  • Проголосовать: нравится
  • +68
  • Проголосовать: не нравится

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

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

»
5 недель назад, # |
Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      5 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

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

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

  • »
    »
    5 недель назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Try this test:

    1
    6
    1 6 4 5 3 2
    

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

    Spoiler
    • »
      »
      »
      4 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

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

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.

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    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?

    • »
      »
      »
      5 недель назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 недель назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
5 недель назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Tsk, shame on me there. Thank you.

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

      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.

      • »
        »
        »
        »
        5 недель назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          5 недель назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          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?

          • »
            »
            »
            »
            »
            »
            5 недель назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              5 недель назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

      • »
        »
        »
        »
        5 недель назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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)

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

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