chokudai's blog

AtCoder Beginner Contest 241（Sponsored by Panasonic） Announcement
By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 241（Sponsored by Panasonic）.

We are looking forward to your participation!

  • Vote: I like it
  • +47
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

The link is broken. Correct link

→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

i feel today's D and E were easy.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm getting the wrong answer in 2 test cases in E. can anyone help me, why is it so? Thanks submission

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I reordered some lines of your code. Now it can pass: Submission

    Basically, your original code is checking for == 3 too late. You incremented vis[md], but not check for == 3 immediately. Instead, you waited until a long time after you check for == 3.

    Please see my submission above.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for your help

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In fact, another way to fix the original submission is to change the 2*n for loop to 3*n.

        Then, it can pass all tests. Submission

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Could someone explain, why into the Editorial for problem E the following property applies.

$$$\mathbf{f}(i) = (i + A_i) mod N$$$

Editorial Reference : https://atcoder.jp/contests/abc241/editorial/3480

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The function $$$f$$$ represents applying the operation one time. Note that the only thing that matters is the remainder of candies modulo $$$N$$$, since we never actually need the total value. Also, modulo operation distributes across sums. So if we currently have $$$i$$$ candies modulo $$$N$$$, then the amount of candies we will have after applying the operation is $$$f(i) = (i + A_i) \mod N$$$.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Gotcha, thanks for the clear explanation.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E, I find the period as follows.

At first, we add A0, and then we add Ax, where x=A0%N. To make this more clear and simple, we could just set x=3(note that it could be any index), i.e., A0,A3. Similarly, we could just write down the added elements in a sequence like, A0,A3,A7,A4,...

Note there are at most N elements, and thus sooner or later, the same element will be added again. For instance, A0,A3,A7,A4,...A9,A7, where A7 is the first element which appears again. This means, (A0+A3+A7+A4+..+A9)%N=7, and (A0+A3)%N=7, which further implies that (A7+A4+...+A9)%N=0. Therefore, (A0+A3+A7+A4+...+A9+A7)%N=(A0+A3+0+A7)%N=(A0+A3+A7)%N=4. Then, the next added element after A7 is A4. Now, we could see that the sequence becomes A0,A3,A7,A4,...A9,A7,A4, and by similar induction, we could see that the period has been found, which is (A7,A4,..A9). Finally in a word, the sequence is A0,A3,(A7,A4,..A9),(A7,A4,...,A9),...

→ Reply