Блог пользователя maroonrk

Автор maroonrk, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +145
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Look forward to the new ARC!

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    YES

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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.

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Can we make problem B harder and C easier?

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Can D be solved by FFT?

  • »
    »
    3 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

    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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится
        $$$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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you make clear how the transition works? Thanks.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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}$$$

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

C & E are implementation garbage

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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?

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

What a pure implementation garbage you made to C there.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

The difficulty spike from B to C was HUGE

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Someone explain C, please.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Hints for C

    Code

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      What is your insight?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        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 .
        
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Dp Transitions
        How dp transition handles all the cases ?
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

plz explain b

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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)

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

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)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Weak test case for C

Test Case
My AC code which fails on it
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится -16 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится -6 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +16 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится -9 Проголосовать: не нравится

              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.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +34 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.