I_Love_YrNameCouldBeHere's blog

By I_Love_YrNameCouldBeHere, history, 3 months 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 HealthyUG

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

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

great round! thanks for setting!

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

....

»
2 months 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 :(

  • »
    »
    2 months 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.

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

    this is quite similar but a little more interesting.

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

Solution to E using binary search.
Since we want to find the ordered pairs [L, R].

What we can do is to select L and find the first R that makes it possible for the range [L, R] to have t included.
So all the indexes from [R, R+1, R+2, ... , N] will also form [L, R + i] that includes t.
To find the first R that includes t, I binary search on the locations where t is present.

Implementation : https://codeforces.com/gym/102873/submission/99576834

»
2 months 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.

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

Cool contest, F was a pretty interesting task!

»
2 months 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:
  • »
    »
    2 months 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.

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

I enjoyed the Contest, please do make more like it

»
2 months 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.com/gym/102873

It will be more helpful! :)

»
2 months 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.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

great editorial.thank you for making this.

»
2 months 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.com/gym/102873/submission/99581289

  • »
    »
    2 months 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.

»
2 months 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.

»
2 months 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.

  • »
    »
    2 months 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.

»
2 months 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 !!

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

»
2 months 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.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Great round! Please set more rounds like this.