Problem F: AC 4

Problem G: AC 7

Problem H: AC 5

...

Thanks for the fast editorial!

Passed G with the following solution.

Increase $$$hp_1$$$ such that $$$n$$$ is divisor of $$$\sum hp_i$$$. $$$m$$$ times choose greedily maximum group size such that it's possible to attack with this group without affecting the answer and then simulate this attacks randomly.

Any idea why this solution works?

It seems that someone is curious about what I've done on problem A. Let me describe what has happened.

Contest starts ---> Open problem A ---> A little difficult? ---> I can solve it by binary search in O(nlogn) !

===== One hour later =====

Oh my god!!!

How to solve B in O(nlogn) or O(nlog^2 n)?

I did problem B in 125 bytes (including an LF) in Ruby. I tried to squeeze author's Python solution and it became 125 bytes as well. So to me seems like a notorious coincidence.

(n,k),a=$<.map{|s|s.split.map &:to_i};p (1...n).find{|i|k<a.take(i+1).sort.reverse.values_at(*(0..i).step(2)).inject(:+)}||n

f=lambda:map(int,input().split());[n,k],arr=f(),list(f());print([i for i in range(n+1)if sum(sorted(arr[:i])[::-2])<=k][-1])

Why this is correct for C — If number of cells where A and B doesn't match in every row and column is even then answer is 'Yes' else it's 'No'?

Can someone explain the proof of problem C?

Simple DP solution for E: 52420096

I have slightly different approach on problem E. Don't know why it is true but it passed the systests. If the number of ones in the initial array is 0 then the answer is $$$sum of all elements / 3$$$(somehow we can take almost everything). If there are ones then we should compute the minimum possible amount of unused ones. Go from the end to the begginng of the array storing current amount of tiles we can use with the ones. If current $$$a_i$$$ is even the we increase this amount by $$$a_i / 2$$$, otherwise, we take one triangle from three tiles of this type and take the rest increasing amount by $$$(a_i - 3)/2$$$. Then the answer if $$$((sum of all elements) - (minimum number of unused ones)) / 3$$$.

Here's my code : 52409622

Here's a 112 byte solution to B: 52424010

The editorial for problem H is little unclear.

I think editorial proof for problem G is wrong. It states "This way the first $$$i$$$ groups will have size $$$k_i$$$", but that would require the first group to atack every enemy in different steps, which is impossible if the final answer is less than $$$m$$$.

I submitted a solution (52431440) that greedily chooses the biggest possible size for a group that doesn't waste soldiers in any atack (after incrementing the first enemy group health so that total enemy health is a multiple of $$$n$$$). It passes system tests, but I couldn't come up with a proof of its correctness yet.

Why when i choose Solution(Rus) it shows Solution(Eng)

Still can't understand the C solution/proof !

and what's the meaning of the "parity of the matrix" ?

Why can't the editorial be made easier to understand? Look at the number of people solving problems F,G and H, its hardly 20 people.

I have a doubt in Problem B. Example 2 Can anybody please explain? If there an arbitrary number of shelves then in example 2 then we can install 9 shelves and thus I will be to keep all 9 bottles of height 1 unit but not the bottle of 9 units. Then our answer will be 9...Isn't it correct?

From problem D code, I am unable to understand the purpose of "t" array and how is it helping in calculate the result. Can anyone please help me in understanding the code or suggest a simpler solution?

quick question about C i just wrote a python code for make A to B but it doesn't work like i thought.

def op(grid, sy, sx, ey, ex):
    grid[sy][sx] = 1-grid[sy][sx]
    grid[ey][ex] = 1-grid[ey][ex]
    grid[sy][ex] = 1-grid[sy][ex]
    grid[ey][sx] = 1-grid[ey][sx]


n, m = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
B = [list(map(int, input().split())) for _ in range(n)]
while A!=B:
    for y in range(1, n):
        for x in range(1, m):
            if A[0][0] != B[0][0] or A[y][x] != B[y][x] or A[y][0] != B[y][0] or B[0][x] != A[0][x]:
                op(A, 0, 0, y, x)

Here's a simple (?) general approach of solving H for $$$m$$$-tuples (instead of triples) in $$$O(n2^m + (m + k)2^{m + k})$$$. As explained above it suffices to solve the following problem: consider a set $$$t_1, \ldots, t_n$$$ of $$$m$$$-tuples of $$$k$$$-bit numbers. For a $$$k$$$-bit number $$$x$$$, say that the mask $$$y$$$ induced by $$$x$$$ for a tuple $$$t_i$$$ consists of all indices $$$j \in {0, \ldots, m - 1}$$$ such that $$$x$$$ and $$$t_{i, j}$$$ have an odd number of common bits. For each $$$k$$$-bit number $$$x$$$ and each mask $$$y$$$ of size $$$m$$$, we have to find how many tuples have mask $$$y$$$ induced by $$$x$$$.

Recall that multiplication of monomials in $$$\mathbb{Z}[x_0, \ldots, x_{k - 1}]$$$ with relations $$$x_i^2 = 1$$$ behaves the same way as xoring $$$k$$$-bit numbers. Further, WHT of an array $$$A = (a_0, \ldots, a_{2^k - 1})$$$ is the same as $$$k$$$-dimensional Fourier-transform of $$$P_A(x_0, \ldots, x_{k - 1}) = \sum_{i = 0}^{2^k - 1}a_i X(i)$$$, where $$$X(i)$$$ is the product of $$$x_j$$$ such that $$$j$$$-th bit is set in $$$i$$$. In simpler terms, we substitute all combinations $$$1$$$'s and $$$-1$$$'s into $$$P_A(\ldots)$$$ to obtain $$$2^k$$$ numbers; for the $$$j$$$-th number, the value of $$$x_i$$$ is $$$1$$$ if the $$$i$$$-th bit in $$$j$$$ is $$$0$$$, and $$$-1$$$ otherwise. Finally, recall that WHT is linear, and WHT of a product of two functions is the element-wise product of their WHT's (since WHT is basically FFT).

Consider a set of $$$k + m$$$ variables $$$x_0, \ldots, x_{k - 1}, y_0, \ldots, y_{m - 1}$$$. For a tuple $$$t_i = (t_{i, 0}, \ldots, t_{i, m - 1})$$$, consider a polynomial $$$Q_t(x_0, \ldots, x_{k - 1}, y_0, \ldots, y_{m - 1}) = \prod_{j = 0}^{m - 1}(1 + X(t_{i, j})y_j)$$$. What are the values of WHT of $$$Q_t$$$? Let's say that values of $$$x_i$$$ correspond to $$$k$$$ bits of a number $$$x$$$, and $$$y_j$$$ determine whether each index $$$j$$$ is included into the mask $$$y$$$. Then, one can observe that $$$1 + X(t_{i, j})y_j$$$ is equal to $$$2$$$ when $$$y_j$$$ matches the parity of the number of common bits of $$$x$$$ and $$$t_{i, j}$$$ (that is, $$$j$$$ is in the mask induced by $$$x$$$). Consequently, $$$Q(t)$$$ is equal to $$$2^m$$$ when $$$y$$$ is induced by $$$x$$$, and $$$0$$$ otherwise. By linearity, the WHT of $$$\sum_{i = 1}^n Q_{t_i}$$$ contains the exact values we wanted to obtain (after division by $$$2^m$$$).

how i can do c

would you translate following line into more easier english please? i trying to understand this line for like 30hours... but i cannot understand... 'the line starts from anoter perspective...' Now come the queries. Given a fixed value of w, we need to quickly compute (∑n=1i=1min{di,w})+w. From another perspective, this equals the sum of value times the number of occurrences, namely (∑wk=0k⋅count(k))+(∑∞k=w+1w⋅count(k))+w, where count(k) denotes the number of times that integer k occurs in d1…n−1.

why did the contest problem's rating not show in the problemset

Problem H. How do I prove $$$x-y-z+w=p$$$?

How to apply FFT in 1119E - Pavel and Triangles ? I saw FFT tag in this problem

Another approach for C: Note that the problem can be restricted to only needing to perform the operation on a $$$2 \times 2$$$ submatrix, as any instance of the operation on bigger submatrices can be reduced to some number of the $$$2 \times 2$$$ operations. Proof: if we denote performing the operation on a $$$2 \times 2$$$ submatrix by the coordinates of its top left cell, performing all operations $$$(i, j)$$$ where $$$i \in [x, x+n-1)$$$ and $$$j \in [y, y+m-1)$$$ is equivalent to performing a single operation on submatrix of size $$$n \times m$$$ with top-left corner $$$(x, y)$$$.

With the problem thus reduced, an easy greedy solution emerges: Compare every position in the two grids in reading order. When encountering any position where $$$A$$$ and $$$B$$$ differ, perform the operation on $$$A$$$ with top-left corner at that position. If that's not possible because the position is on the last column or row, the answer is No.

In problem E

Let's take 3 numbers i, j, k such that i < j < k.

Then why taking (i, k, k) and (j, j, j) is giving WA but taking (i, j, j) and (j, k, k) don't? 300iq

I came on a pilgrimage to the Holy Land. Please don't let IOI have problems with output only.

I came on a pilgrimage to the Holy Land. Please let me have a girlfriend who does problem solving.

Hmmm, problem F seems familiar ...

Is it just me, or the E problem is too easy to be E. I feel its more like Div2 B.

Problem E editorial has very few cases please create problems with 10000000 if else's branch statements so that all red coders also have fun like me. Editorial teaches me to think complicated now onwards I will try to think as complicated as possible