rng_58's blog

By rng_58, history, 3 weeks ago, In English,

Sorry for the late announcement and unusual time. It was hard to find a good slot (some local marathon contest and SRM on Saturday, Open Cup on Sunday, sponsored ARC in the next week, TCO after that, etc.)

We hope to hold two more AGCs in this year (excluding this AGC), and guarantee at least one.

We will hold AtCoder Grand Contest 040. This contest counts for GP30 scores.

The point values will be 300 — 600 — 800 — 1100 — 1400 — 2200.

We are looking forward to your participation!

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

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

I have to say I really love this start time. US time is changing one hour eaRlier soon, which makes usual atcoder start time to be 7am ET...

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

    But Chinese have to stay up late :(

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are correct!It is too unfriendly for us Chinese ,especially high schooll students

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

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

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

This contest will have editorial?

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

How to solve C? I only found that a sequence can be eliminated iff $$$-(cou[AC] + cou[CB] + cou[CC]) \leq cou[AB] - cou[BA] \leq (cou[BC] + cou[CA] + cou[CC])$$$

This is since we can first select for every $$$C$$$ whether it is a $$$A$$$ or a $$$B$$$, then eliminate the string containing only $$$A$$$'s and $$$B$$$'s. This is possible iff $$$cou[AB] = cou[BA]$$$.

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

    Change all odd A into B and odd B into A. Now you can't delete AA or BB. Any string with at most $$$n/2$$$ As and Bs is good.

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

    Typical trick of inverting character in an odd position. I failed on such problemsetting trick for 5+ times. Why I don't change...

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

    For any sequnce, build a bipartite graph where left half is odd positions and right half is even positions. Connect two positions if they are not $$$AB$$$ or $$$BA$$$. My guess (Sorry, no proof yet) is that the sequence can be eliminated iff the graph have a perfect matching.

    Then because of Hall's theorem, we have something like $$$cnt[A] + cnt[C] >= cnt[A']$$$, $$$cnt[A'] + cnt[C'] >= cnt[A]$$$, $$$cnt[B] + cnt[C] >= cnt[B']$$$ and $$$cnt[B'] + cnt[C'] >= cnt[B]$$$. $$$A, B, C$$$ are for the left positions; $$$A',B',C'$$$ for the even. Then the problem becomes a much more straightforward one.

    P.S. Oh god, this sounds an overkill.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For the string $$$ABAABA$$$, $$$\{ 0-3, 1-4, 2-5 \}$$$ is a perfect matching but it is not possible to eliminate the string by pairing those positions.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I can iteratively remove the two middle elements, right?

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sure, but then you're pairing different positions ($$$\{ 0-5, 1-4, 2-3 \}$$$).

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

            Yeah. There is no one-to-one correspondence from matching to elimination order. I think I am just accidentally right on my guess because of the special property of this problem.

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

    My approach seems different to the editorial.

    I try to count the number of non-emptiable strings. If $$$s$$$ is emptiable, then there is a way that after replacing every $$$C$$$ to either $$$A$$$ or $$$B$$$, $$$s$$$ becomes a valid braket if we regard $$$AB$$$ as the left (resp. right) braket and $$$BA$$$ as the right (resp. left) braket. We see that $$$A$$$ and $$$B$$$ are equivalent (or swappable), the answer will be

    $$$ 3^n - 2*(\text{the number of non-emptiable strings if we regard $$$AB$$$ as the left braket}). $$$

    Now, if $$$AB$$$ is regarded as a left braket (+1), then $$$BA, CA, CC, BC$$$ (4 items) are regarded as right brakets (-1), $$$AA, BB, AC, CB$$$ (4 items) are regarded as nothing (or empty brakets) (0). Now consider the generating function $$$f(x) = x+4+4x^{-1}$$$, then the number of non-emptiable strings if we regard $$$AB$$$ as the left braket is the sum of coefficients for all $$$x^k (k > 0)$$$ in $$$(f(x))^{n/2}$$$.

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

      I'm counting non-emptiable strings with a different condition: let $$$A_1$$$ be the number of 'A' at odd positions and $$$B_0$$$ the number of 'B' at even positions, then if $$$A_1+B_0 > N/2$$$, the string is non-emptiable; the same holds if 'A' and 'B' are flipped, but that gives the same number of cases. Why are they non-emptiable? The number of 'A' or 'C' at even positions is $$$N/2-B_0 < A_1$$$ and each 'A' at an odd position has to be paired with one of them, which is impossible.

      I haven't proved why all other strings are emptiable, but it makes sense intuitively — there will always be a pair 'AA', 'BB' or a suitable removal with 'C'.

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

Is C — sum(0 to n/2)ncr(n/2,i)*2^(2i)*3^(n/2-i)?

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

I think the editorial for A is slightly wrong.

It says "Thus, the answer is the sum of these lower limits". I think it should be the max, right?

»
2 weeks ago, # |
  Vote: I like it +58 Vote: I do not like it

I just wanted to say that problems are of amazing quality O_O

maroonrk, how do you even do this every time?

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

What the hell is wrong with my solution for D? ...

My idea is that when the planks are split into those where Snuke and Ringo are getting closer ("near") and where they're getting farther away from each other ("far"), then we want some "far" planks at the beginning, then some "near" planks and finally the remaining "far" planks. These last "far" planks can be ignored — if Ringo is on them, there's no way to reach him. Now, if Snuke can catch Ringo, then Snuke can reach the end of the sequence of "near" planks faster, so we want to find a point $$$x$$$ such that the time Ringo takes to reach the end of the "near" planks from this point is greater than the sum of $$$A_i$$$ of all "near" planks and all "far" planks put at the beginning; the probability is $$$x/N$$$.

Then, if $$$x$$$ is on the "far" planks, we can throw out a "far" plank and $$$x$$$ won't decrease. Therefore, $$$x$$$ only depends on $$$B_i$$$ of "near" planks, not "far" planks, and for a fixed number of "far" planks at the beginning, we want the sum of $$$A_i$$$ to be as small as possible, so we should sort "far" planks by $$$A_i$$$ and consider only the prefixes of this sequence. On the other hand, we should sort "near" planks by $$$B_i$$$ (their $$$A_i$$$ only contribute to the time mentioned above) and $$$x$$$ is the (number of "near" planks + "far" planks at the beginning) minus $$$(k + d)$$$, where the time we want to reach is the sum of $$$B_i$$$ of the last $$$k$$$ "near" planks plus $$$d \cdot B$$$ for the last $$$k-1$$$-th "near" plank.

It gets WA. I don't see any mistake in the reasoning.

Anyway, very nice problems. I didn't get to reading E/F at all, but B-D were excellent.

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

    x can be on far planks — 2 8 4 7 14 here x is 3/4 if we keep first plank before 2nd plank.

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

can someone please proof why only this kinds of solution is required in B?

"we can solve it by actually sorting the indices in this way and try all candidates of the solution in this form one by one."

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

For B I got AC but still, I am unable to prove correctness of my solution.(Even I don't know if the approach is correct or not).

sort the pairs based on l and then on r

initially maintain p= a[0] and q=a[1] and ans=total number of happy participant using only 2 problems

then for each pair in the array, see which is better

p=merge(p,q) q=a

p=merge(p,a) q=unchanged

q=merge(q,a) p=unchanged

calculate participants for all of the above cases and then make the best possible assignment.

Can anyone tell me if this approach may fail on certain test case. If it doesn't then please can someone help in deriving proof of correctness.

I submitted and got AC just based on intuition.

Thanks.

»
2 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

Thank you for your participation!

You may have noticed "Sample" data set did not contain any test during the contest.(Though sample tests are included in "All" set.) It was a misconfiguration and now fixed.

Sorry for the inconvenience, but I believe the effect is negligibly small.

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

Hello, I'm passing all test cases for problem B except for 2, I can't figure out what's wrong with my code, can anyone help? Here's my submission: https://atcoder.jp/contests/agc040/submissions/8280444

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

    Your code returns 9. Correct output is 11.

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

      I see, my approach is actually completely wrong. Thanks for the help.

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

Thanks for the amazing problems indeed!

My screencast with commentary in Russian (by Errichto's advice): https://youtu.be/_k7ADEJGrTM

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

I enjoyed B very much, also the solution for C explained in the editorial is very beautiful.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone find errors in my logic for D ? I assume that Snuke can win if he catch up or pass Ringo at the end of some plank so I need to find the set of all the planks to the left of that plank and that plank itself. It is alway optimal to arrange set of planks by increasing order of $$$B_i$$$ to get the position $$$x$$$ that Snuke will win if Ringo start at some positon $$$<= x$$$. I can observe that is alway better to add some planks with $$$B_i >= A_i$$$ to the set and if some planks with $$$A_i > B_i$$$ locate outside range $$$[0...x]$$$ then we can remove it to get better answer. Then my solution is to put all planks with $$$B_i >= A_i$$$ to the set and iterate throught all the other planks $$$C$$$, consider scenario where that planks $$$C$$$ is the maximal $$$B_i$$$ planks with $$$B_i < A_i$$$ and add other planks with non-greater $$$B_i$$$ such that the $$$C$$$ doesn't locate outside range $$$[0...x]$$$. I repeatly take the planks with minimum $$$A_i$$$ among such planks when it is takeable. Of course I consider when there no such planks that $$$B_i < A_i$$$. My solution got WA : 8301236

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Generate some random cases and compare with some AC solution. I found a lot of mistakes in my thinking that way.