maroonrk's blog

AtCoder Regular Contest 135 Announcement
By maroonrk, history, 3 years ago, In English

We will hold AtCoder Regular Contest 135.

The point values will be 300-500-500-700-800-1000.

We are looking forward to your participation!

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

Comments Comments (49)
| Write comment?
»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Is that Rated?

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

    Yes.
    All beginner, regular and grand contests are rated

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

    Yes, they are usually rated (AtCoder Regular Contests are rated for ratings up to 2799 in their platform).

    Around the end of last year, 2021, AtCoder has started providing options to register for a Rated contest either as Rated Participant or Unrated Participant. If you do a Rated Registration against a competition, be sure to participate in it because it will affect your rating whether or not you participate in that contest, or unregister at least 5 minutes before the contest begins.

    More information regarding it here, in their post on it: https://atcoder.jp/posts/745

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

Arc is awesome.

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

Good luck to every participant!

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

AtCoder Regular Contest 135 is begun.

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

What's the reasoning behind putting such hard problems as DEF in a contest rated <2800? EF are generally unsolvable for rated participants, the ranks 70-900 are determined by the speed of solving ABC.

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

    Once I thought that there's only SpeedForces.

    And now I learn there's also SpeedCoder.

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

    wtf dude

    imagine crying over difficulty distribution on a contest full of amazing problems.

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

    non-negligible number of rated people solved E today

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

Can anyone explain C please.

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

      Thank you ! Turns out i read the question incomplete and completely missed the line "do operation for every i (⊕ denotes the bitwise XOR operation)". I started solving using basis and messed it up.

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

    The main observation is that the second XOR operation kind of negates the first. So actually we do only one XOR operation, with one of the a[i].

    Knowing this we only want to find which one. That can be done by counting the number of set bits at each bit-position, and then try each a[i] as the candidate for the XOR operation.

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

how to solve task A? i trying to finding pettern but getting wa

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

    Just do recursion with memoization. Submission

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

    I solved this task with a memorized dfs.We can see that if there is an integer x(x<=4),we can't get a better result by breaking it down.

    That also means if there is an integer x(x>4) ,we can get a greater product by change it to x/2 and (x+1)/2.So I used kind of memorized searching.

    Here is my code

    Hope it will help you.

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

      Fact: Spliting N into n integers such that their a_1 + a_2 + ... + a_n = N and try to maximize a_1 * a_2 * ... * a_n. Doing some math, when a_i = e (2.718...) we can obtain the maximum product. Since we are dealing with integers, 2 and 3 are the closest integers from e.

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

        Wow.I didn't realize that before.I was just trying to split 1,2,3,4,5,6... and to find something.Thanks.That's awesome.

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

I tried to use Linear Programming Dual to solve D. Sadly it only gave me the answer, but not the actual construction.

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

Can anyone explain B, please!

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

    For n=1 , The answer would be Directly s[0] , 0 , 0 .

    s[i] = a[i] + a[i+1] + a[i+2]
s[i+1] = a[i+1] + a[i+2] + a[i+3]
Thus a[i+3] - a[i] = s[i+1] - s[i]

    Thus once we fix the values of a[0] , a[1] and a[2] the other elements of a get fixed. Try to find minimum a[0],a[1],a[2]>=0 such that for all remaining i a[i]>=0 if s[0]>= sum of those minimum values of a[0] a[1] and a[2] then The solution is possible else not

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

      "Try to find minimum a[0],a[1],a[2]>=0 such that for all remaining i a[i]>=0 if s[0]>= sum of those minimum values of a[0] a[1] and a[2] then The solution is possible else not" , can you elaborate this , and your thought process

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

        let us assume a[0]=0 , a[1]=0 ,a[2]=0 because a[i]>=0 now using a[i+3]=a[i]+s[i+1]-s[i] we will get the remaining values of a[i], Now since a[i]>=0 is mandatory so if some a[i] comes negative we need to make is >=0 we take three variables mn0,mn1,mn2 where mnj = min(a[i]) such that i%3 = j . After this process we increase all a[0],a[3],a[6] by abs(mn0) all a[1],a[4],a[7] by abs(mn1) all a[2],a[5],a[8] by abs(mn2) if now s[0]>=(a[0]+a[1]+a[2]) then we can proceed further otherwise not. if s[0]>=(a[0]+a[1]+a[2]) then let d = s[0] — (a[0]+a[1]+a[2]) , we increase all a[0],a[3],a[6] again by d and print array a

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

        We can see that i+3 can be obtained from i, thus we get a chain of values that are dependent on each other like (0,3,6,9,..),(1,4,7,10,..) and (2,5,8,11,..). Thus if we somehow choose optimally (0,1,2) such that every A[i]>=0 in our answer array we are done. We can do that by assigning the first member i.e (0,1,2) from each chain at least the absolute value of the minimum running sum as it would make every element in the worst case equal to 0 but not less than it such that A[0]+A[1]+A[2]=S[0] is satisfied otherwise answer is not possible.

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

    I have solved it as follows:

    If we have some $$$i$$$ where $$$S[i]=0$$$, this uniquely determines the answer, where $$$A[i]=A[i+1]=A[i+2]=0$$$, and we propagate other values accordingly in $$$A$$$ to satisfy those in $$$S$$$. Suppose the minimum value in $$$S$$$ is $$$min$$$, we can subtract $$$min$$$ from all values in $$$S$$$ and calculate an answer $$$AnsTmp$$$.

    Now we want to change $$$AnsTmp$$$ in some way to account for the $$$min$$$ we subtracted earlier. This is like calculating answer $$$AnsTmp2$$$ for an array $$$S$$$ whose all values are all $$$min$$$. In this case, if the first $$$2$$$ elements in $$$AnsTmp2$$$ are $$$a$$$ and $$$b$$$, the third value will be $$$min-a-b$$$, the fourth will be $$$min-(min-a-b)-b=a$$$, the fifth will be $$$min-a-(min-a-b)=b$$$, and so on, this means $$$AnsTmp2$$$ will be similar for all $$$i$$$ which are equal $$$mod$$$ $$$3$$$.

    Let's see the minimum non-negative integer for each $$$i$$$ from $$$0$$$ to $$$2$$$ which if we added to $$$AnsTmp[j]$$$ ($$$j$$$ $$$mod$$$ $$$3=i$$$) will make $$$AnsTmp[j]$$$ non-negative for all $$$j$$$ and add them to $$$AnsTmp2$$$. If $$$AnsTmp2[0]+AnsTmp2[1]+AnsTmp2[2]>min$$$, then there is no answer. Else we can just add $$$min-AnsTmp2[0]-AnsTmp2[1]-AnsTmp2[2]$$$ for $$$AnsTmp2[i]$$$ ($$$i$$$ $$$mod$$$ $$$3=0$$$) and each $$$ans[i]$$$ will be just $$$AnsTmp[i]+AnsTmp2_[i]$$$.

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

Try to find minimum a[0],a[1],a[2]>=0 such that for all remaining i a[i]>=0 if s[0]>= sum of those minimum values of a[0] a[1] and a[2] then The solution is possible else not .. don't undestrant please briefly explain.

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

For A, Why does this logic fail?

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

    Note that in max(val,ch). U hv taken the mod of ch in step ll ch = (recurse(op1)%mod * recurse(op2)%mod)%mod;. So even if ch would hv been actually big than val, it would hv become less than val after mod. The observation is that, u only hv to avoid splitting the numbers if they are less than or equal to 3. Handle that seperatly, and keep dp[val]=ch;

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

Could anyone tell me why my submission for A gives WA for large test case. I believe the problem is how I apply the modulo operation.

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

    The idea with mod is to mod the result of computations, but your code is MODing the input numbers, which will of course not yield the correct answer. Consider n = MOD * 2. Your code obtains p1 = p2 = MOD, which immediately just becomes 0.

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

My solution to arc133c is almost the same with today's D. Cannot imagine it can be used in another arc!

code1 code2

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

In the editorial of problem E, there is one argument:

$$$B_i<\frac{X}{i}+i$$$ for every $$$i$$$.

It is easy to be proved, but I don't really know how to get it. Could anyone explain the way to get it?

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

    Maybe we can notice the increasing rate of A[], which is of $$$O(n^2)$$$, so we have got an upper boundary of A[]. Then we divide it by $$$i$$$ (according to B[]'s definition) to see what happens on B[].

    The $$$O(n^2)$$$ thing: notice that A[i+1]-A[i] <= i+1, so A[i] — X = A[i] — A[0] <= (i+2)(i-1)/2.

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

      Thanks! It's really a good way!

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

In prob B. Im still confused how to determine a, b in $$$A$$$

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

    Sadly, I didn't solve the problem during the contest, but I upsolved it afterwards (with editorial).

    I'll try to explain. If I can do it, that means I understand how to solve this problem. :-)

    First, you forget the condition $$$0 \le A_i$$$ for a moment. Just choose some random $$$A_1 = a$$$ and $$$A_2 = b$$$.

    Doing some math, we have $$$S_i = A_i + A_{i+1} + A_{i+2}$$$, and $$$A_{i+2} = S_i - A_{i+1} - A_i$$$. So, if we know $$$a$$$ and $$$b$$$, we can determine all other terms of sequence.

    Now we continue our math (with the formula for $$$A_{i+2}$$$ above):

    $$$A_1 = (0) + a$$$ (by definition)

    $$$A_2 = (0) + b$$$ (by definition)

    $$$A_3 = (S_1) - a - b$$$

    $$$A_4 = (S_2 - S_1) + a$$$

    $$$A_5 = (S_3 - S_2) + b$$$

    $$$A_6 = (S_4 - S_3 + S_1) - a - b$$$

    $$$\dots$$$

    We can now see the pattern:

    $$$A_i = (x_i) + a$$$, for $$$i = 1, 4, 7, \dots$$$

    $$$A_i = (x_i) + b$$$, for $$$i = 2, 5, 8, \dots$$$

    $$$A_i = (x_i) - a - b$$$, for $$$i = 3, 6, 9, \dots$$$

    for some mystery constants $$$x_i$$$.

    But how do we know these constants $$$x_i$$$? Well, we can choose $$$a$$$ and $$$b$$$ to be equal to $$$0$$$ and compute them directly.

    We now recall the condition $$$0 \le A_i$$$. To fulfill this condition, we need the following satisfied:

    $$$A_i = (x_i) + a \ge 0$$$, for $$$i = 1, 4, 7, \dots$$$

    $$$A_i = (x_i) + b \ge 0$$$, for $$$i = 2, 5, 8, \dots$$$

    $$$A_i = (x_i) - a - b \ge 0$$$, for $$$i = 3, 6, 9, \dots$$$

    Rearranging, we get:

    $$$-x_i \le a$$$, for $$$i = 1, 4, 7, \dots$$$

    $$$-x_i \le b$$$, for $$$i = 2, 5, 8, \dots$$$

    $$$a + b \le x_i$$$, for $$$i = 3, 6, 9, \dots$$$

    Let's take a closer look. The first two inequalities tells us that we want to maximize $$$a$$$ and $$$b$$$. The third inequality tells us that we want to minimize $$$a + b$$$. So, we can try to take the minimum possible $$$a$$$ and $$$b$$$.

    The minimum possible $$$a$$$ is $$$m_a = max(-x_1, -x_4, -x_7, \dots)$$$.

    The minimum possible $$$b$$$ is $$$m_b = max(-x_2, -x_5, -x_8, \dots)$$$.

    The maximum possible $$$a + b$$$ we allowed to have is $$$m_s = min(x_3, x_6, x_9, \dots)$$$, otherwise we can't satisfy the condition for at least one of $$$x_3, x_6, x_9, \dots$$$

    So if $$$m_a + m_b \gt m_s$$$, that means we can't satisfy all three conditions above for at least one of $$$x_i$$$ and the answer is NO. Otherwise the answer is YES and we can take $$$a = m_a$$$ and $$$b = m_b$$$.

    Now we can easily restore the whole answer.

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

      Thank you for your kind explanation.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it 
      A1=(0) + a
A2=(0) + b
A3=(s1) - a - b
A4=(s2-s1) + a
A5=(s3-s2) + b
A6=(s4-s3+s1) - a - b
A7=(s5-s4-s1+s2) + a
....
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, my poor math. I knew I was wrong somewhere.

        Thank you for pointing this out.

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

These problems really inspire me a lot! Thank you, great author and testers, for your hard work. Also, once again, I have realized that there is still a long way to go. It took me about 90 minutes to solve abc while for top ones, it is just 10-minutes work. Hope that someday, I could be like this as well.

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

Need a bit of help in problem C.Is there any proof of the fact that performing at max one operation is enough to find our final answer?The editorial just states that the answer could be obtained by zero or one operations but does not have any proof attached to it.Thanks

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

    Think of 2 operations, selecting number $$$B_0$$$ and $$$B_1$$$. $$$B_0$$$ is selected first, it's in the original array. Then consider $$$B_1$$$, there must be some $$$A_0$$$ in original array such that $$$B_1=B_0\oplus A_0$$$, because you must choose it in the new array you got after selecting $$$B_0$$$. Then we discover that the operation sequence $$${B_0,B_1}$$$ is totally equivalent to one single operation of choosing $$$A_0$$$.

    If there's more than 2 operations, we compress the first 2 into one single operation $$$O$$$, then do so to $$$O$$$ and the 3rd operation, until there's only one operation in the queue.

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

    you can think like this,

    v = A1 A2 A3 A4

    after performing operation with x = v[1] = A1

    0 A1^A2 A1^A3 A1^A4

    after performing operation with x = v[4] = A1^A4

    A4^A1 A4^A2 A4^A3 0

    which is same as if you do operation on A1 A2 A3 A4 and x=v[4]=A4

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

in problem E: how to solve the inequality $$$\lceil \dfrac{B_i - cx}{i+x+1} \rceil-1\lt c$$$ that pops up when getting the bounds for all $$$B_i-B_{i+1}=c$$$?

Also can someone please teach me how to handle the general cases when ceilings are in the left of a less than symbol? Will I have to consider whether the expression inside is a integer or not?

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

For problem D, I wanted to know if the subproblem:

Given row-sums and col-sums for all rows and columns, construct a grid with minimum absolute sum of its elements.

is well-known?

→ Reply