chokudai's blog

Japanese Student Championship 2021 Announcement
By chokudai, history, 4 years 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

Comments Comments (17)
| Write comment?
»
4 years 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?

→ Reply
  • »
    »
    4 years 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 ?

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry, different problem.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    → Reply
  • »
    »
    4 years 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 :'(

    → Reply
    • »
      »
      »
      4 years 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!

      → Reply
»
4 years 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).

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

    The data structure is called Binary Indexed Tree
    My submission.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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

        → Reply
    • »
      »
      »
      4 years 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?

      → Reply
»
4 years 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

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply