### I_Love_YrNameCouldBeHere's blog

By I_Love_YrNameCouldBeHere, history, 3 months ago,

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

We hope everyone had fun and enjoyed the contest!

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

 » 2 months ago, # |   0 great round! thanks for setting!
 » 2 months ago, # | ← Rev. 2 →   0 ....
 » 2 months ago, # |   +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 :(
•  » » 2 months ago, # ^ |   +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.
•  » » » 2 months ago, # ^ |   0 Thanks for the explanation :)
•  » » 2 months ago, # ^ |   0 this is quite similar but a little more interesting.
 » 2 months ago, # |   0 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, # |   +5 E was not clear in the statement whether it is substring or subsequence, I was first solving the latter case.
•  » » 2 months ago, # ^ |   0 Did you notice the problem name?
•  » » » 2 months ago, # ^ |   0 You didn't get, you count substrings but it is not clear whether you should care about t as a subsequence or as a substring.
•  » » » » 2 months ago, # ^ |   0 Ah cool, got it now. Sorry!
•  » » 2 months ago, # ^ |   +8 Sorry for the confusion
•  » » 2 months ago, # ^ |   0 can you give me inbuilt fn on how to convert a string to integer value?
•  » » » 2 months ago, # ^ |   0 stoi(x) — converts string x to integer and returns it.
•  » » » » 2 months ago, # ^ |   0 I don't recommend this, because it won't work for long long.
•  » » » » » 2 months ago, # ^ |   0 Use stoll(x) for long long
•  » » » » » » 2 months ago, # ^ |   0 Thanks man, did not knew about this.
•  » » » 2 months ago, # ^ |   0
•  » » » » 2 months ago, # ^ |   0 thank y'll
•  » » » » » 2 months ago, # ^ |   0 string s="sss"; int x=stoi(s); cout<
•  » » » » » » 2 months ago, # ^ |   0 try with strings "123", "10123" or others. Stoi converts strings to integers but the string has to be a number (formed only of digits).
 » 2 months ago, # |   +4 Cool contest, F was a pretty interesting task!
•  » » 2 months ago, # ^ |   0 Thank you!
 » 2 months ago, # | ← 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:void solve(int tc = 0) { int n; cin >> n; vector arr(n); FOR(0, n) cin >> arr[i]; sort(arr.begin(), arr.end()); if(n == 1){ cout << 0; }else if(n == 2){ int v = arr[n — 1]; ll ans = 0; FOR(0, n){ ans += abs(arr[i] — v); } cout << ans; }else if(n == 3){ int val = arr[1]; ll ans = 0; FOR(0, n){ ans += abs(val — arr[i]); } cout << ans; }else{ ll first = arr[(n + 1)/ 2]; ll second = arr[((n + 1) / 2) — 1]; ll value = (first + second) / 2; ll ans = 0; FOR(0, n){ ans += abs(value — arr[i]); } cout << ans << "\n"; } } 
•  » » 2 months ago, # ^ |   +22 Write from your main account and provide a submission link. It's then easier to see the test.
•  » » » 2 months ago, # ^ |   0
•  » » » » 2 months ago, # ^ |   0 Assume a={1,2,3,4,5}Then first=3, second=2, value=2... wrong answer. You can ignore second and value, just use first.
 » 2 months ago, # |   +3 I enjoyed the Contest, please do make more like it
 » 2 months ago, # |   0 Could you write the editorial's URL at contest top page? https://codeforces.com/gym/102873It will be more helpful! :)
 » 2 months ago, # |   +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.
 » 2 months ago, # |   +1 great editorial.thank you for making this.
 » 2 months ago, # |   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?
•  » » 2 months ago, # ^ |   0 You have to put " return 0; " after printing answer for x<=0 else you will print NO 2 times.
 » 2 months ago, # |   0 I believe if you swap problems B and F nobody will notice and more people will have solved F.
 » 2 months ago, # | ← 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.
•  » » 2 months ago, # ^ |   +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.
 » 2 months ago, # |   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 !!
•  » » 2 months ago, # ^ |   +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.
•  » » » 2 months ago, # ^ |   0 ok thanks
•  » » 2 months ago, # ^ |   +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.
•  » » » 2 months ago, # ^ |   0 sure will look into it again
 » 2 months ago, # |   -6 Problem E is the best problem from the whole didn't see such good problem in a while.
•  » » 2 months ago, # ^ |   0 ok, mathbot
 » 2 months ago, # |   +1 Great round! Please set more rounds like this.