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.**

- Contest URL: https://atcoder.jp/contests/jsc2021
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210417T1610&p1=248
- Duration: 120 minutes
- Number of Tasks: 8
- Writer: kyopro_friends, QCFium, tatyam
- Rated range: ~ 1999

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

We are looking forward to your participation!

Is it Rated?

:) 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 ?

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.

Sorry, different problem.

I'm not sure how you approached it. I got the same verdict as well.

After

splittingthe 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 thesecond bestoption in some index, to make it $$$level 1$$$ . I considered themiddle index of some halffor this as well which is wrong, since changing that would not reduce the level. Fixed it 1 minute after the contest :'(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 numberssupport removing and adding numbersfind the number of elements less than a specified valuefind the sum of elements greater than a specified valueBy 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?

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?I'm also still thinking about this, about both approaches. My thoughts about the second approach up to now are:

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)