chokudai's blog

By chokudai, history, 4 weeks ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +58
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it -43 Vote: I do not like it

Is it Rated?

»
4 weeks ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

:)  Does anybody have any idea what could be test case 57 in probem E?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you help me with how you handle the level 0 string to be non-palindromic ?

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

    Sorry, different problem.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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   Vote: I like it +9 Vote: I do not like it

      This was the exact problem with my solution too, great observation mate! Thanks a lot!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    The data structure is called Binary Indexed Tree
    My submission.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it +8 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the testcases be uploaded ? chokudai

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any one tell me how to solve problem C , i am not getting it from editorial.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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)