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!
:)
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 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 :'(
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:
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?
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
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 \lt = A-B$$$. This we can check for all m descending (c increasing). It is always true for m=1 so it will terminate.