idkwhatisthis's blog

What is your opinion on today's problem B?
By idkwhatisthis, history, 3 years 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

Comments Comments (2)
| Write comment?
»
3 years 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';
→ Reply
  • »
    »
    3 years 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.

    → Reply