### chokudai's blog

By chokudai, history, 4 weeks ago, We will hold Japanese Student Championship 2021.

Everyone is welcome to participate. Please note that this contest will be held at a different time than usual.

The point values will be 100-200-300-400-500-600-600-600.

We are looking forward to your participation! Comments (20)
 » Is it Rated?
 » 4 weeks ago, # | ← Rev. 2 →   :) Does anybody have any idea what could be test case 57 in probem E?
•  » » Could you help me with how you handle the level 0 string to be non-palindromic ?
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   Here's what I did: First find the minimum cost $level-0$ string (by cosidering characters with max frequency), if that string is palindromic (That means its not actually a $level-0$ string), then you only need to change a single character in it to make it non-palindromic, therefore you can greedily change a character such that it increases our solution by the least amount.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   Sorry, different problem.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →
•  » » I'm not sure how you approached it. I got the same verdict as well. After splitting the string $k - 1$ times, you'll need to make all the substrings one $level 1$ palindrome. After minimizing the changes needed to make it any palindrome, it might be a higher level palindrome. So we look for the second best option in some index, to make it $level 1$ . I considered the middle index of some half for this as well which is wrong, since changing that would not reduce the level. Fixed it 1 minute after the contest :'(
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   This was the exact problem with my solution too, great observation mate! Thanks a lot!
 » Can anybody please share their data structure implementation for problem F.In the editorial, it is written that we need a data structure with following capabilities: manage the set of numbers support removing and adding numbers find the number of elements less than a specified value find the sum of elements greater than a specified value By the problem constraints, we need to implement all of it in at most O(logn).
•  » » The data structure is called Binary Indexed Tree My submission.
•  » » » Can u explain how u are getting sum of all numbers greater than x using BIT. I am unable to understand that part from your code. Thanks.
•  » » » » Sum of all numbers greater than x=total sum-sum of all numbers <=x You can find the latter part using BIT pretty easily, and you can keep a total sum variable for the rest
•  » » » yeah, but then we will have to implement it offline, by doing coordinate compression. Is there any way we can do it online?
 » 4 weeks ago, # | ← Rev. 3 →   Edit: I found my problem while writing this here down. I returned "-1" to indicate impossible, but I still was adding the changes from combining odd-lenghted palindromes. Stupid me. That's what you get from abusing signed integers and giving negative values special meaning. In Problem E I am able to solve (nearly) all cases, the cases 48-52 (the ones labeled "impossible") give me WA. I implemented and algorithm that recursivly splits the string in its substrings. Impossible can happen if: At level 0 we have only 1 character left. This one mustn't be a palindrome, but since it only has 1 character, it is a palindrome. So it is impossible. At some level L>0 we have 0 characters left. A Level L>0 palindrome must have at least 1 character. It is impossible. What am I missing? (Edit: I was missing nothing.)My submission: https://atcoder.jp/contests/jsc2021/submissions/21832753
 » When will the testcases be uploaded ? chokudai
 » In problem F acc. to solution: One can use a self-balancing binary search tree, but it can alternatively be solved with coordinates compression and segment trees. can anyone help me out on how to proceed with the second approach?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   I'm also still thinking about this, about both approaches. My thoughts about the second approach up to now are: Preprocess all the Queries and collect all Values $Y_i$ Build a segment Tree, with sorted $Y_i$ values as leaves. In the Beginning all leaves in the tree are "deactiviated". start processing the Queries for real now. Reading in a $Y_i$ activates it in the segment Tree. The tree has to be updated in regards to "Number of elements smaller than some $Y$" and "Sum of elements bigger than some $Y$" Of course you need to separate this between both trees. I'm still not sure about the details though, I will answer again when I have hopefully my own implementation.
 » Can any one tell me how to solve problem C , i am not getting it from editorial.
•  » » Maybe another (similar) way to find a solution. (It helps to look at problems from different perspectives). Assume $m$ ist the maximum possible number, such that $gcd(x,y)=m$. Then $x-y \ge m$ since both of them are divisible by m. So $B-A \ge m$But now assume $m=B-A$. Then, in order to have $gcd(x,y)=m$ both $x$ and $y$ must be divisible by $m$. Since $x-y=m$ we must have $x\mod m=0$. If that ist not the case, we can try the nextsmaller $m$. What if $m=B-A-1$? Then either $x=A$ and $y=B-1$ or $x=A+1$ and $y=B$. So either $A \mod m =0$ or $A+1 \mod m =0$. If this does not work, what if $m=B-A-c$? We can notice a reccurence: We can find such $x$ and $y$ if $(A \mod m) + c <= A-B$. This we can check for all m descending (c increasing). It is always true for m=1 so it will terminate.
 » Having trouble understanding “E — Level K Palindrome”.What will be a level-2 palindrome obtainable in 6 ops from the “aca a bcb a bab a aac”? (Sample Input 5)