https://clist.by/ says that only 4 hours are left. That's a mistake, right?

Chmel_Tolstiy said that it will be possible after ending of qualification round. But it is strange that now it isn't possible...

Define $$$cnt_i$$$ — size of suffix consisting of only bits $$$1$$$

One condition in good matrix is $$$cnt_i \ge cnt_ {i-1}$$$ and other bits in row $$$i$$$ consist of bits $$$0$$$, for $$$2 \le i \le n$$$

Write DP $$$dp_{i,j,k}$$$ — minimum number of swaps if we make suffix $$$i$$$ of rows and suffix $$$j$$$ of columns in row $$$i$$$ consist of $$$1$$$ using $$$k$$$ bits from some positions.

So transiions:

• $$$dp[i][j][k]-(!a[i][j]) \Rightarrow dp[i][j + 1][k - 1]$$$

• $$$dp[i][j][k]+(m - j + 1) - sf[i-1][j] \Rightarrow dp[i - 1][j][k + (m - j + 1)]$$$, where $$$sf_{i, j}$$$ is number of bits $$$1$$$ in row $$$i$$$ on suffix $$$j$$$

Answer is $$$\min(dp_{i, j, sum})$$$ for all positions $$$(i; j)$$$ and sum bits of matrix $$$sum$$$

Observation: if we fold the matrix along the horizontal axis, all numbers in the same column became equal. For example for the matrix:

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

After folding

14 16 18 20
14 16 18 20

And if we fold along the horizontal axis again (just assuming, this is forbidden in the problem statement for this example), every numbers will be doubled.

And the same observation hold for the vertical axis. Also if there is a moment that we have already done 2 type of folds, all numbers will be the same.

The second observation is that we must fold along the bigger side. Suppose that side is $$$m$$$. Then we will have: $$$n \le m$$$, so $$$n \le \sqrt{n \times m} \le \sqrt {2^{30}} = 2^{15}$$$, which is small enough. That means after the first time folding, we actually can just maintain the set of the numbers in every columns. That is, we calculate them, put them into a set. While $$$m > n$$$, we double these numbers again and again, put them into the set. And finally we can fold along the other axis and all number will become one. Now is just looping until $$$n = m = 1$$$ and double this number again and again.

This algorithm works in $$$O(\min(n, m) \log n \log m)$$$

Problem have $$$O(log(n)+log(m))$$$ solution.

We have some numbers after each fold. We need add count of this numbers to the answer and subtract count of numbers that have already been added since the previous fold. It can be proved that it is necessary to subtract only numbers $$$\le n\cdot m$$$ (numbers that intersect with the original sequence). It can be done in $$$O(1)$$$ with simple math formulas.

Let's formalise reversing a path as changing each edge $$$p \rightarrow v$$$ to $$$q \rightarrow v$$$ and vice versa iff $$$v$$$ isn't on the path. Now it's simple casework with some efficient tree stuff.

• If one of the vertices $$$p,q$$$ coincides with $$$1,N$$$:
  • If the other two also coincide, the path doesn't change. W.l.o.g. now $$$p=1$$$.
  • If $$$q$$$ is on the path at distance $$$d$$$ from $$$1$$$, the length decreases by $$$d$$$ because the $$$q \rightarrow$$$ part of the path is changed to $$$1 \rightarrow$$$.
  • If $$$q$$$ isn't on the path, the length can only change if the edge $$$1 \rightarrow$$$ isn't between $$$1$$$ and $$$q$$$ — the whole path is extended and its length increases by the distance between $$$1$$$ and chosen $$$q$$$.
• Otherwise, exactly one of the vertices $$$p,q$$$ (w.l.o.g. $$$p$$$) must be inside the path between $$$1,N$$$. If both are inside the path, its length doesn't change; if neither's inside, then all edges of the path don't change.
• Let's say that we moved from $$$p$$$ towards $$$1$$$, again w.l.o.g., for $$$d_1$$$ edges, left the path before reaching $$$1$$$ and moved further for $$$d_2$$$ edges. Then the length of the path increases by $$$d_2-d_1$$$. (Only if $$$d_2 \gt 0$$$ and $$$d_1 \gt 0$$$, the length doesn't change otherwise.)
• If we instead reached $$$1$$$ and moved further for $$$d_2$$$ edges, the same rule applies except $$$d_1$$$ is uniquely defined as the distance of $$$1$$$ and $$$p$$$.

We can bruteforce all cases for one of $$$p,q$$$ coinciding with $$$1,N$$$. Now let's pick the vertex $$$v$$$ (possibly $$$1$$$ or $$$N$$$) where we left the path after moving from $$$p$$$ to $$$q$$$; we know $$$d_1$$$ and just need the sum of distances to all vertices in its (non-path) subtrees, with some multiplier since we have equivalent cases depending on which vertex is on the path and to which one we're moving. $$$O(N)$$$.

For mine, each tile can be rotated so for each tile I see the lexicographically minimum representation of it (there might be a better way). Like

WW

BB

can be

BW

BW

if it's rotated, but both tiles can be

BB

WW

which is the lexicographically minimum of them (going clockwise starting at upper left) so I use that to represent the first 2 tiles. I mapped the first 2 tiles to the third tile, and the third tile is mapped to the number of tiles that can be rotated to it.

Then, for each tile in the picture, I get how many tiles left I have that can be rotated to this tile, and if I run out of tiles that can be put there it's "No".

the official contest side says it will be 2:30 starts at 2:00am (-7 utc). Anyway, can't believe they haven't announced yet the schedule even before 48 hours ago. https://contest.yandex.ru/yacup/contest/29447/enter?lang=en

150-minutes contest will start at 9 a.m. UTC (12:00 Moscow time).

https://contest.yandex.ru/yacup/contest/29447/standings

I guess that's just a troll... There is a simple win strategy.

Thank you for feedback. Sorry, for these issues.

• will double check it in next time
• frustrated to make the same mistake twice
• first time report of such an issue (will double check it)
• found an error fast and tried to fix it fast, forgot in hurry to send a message

By the way hope it was quite good contest.

What's "best"? If the grader plays the winning side, of course it can beat you, and if the grader plays the losing side, all moves are losing unless you mess up.

[1,2]; [3,4]; ...; [2n-1,2n].

I consider, so beautiful.

In case of some issue with email contact we'll get in touch right here.

Eh, D is pretty much classical "store prefix hashes and prefix reverse hashes", I wouldn't call that very nice.

Ad C. Can you elaborate on that? IIRC Berlekamp-Massey guesses the linear reccurrence from given n points. I am convinced that for a given $$$A$$$ there will be a linear rec. But how to feed it with initial values?

My solution was like this:

Let

and

If you have

you can easily calculate the answer. Let us fix k. To calculate $f(k)$:

For $$$j=1,2,3,...,k$$$ we define

One can write matrix M s.t.

Now

and this can be easily calculated with matrix exp, if you extend the matrix and the vector to maintain also the sum of everything.

Also, this got WA, but I am pretty sure that I have a bug in implementation. So if anyone could provide a correct result for 500000000 50, or share a solution, so I can find an input to debug, I would appriciate that.

Can you please share your idea on problem A?

I was able to solve it with (I think) $$$O(L^2 \cdot n \cdot log(k))$$$ where $$$L \leq 20$$$. Using a trie with a map<int,int> for transitions in each node. It worked in ~1.8 seconds in C++, which seems too close to TL.

Check your spam and filters, I have mails with remainders as intended: