maroonrk's blog

AtCoder Regular Contest 104 Announcement
By maroonrk, history, 4 years ago, In English

ARC is back!

(The problem set is organized by rng_58, but it seems that he forgot to write a blog. Thus I do it instead.)

We will hold AtCoder Regular Contest 104.

The point values will be 100-400-600-700-700-1000.

We are looking forward to your participation!

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

Comments Comments (77)
| Write comment?
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Look forward to the new ARC!

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

Just to be clear, is the point value system of ARC consistent with that of ABC in terms of difficulty of problems? As in will ARC B be as tough as ABC D, ARC C as tough as ABC F,... and so on?

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

From B to C big difficulty difference.. only for me ?

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

    YES

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

    B is much easier than C. Many contestants only solved A and B.

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

      yes.. By only solved A & B fast . i got 139+ (490 to 629)

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

    I think maybe ARC should just drop the first two problems or make them harder. The rest of ARC is div 1.5 or so, so it doesn't really make sense to add 2 "implement what you see" problems to the beginning.

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

      That way people who can solve zero hard problems are baited into participating and getting negative rating. This is why I'm scared of AGCs, since I'm one of those people. :)

      That said, I looked at today's round and today's A felt closer to an ABC A or B, not an ARC A, to my recollection of what ARCs are typically like.

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

Can we make problem B harder and C easier?

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

    I think this gives us chance to solve harder problems. But, B is too easy.

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

Can D be solved by FFT?

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

    no need, just some small constant dp will do

    mine works in roughly ("$$${O(n^2k^2)}$$$"), sorry it's actually $$$O(n \times n^2k)$$$ for n rounds and each round you need up to k * (1+2+...n/2)

    My Ac Code

    $$$ dp_{ij} $$$ means how many ways can we have maximum value used is i and sum is j

    for sum we need only values between [1, k(1+2+...n/2)]

    and you can treat average x as find how many ways can we have the sum of maximum used value

    x-1 the same with maximum used value n-x

    -- update I am not sure why it passed, but I heard that with some optimize like maintaing current maximum sum can reduce the time complexity to .. I don't know

    Hope someone can answer it for me

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

      "you can treat average x as find how many ways can we have the sum of maximum used value x-1 the same with maximum used value n-x" can someone explain it. Thanks in advance.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it
        $$$1 \times k_1 + 2 \times k_2 + ... + N \times k_N = x \times (k_1 + k_2 + ... + k_N)$$$
        $$$<=> (1-x) \times k_1 + (2-x) \times k_2 + ... + (x-x) \times k_x + ... + (N-x) \times k_N = 0 $$$
        $$$<=> k_{x+1} + 2 \times k_{x+2} + ... + (N-x) \times k_n = k_{x-1} + 2 \times k_{x-2} + ... + (x-1) \times k_1$$$

        The left side is a sum with maximum used value n-x and the right side is with maximum used value x-1. Count the number of cases where the two are equal.

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

      Can you make clear how the transition works? Thanks.

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

        so in normal transition

        when we want to count $$$ dp_{ij} $$$ , it should be

        $$$ dp_{ij} = dp_{i-1, j} + dp_{i-1, j-1*i} + dp_{i-1, j-2*i} ... dp_{i-1, j-k*i} $$$

        it takes $$$O(k)$$$ for each transition

        but now if we maintain some kind of prefix sum

        we can speed up to amortized $$$O(1)$$$

        in case when i is 1

        we just need add our dp to another array $$$ad$$$

        like in $$$dp_{ij}$$$ we know that $$$dp_{i+1, j}, dp_{i+1, j+1}...dp_{i+1, j+k} $$$ will be added $$$dp_{ij}$$$

        so we add $$$dp_{ij}$$$ to $$$ad_j$$$ and $$$-dp_{ij}$$$ to $$$ad_{j+k}$$$

        after all $$$dp_i$$$ is put into $$$ad$$$

        we do a prefix sum in $$$ad$$$

        and we know $$$dp_{i+1,j}$$$ should be $$$ad_j$$$

        consider the case when i is not 1

        the only difference will be when you do a prefix sum

        $$$ad_j += ad_{j - i}$$$ instead of $$$ad_j += ad_{j-1}$$$

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

C & E are implementation garbage

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

    Is C just writing a lot and lots of if else ?

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

      No, but there's a lot of cases where the input is "incorrect".

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

        Could you point out some not-so-obvious cases?

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

          For me the problem wasn't solved because of one missed if-else statement, and it wasn't where input was "incorrect" :( I missed the case like (1 -1), (-1 4), (3 6) where 1 and 4 must be combined to one pair, but are located in different pairs.

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

            Shouldn't it not be valid to combine pairs like that, since they said that they provide the (A, B) pairs for each i? So the (1, -1) pair is only the first person and the (-1, 4) pair is only the second person?

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

              It isn't valid, but my solution initially ignored that.

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

              It isnt valid. if you have (3, 6), then you need (2, 5) and (1, 4).

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

            And also (1,-1),(-1,3)

            and (2,3),(-1,-1),(5,8),(-1,-1)

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

What a pure implementation garbage you made to C there.

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

is anyone else think the statement is hard to understand? or just me?

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

Can anyone give a counter case for my submission of C! https://atcoder.jp/contests/arc104/submissions/17176607

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

    2

    1 4

    -1 -1

    ans should ne no

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

      Why no? it's possible that the second person gets on at 1 and gets off at 4 as well? Or did i misunderstand?

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

        Not possible

        Every floor has exactly one on or one off

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

        Read the statement it says only 1 person can get on/off at some floor so the A and B generated will themselves be some permutation of numbers from 1 to 2N respectively.

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

      Thanks ! I misread the problem!

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

The difficulty spike from B to C was HUGE

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

Someone explain C, please.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Hints for C

    Code

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

      Correct sequence will look like this ((())) (((()))) (()) some consecutive opening and equal number of consecutive endings

      What is your insight?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        I have tried some smaller cases 
1. Number of in and out is clearly equal .
2. ))(( this is Impossible 
3.( () () ) 
This type of sequence is not possible . Because length of the outer segment is clearly greater then the two inner segments . But they should be equal .
        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      During contest, I get to hint number 2 but could not think of a way to implement it. I didn't think about dp though.

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

      Hint1 & Hint2 are pretty obvious from the question itself. But can you please elaborate more on DP states and how transitions handles all the cases?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        Dp Transitions
        How dp transition handles all the cases ?
        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

plz explain b

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

    generate all substring and check if the number of 'A' character equal to the number of 'T' character ,and the number of 'C' character equal to the number of 'G' character

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

    Keep count of A, T, C and G at each position.

    Iterate over all substring where starting position $$$i$$$ and ending position $$$j$$$.

    Check condition $$$cnt(A) = cnt(T)$$$ AND $$$cnt(C) = cnt(G)$$$. If yes, increment answer.

    My submission C++ with simple code. See if it helps.

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

Actually, I don't understand C (sure my bad english). But it is written in weird case, why not write for each pair of person $$$i, j$$$ ... then $$$C_i = C_j$$$.

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

Thank you for your participation! I like D and F.

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

First, two nobrainer problems that put together barely compete with a typical div2A

And then, boom, right after them is something on the level of div2E (or D in relatively tough rounds)

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

For E, seems like if you consider all possible orderings, you only need to consider N! orderings of n numbers (with some tie-breaking rules), which is much smaller than 4386 groups mentioned in editorial for N=6 (N!=720).

My solution that generates and checks each ordering: https://atcoder.jp/contests/arc104/submissions/17177505 (Unfortunately it's a complete mess as I try to debug within last 5 minutes)

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

Looks like I am not still sure about the problem statement C.

→ Reply
»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Weak test case for C

Test Case
My AC code which fails on it
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Also, could you try to make a more balanced contest? This one was worse than most Codechef Cook-offs

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

    ARC was always supposed to be "div 1.5". I don't think it was ever aimed at pupils, or even experts. If you see here, besides A and B being way too easy, it's not like C was too out of place from a difficulty standpoint.

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

      Not like I argue that it is meant to be "div 1.5"

      But your link only confirms that the balance is often quite terrible

      I mean previous ARC had A800, B2900, C1700, D3000...

      And actually atcoder often has this kind of jumps

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

What does left and right signify in C's Editorial??

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

    A 'left' is a floor number that belongs to the set 'A'. A 'right' is a floor number that belongs to the set 'B'.

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

I think C is missing a few crucial test cases. My code gets AC even though there is a simple case where it fails.

Break case

My code answers "Yes" but the actual answer is "No".

I didn't do any sort of DP, I just check for various conditions where the answer is obviously "No". If the input passes all my checks(which is obviously incomplete) I output "Yes". So my code gives false positives but never false negatives.

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

    Not directly related to this case, but I found another simple case in which my AC code fails:

    Break case

    Maybe this kind of cases should be included in after_contest.

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

As always, here's a screencast (didn't even get close to 69th place this time) with A-D video solutions

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

Perhaps Problem C should have been a construction problem since Yes/No problem causes a lot of False Positives / Negatives.

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

Saw a lot of negative feedback, want to say that problems were nice. Wording really could be better in some problems. And yeah, difficulty estimation for C is way off, I was sure that I did some overkill while it was intended solution. But I wouldn't say that the contest is less balanced compared to other ARCs, usually the gap is from E to F though and most people just don't see it.

While I'm here... screencast with commentary if somebody is interested

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

I think the submitted solutions for C and editorialist's solution is not completely correct. Let's take the following test case:

2
-1 3
-1 4

There is only one possible solution for this test case, which is:

2
1 3
2 4

Now, in the DP approach dp[i] stores whether a possible solution exists using all the floors from 1 to i, such that people using floors from 1 to i enter and exit at floors between 1 to i only. And, the answer eventually would be dp[2*n].

So for the above mentioned test case dp should look like the following:

i: 0 1 2 3 4
dp: 1 0 0 0 1

dp[2] is false.

But, editorialist's solution (which passes) outputs the following value:

i: 0 1 2 3 4
dp: 1 0 1 0 1

dp[2] is true (should be false).

Although, dp[2*n] is correct for all solutions, and that's the only thing that matters eventually. But, I failed to understand how dp[2*n] will be always correct, even when some values in dp[i] may be incorrect.

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

    There are no people directly contradicting with segment 1-2, so dp thinks that we can use this segment.

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

      Yes, in the above case both 1 and 2 are unassigned, and the dp therefore thinks that a person going from 1 to 2 is valid. But that's not true.

      And, I think it will be better to keep track of number of people whose A and B are (-1 -1), which will help in deciding whether someone can go from i to j, if both i and j are unassigned.

      galen_colin keeps track of such people in his dp solution.

      Link to solution

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

        What do you mean by better? The solution is correct, dp[2*p] means that we can divide positions [1..(2*p)] into segments such that no person contradicts no segment.

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

          By, better I meant its easier for me to think of it when keeping track of above mentioned persons in my dp.

          Because, its difficult for me to prove the correctness of the solution mentioned in the editorial.

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

            Well that's your problem, isn't it? I don't like how you twice said that the solution in editorial is not correct. You accuse people of something because you can't understand their logic. That's not good.

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

              Well, I am sorry about how I phrased it, but I mostly meant, as you can see in my last sentence of the original comment that "I failed to understand how it will be always correct", and to understand the same was one of the reasons of posting it here.

              → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +34 Vote: I do not like it

Someone pointed out that the writer's solution code was wrong. (logic itself was ok though) We checked that the outputs of three testers’ codes were correct, and test cases used for the contest were unaffected. We don’t have hack systems, so writer’s code itself is not used during contests, therefore the contest is still rated. We apologize for the weak test cases.

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

Can anyone be kind enough to tell me how to make the "solution using Formal Power Series" of problem D?

Actually I don't how to maintain the multiply of (1-x^(k+1)i)/(1-x)...Should I use fft to get the inverse of the polynomial and multiply them？But the solution says this solution's time complexity didn't have a log element.

Can anyone help me? thks in advance.

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

I think the official editorial of the Problem C is wrong.

It reads "There is no pair of floors $$$(x+i,x+k+i)$$$ such that the person at Floor $$$x+i$$$ is 'left'."

I think the correct version is "There is no pair of floors $$$(x+i,x+k+i)$$$ such that the person at Floor $$$x+i$$$ is 'right'."

And the next sentence is in the same way.

→ Reply