erniepsycholone's blog

By erniepsycholone, 8 months ago, In English

1933A - Turtle Puzzle: Rearrange and Negate

Idea: snowysecret, prepared: snowysecret

Tutorial
Solution

1933B - Turtle Math: Fast Three Task

Idea: snowysecret, prepared: snowysecret, erniepsycholone

Tutorial
Solution

1933C - Turtle Fingers: Count the Values of k

Idea: dbsbs, prepared: dbsbs, snowysecret

Tutorial
Solution

1933D - Turtle Tenacity: Continual Mods

Idea: snowysecret, erniepsycholone, prepared: snowysecret

Tutorial
Solution

1933E - Turtle vs. Rabbit Race: Optimal Trainings

Idea: snowysecret, prepared: snowysecret

Tutorial
Solution

1933F - Turtle Mission: Robot and the Earthquake

Idea: erniepsycholone, prepared: erniepsycholone

Hint
Tutorial
Solution

1933G - Turtle Magic: Royal Turtle Shell Pattern

Idea: snowysecret, jerryliuhkg, prepared: snowysecret

Tutorial
Solution

Hope the contest was in some way helpful in improving your skills, and that you all had fun!

“If you only do what you can do, you will never be more than you are now.” – Master Oogway

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

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

This Round was really amazing. I really enjoyed this round. The problems are very good.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the problem F tutorial (spoiler alert): I don't understand this part: "Finally, choose the best among all n tiles after waiting for the endpoint to cycle back." can someone explain it to me?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Let $$$b_i$$$ be the minimum time needed to reach cell $$$(i, m-2)$$$ in the transformed problem. Then, it takes $$$b_i + 1$$$ time to reach cell $$$(i, m-1)$$$ in the transformed problem.

    The transformation we did is to imagine the robot moving down instead of the rocks moving up. Therefore in reality it takes $$$b_i + 1$$$ time to reach cell $$$(c_i, m-1)$$$ where $$$c_i = (i-(b_i+1)) \bmod n$$$. Hence, to reach $$$(n-1, m-1)$$$ we really need $$$b_i + 1 + \min(c_i + 1, n - 1 - c_i)$$$ time.

    Therefore the answer is just $$$\min_{i=0}^{n-1} b_i + 1 + \min(c_i + 1, n - 1 - c_i)$$$ where $$$b$$$ and $$$c$$$ arrays are defined above.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks a lot buddy

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have seen solution for same problem via simple bfs to reach to end position how come that solution works scratching my head on that for a while

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why unordered_set TLEs for question D but set doesn't?

unordered_set: https://codeforces.net/contest/1933/submission/248601138

set: https://codeforces.net/contest/1933/submission/249214209

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because there time complexity goes in order of O(n) in worst case and the same happens with unordered map also, while in simple amp and set the time complexity remains O(logn).

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For F,I dont understand why the row update 3 times like"for(int j=0;j<3*n;j++)".I try using 2 times and get WA,3 times AC.HOW?

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

    As RT can go from $$$(x,y)$$$ to $$$((x+2) \text{ mod } n,y)$$$, if x=0 currently, and $$$n \text{ mod } 2=1$$$, it would require the 2 times you mentioned. However, if $$$x!=0$$$, we need to loop $$$3$$$ times to run an entire cycle throughout a column. An example would be if RT is at $$$(3,0)$$$, with $$$n=5$$$, the following operations would be needed to run through column $$$0$$$:

    $$$(3,0)$$$ --> $$$(0,0)$$$ --> $$$(2,0)$$$ --> $$$(4,0)$$$ --> $$$(1,0)$$$ --> $$$(3,0)$$$

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot!!

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hello,I still don't understand.I used"for(int i=0;i<200*n;i++)for(int j=0;j<m;j++)" and WA on test 36. Why we should run m before n?my submission

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        observe the update exprssion,you will find out that it need m first to ensure the correctness

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, but why should it complete a cycle? like in 2 loops it is able to reach till (1,0), why should it get back to (3,0)? (my assumption is that the optimal path to reach is starting at (3,0) so going a loop back to (3,0) seems redundant)

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you for the great round!) I've finally got the pupil)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried to solve problem E using ternary search but it gave TLE on 8th test case (https://codeforces.net/contest/1933/submission/249501917), can anyone share the ternary search solution for problem E.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In E, they used the following formula to calculate the first t terms of an arithmetic series: ~~~~~ int ut = (u + (u — t + 1)) * t / 2; ~~~~~ But it is wrong because u-t+1 might be negative, and in that case, the standard formula doesn't work, but why does it pass the test cases?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, my bad. It is the correct formula, even if a0 is negative.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

my solution for problem E : https://codeforces.net/contest/1933/submission/249920547

i feel my way of applying binary search here is much easier , compared to the other solutions i saw

feel free to let me know what u think !!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://ibb.co/nR5Cb0Z

I don’t really get this part. I mean why do we need this part for implementing and how to come up with the formula i + floor(j/2), j + floor(i/2),… Please help me with this. Thank you!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Round was overall really good. Thanks.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am encountering an issue with Problem E: Turtle vs. Rabbit Race — Optimal Trainings. My solution, which produces the expected output locally on my IDE, is being marked as incorrect on Codeforces, specifically in the first test case. Here, is my submission link 253865555