We will hold AtCoder Regular Contest 135.

- Contest URL: https://atcoder.jp/contests/arc135
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220213T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: maspy
- Tester: HIR180, tatyam
- Rated range: — 2799

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

We are looking forward to your participation!

Is that Rated?

Yes.

All beginner, regular and grand contests are rated

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

Arc is awesome.

Good luck to every participant!

AtCoder Regular Contest 135 is begun.

What is 'is begun'?

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.

Once I thought that there's only SpeedForces.

And now I learn there's also SpeedCoder.

Me too.

wtf dude

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

non-negligible number of rated people solved E today

Can anyone explain C please.

HintIt is optimal to apply the operation at most once. Suppose for the first operation we chose some number $$$x$$$ and for the second operation we chose $$$A_i \oplus x$$$. Then for some index $$$j$$$, it's new value after the second operation will be $$$(A_i \oplus x) \oplus (A_j \oplus x) = A_i \oplus A_j$$$, so the result does not depend on the first operation.

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

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

Just do recursion with memoization. Submission

I solved this task with a

memorized dfs.We can see that if there is an integerx(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 tox/2and(x+1)/2.So I used kind ofmemorized searching.Here is my code

Hope it will help you.

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.

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.

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

Can anyone explain B, please!

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

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

"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

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

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

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.For A, Why does this logic fail?

CodeNote 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;`

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.

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.

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

code1 code2

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

It is easy to be proved, but I don't really know how to get it. Could anyone explain the way to get 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.

Thanks! It's really a good way!

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

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 tominimize$$$a + b$$$. So, we can try to take the minimum possible $$$a$$$ and $$$b$$$.The

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

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

maximumpossible $$$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 isYESand we can take $$$a = m_a$$$ and $$$b = m_b$$$.Now we can easily restore the whole answer.

Thank you for your kind explanation.

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

Thank you for pointing this out.

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.

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

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.

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

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?

Ah, it's actually easy to solve, me dumb.

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?