rng_58's blog

AtCoder Grand Contest 021
By rng_58, history, 7 years ago, In English

AtCoder Grand Contest 021 will be held on Saturday (time). The writer is DEGwer. This contest counts for GP30 scores.

Contest Link

Contest Announcement

The point values will be announced later.

Let's discuss problems after the contest.

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

»
7 years ago, # |
  Vote: I like it +52 Vote: I do not like it

Looking forward to the contest!

Is there already a page/spreadsheet with GP30 scores?

→ Reply
»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Well, I understand that it's strange question from 8-th place, but how to solve anything except A?

I have no idea why my solition on D is correct (just remember from somewhere fact, that this value and length of maximum palindrom sub-sequence is same). And my solution of B seams to be too hard and still not fully proven.

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

    For D, isn't it obvious? Suppose for simplicity that the answer is even. We divide the subsequence into two strings, the first string s1 with the indices at most and the second s2 with the rest. Now if length(s1) > length(s2) then we can construct s1 + reverse(s1), otherwise if length(s2) > length(s1) we can construct reverse(s2) + s2. In both cases we obtain a contradiction with the maximality of length. In conclusion we must have that length(s1) = length(s2). Now if s1 + s2 isn't palindrome we can choose string s1 + reverse(s1) which is a palindrome and have the same length.

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

    B is construct convex hull and find angles. It can be seen easily that each point not on convex hall has finite area or linear dependence on R . for points on convex hull area is of the order of sector area by that 180- angle so it is R*R order. So ratio of 180-angles will be enough

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

      Well, I had the same, but it looked like too hard for 600-point.

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

        It also looked too hard for me, so I decided to keep things simple:

        Let's take a very big circle (R=1e9 isn't big enough but I was lazy to check it in advance and got WA because of that; 1e11 or 1e12 will work better) with center at (0,0). Let's take 1e6 points on it and find answer for each of these points; such approximation will be good enough to get AC :)

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

        Note that we don't need to construct convex hull explicitly because of the low constraints. Please check editorial for details.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for B, please?

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

    The editorial is posted (you can see the English solutions in its second half)

    → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I've read the editorial for problem E and since there's no forum to ask questions, I'll ask here. Firstly, I don't totally agree with the y-x>=B-N+1 restriction in the case when R=B (for the record, I do understand what conditions the sequence must fulfill in order to be counted). Since y represents the count of blue balls and x represents the count of red balls at a point, at least in the particular case when R=B, in order to meet the "red, blue" subsequences requirement, x should be greater than or equal to y (x >= y). That is, the point should never enter the region y-x >= 1, which is totally different from B-N+1 (which btw I have no idea where it comes from). Also, this condition is enough (it also implies that the path passes through (R, B-1)). Where is my reasoning wrong? Anyway, the problem is that I wouldn't be asking here, if I knew how to continue it. The problem is that when B<=R<=B+N-1, we need to have at least N-R+B red-blue subsequences, and in this case I really can't see such an easy interpretation of the constraints: I'd say that only for y>=something (namely, for the last N-R+B blue balls), the points must have y — something <= x (to assure that we have enough many red balls to choose from in order to match the current blue ball). The problem is not the formula, but that in this case, the restriction starts to be applied only after a certain values of y. I guess the editorial can't be that wrong, so could you please briefly explain me where is my reasoning wrong? (and/or note if there is any mistake in the editorial — I really can't see how the formula in the R=B case makes any sense)

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

    I got stuck on the same point. I think you should consider the case n=2, k=6. For example, if we only check we never enter y-x >= 1, we will miss a sequence like "RBBRRB" which is valid.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Holy shit, you're right! I now realize that when I wrote the comment, I was thinking of something like B=R=N (when all the Bs have to be matched with a R that appeared before). I have to rethink the condition, but now that you helped me realize I was totally losing track of N, I think I can. Thanks!

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please upload testcases?

Could I get 27.txt of task C:

input and the answer (YES/NO)?

→ Reply