### 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 Tutorial of Unofficial Div 4 Round #2 by ssense SlavicG Comments (44)
 » great round! thanks for setting!
 » 2 months ago, # | ← Rev. 2 →   ....
 » 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 :(
•  » » For every starting position $L$, find the next occurrence of $t$. After that new position, find the next occurrence of $t$. 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.
•  » » » Thanks for the explanation :)
•  » » this is quite similar but a little more interesting.
 » 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
 » E was not clear in the statement whether it is substring or subsequence, I was first solving the latter case.
•  » » Did you notice the problem name?
•  » » » 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.
•  » » » » Ah cool, got it now. Sorry!
•  » » Sorry for the confusion
•  » » can you give me inbuilt fn on how to convert a string to integer value?
•  » » » stoi(x) — converts string x to integer and returns it.
•  » » » » I don't recommend this, because it won't work for long long.
•  » » » » » Use stoll(x) for long long
•  » » »
•  » » » » thank y'll
•  » » » » » string s="sss"; int x=stoi(s); cout<
•  » » » » » » try with strings "123", "10123" or others. Stoi converts strings to integers but the string has to be a number (formed only of digits).
 » Cool contest, F was a pretty interesting task!
•  » » Thank you!
 » 2 months ago, # | ← Rev. 6 →   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; 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"; } } 
•  » » Write from your main account and provide a submission link. It's then easier to see the test.
•  » » »
•  » » » » 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.
 » I enjoyed the Contest, please do make more like it
 » Could you write the editorial's URL at contest top page? https://codeforces.com/gym/102873It will be more helpful! :)
 » 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.
 » great editorial.thank you for making this.
 » 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?
•  » » You have to put " return 0; " after printing answer for x<=0 else you will print NO 2 times.
 » I believe if you swap problems B and F nobody will notice and more people will have solved F.
 » 2 months ago, # | ← Rev. 2 →   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.
•  » » 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.
 » 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 !!
•  » » 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.
•  » » » ok thanks
•  » » 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.
•  » » » sure will look into it again
 » Problem E is the best problem from the whole didn't see such good problem in a while.
•  » » ok, mathbot
 » Great round! Please set more rounds like this.