idkwhatisthis's blog

By idkwhatisthis, history, 2 months ago, In English

The problem B of today's educational round was unusual. I struggled a lot and solved it very slowly. But after doing so I was able to solve C, D, E quickly enough which saved my ass. I am totally clueless as to why I sucked so much. I saw demoralizer and some other high rated coders struggle in it too. What is your opinion on this problem? What was your thought process? What should one do to improve one's skill in this type of problem? The tag says it is a number theory problem. Do you think it would be enough to practice number theory to get a greater grasp? Or would you suggest something else? Please let me know in the comment section!

 
 
 
 
  • Vote: I like it
  • -45
  • Vote: I do not like it

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

EZ problem for me and very sus You solved C,D,E and not B?

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

If n is even, it's very trivial two cats don't meet each other since there's no middle. Just output k % n == 0 ? n : k % n

If n is odd, then you have to consider how many times cat B skips cat A. Since, there's a middle the very first time the cat B skips cat A is when $$$k = \frac {n + 1} 2$$$. Notice that cat B will always meet the other cat in the middle regardless of indices. But after the first skip it'd only take $$$n / 2$$$ steps to let cats meet each other. Therefore, output


k += (k - 1) / (n / 2); std::cout << (k % n == 0 ? n : k % n) << '\n';
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah i thought the same thing, but int terms of skips of 1 and skips of 2 and whenever they have a cycle they skip 2, so I just calculate the length of the cycle and divided it by k, so how many times the cycle appears. Then I just added the rest of the extra jumps to k and I got the answer.

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

      Nice. You can just rather add the skips once. And, One bug in your template LARGE = 0 << 18 is just 0 it should be 1. And why are you accessing negative index in your template? I consider it as sin.

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

        I apologize sir.

        But for real, vs code vim did this weird thing where it decreased all the numbers in the file. Still trying to figure out how I did it so I don't do it again. I fixed it like 12 hours ago but still searching on gvim website on how to do this if it is not possible.

        (It's also possible this could be a result of vs code directly and not the vim extension.)

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

      Let me explain a bit more. Whenever a cat jumps extra, it takes 2 steps, not one. This property lets us count k moves and add on how many times the cycle appears in the problem (n/2). Then we take how many times the cycle appears in the problem and add that to k. Overall, we don't have to simulate the problem that much because we can count the amount of extra positions we jump.

      P.s. (Sorry about the sloppy writing, I am just a teenager.

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

        I just meant this

        std::cout << (k + (--k / (n / 2))) % n + 1;
        

        instead,

        std::cout << (k - (--k / (n / 2)) + 2 * (k / (n / 2))) % n + 1;
        
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Still I am unable to understand. "notice that cat b meet other cat in middle". How? Cats never meet.

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

      $$$n = 5$$$

      $$$[1, 2, 3, 4, 5]$$$

      $$$(CatB_{pos}, CatA_{pos})$$$

      $$$(1, 5), (2, 4), (4, 3)$$$

      $$$[4, 5, 1, 2, 3]$$$

      $$$(5, 2), (2, 1)$$$

      $$$[2, 3, 4, 5, 1]$$$

      $$$(3, 5), (5, 4)$$$

      So on...