a codeforces contest.
A. Mex Game 1
so I bricked this…pretty nice problem though.
B. Non-Palindromic Substring
If , we split into two cases:
- If is even, we discover that the string is only not -good if every element is equal. Roughly, this is true because if the string begins with
abba, in order for the next substringbba?to be a palindrome, b must equala. Therefore, all adjacent characters must be equal to one another. - If is odd, then the string must be something like “ababababab…ab”. Similar reasoning as above.
We also have to account for the case when and the entire string is actually a palindrome: for this, I just copied Manacher’s from GFG.
C. Tree Compass
Not sure why the constraints are so low because it really made me doubt whether my solution was correct (UPD: I guess it’s for checker implementation?). Anyway, IMO this was the easiest problem in the contest, as I immediately considered isolating the diameter and operating from there. The one thing I missed was that if the diameter is divisible by 4, we can do better than the general even case.
D. Counting is Fun
Unfortunately I was unable to solve this in contest, but I do really like this problem. I kind of came up with the idea of pairing differences mentioned by Golovanov, but I didn’t think this would get anywhere.