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

Автор SlavicG, история, 3 года назад, По-английски

This is the editorial for the Unofficial Div 4 Round #2 by ssense SlavicG.

We hope everyone had fun and enjoyed the contest!

Video Editorial by demoralizer

Problem A — Catching the Impostor.

Tutorial
Solution

Problem B — Rabbit Game

Tutorial
Solution

Problem C — Similar Arrays

Tutorial
Solution

Problem D — Sanda's Job

Tutorial
Solution

Problem E — Count Substrings

Tutorial
Solution

Problem F — Game on Grid

Tutorial
Solution 1
Solution 2
  • Проголосовать: нравится
  • +108
  • Проголосовать: не нравится

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

great round! thanks for setting!

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

How to solve problem E if we had subsequences instead of substrings?
PS: I was trying to solve the problem for subsequences the whole time :(

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

    For every starting position $$$L$$$, find the next occurrence of $$$t[0]$$$. After that new position, find the next occurrence of $$$t[1]$$$. That's the earlier possible value of $$$R$$$ (but any bigger $$$R$$$ will also work for our $$$L$$$).

    Sorry that the statement and samples weren't clear enough.

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

    this is quite similar but a little more interesting.

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

E was not clear in the statement whether it is substring or subsequence, I was first solving the latter case.

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

Cool contest, F was a pretty interesting task!

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

Is it possible to make test cases available? I want to see which tc got me wrong ans.

Help: For C, I took the middle two elements for n > 3 and calculated its mean, and took that as my x (the number to subtract from every number in the array), I think it is correct but I got WA on tc 52. I can provide the code if needed.

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

I enjoyed the Contest, please do make more like it

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

Could you write the editorial's URL at contest top page? https://codeforces.com/gym/102873

It will be more helpful! :)

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

Thanks to problem setters, testers and everyone involved. It was a great contest. Keep making contests like these. I am up for becoming one of the testers if needed.

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

great editorial.thank you for making this.

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

For problem D, I took the difference of the two numbers a and s and kept a count of digits 0 through 9 in a and x(the difference) and compared them, but it's wrong. Can anyone please help?

My code: https://codeforces.com/gym/102873/submission/99581289

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

    You have to put " return 0; " after printing answer for x<=0 else you will print NO 2 times.

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

I believe if you swap problems B and F nobody will notice and more people will have solved F.

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

For E, what if the string T has length N. Now can it be solved in $$$O(N)$$$?
Also, can you please make the submissions of other participants visible for the contest.

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

    Yes, you would need to start from any pattern matching algorithm like KMP or hashing.

    Sadly, it's impossible to make submissions in GYM visible. Maybe it's time to change this, MikeMirzayanov? For educational purposes.

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

hey Errichto, can you plz let us know how to approach problem F. I tried to solve it during contest, but it was failing. here it the code that i submitted : https://ideone.com/Db95wz.

Thanks in advance !!

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

    Have you looked at the editorial for the problem? In your approach Alice wins only if n = 2 which is not right. Check the proof for a better understanding.

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

    No need to tag me. Authors could help you as well.

    The solution is described in the editorial. Your solution apparently prints different answers so it's wrong. In particular, Alice can win for big values of $$$n$$$ like 6 or 10.

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

Problem E is the best problem from the whole didn't see such good problem in a while.

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

Great round! Please set more rounds like this.