SlavicG's blog

By SlavicG, history, 4 years ago, In English

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
  • Vote: I like it
  • +108
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

great round! thanks for setting!

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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 :(

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

    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.

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

    this is quite similar but a little more interesting.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Cool contest, F was a pretty interesting task!

»
4 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

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:
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Write from your main account and provide a submission link. It's then easier to see the test.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I enjoyed the Contest, please do make more like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

It will be more helpful! :)

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

great editorial.thank you for making this.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/gym/102873/submission/99581289

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

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 !!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Great round! Please set more rounds like this.