Typically our intention (at least mine :D) is to have as few hacks as possible. Unfortunately you guys don't always cooperate.

PikMike = Mikhail Pikliaev (so it's man).

Those of C were also weak. :|

When everyone just likes to downvote :V

I love contest too !!

good luck!

Good luck！

Im too

Now it comes true.

Wish you turn purple.

Good luck everyone!!

I wish to be yellow..

On the other hand, it is also possible to hurry up on Atcoder, and finish some minutes before the constest ends :)

why not delaying it for 30 mins like Atcoder? Many people would have more time to have a rest after agc.

No

No.

When I checked and unchecked the "show unofficial" then nothing really changed. So I also wonder like you.

No. They only show up in the "unofficial ranklist"

You can make an array "win[i]" which means that: win[i]=1: if n=i, Alice wins win[i]=0: if n=i, Bob wins

Make a program that generates the values of the array, and then find the pattern. You will easily find it.

Denote $$$f(l,r)=\sum\limits_{i=0}^{l}\binom{r}{i}$$$, Try to move from $$$(l,r)$$$ to $$$(l,r+1)$$$ and three other intervals in $$$O(1)$$$. Then apply Mo's algorithm to solve the problem in $$$O(n\sqrt{n})$$$.

There's a solution that runs in $$$O(N \log MOD)$$$, where the second factor comes from computing modular inverses in the process of building the choose function. I can't explain it particularly well, but the gist is that we define the same sum as Roundgod did and note that the required $$$l$$$ will generally decrease over time. Then, we can transition from $$$r$$$ to $$$r+1$$$ quickly (think about Pascal's triangle to see how this works) and can simply add combinations necessary to change $$$l$$$ in order to get the final answer for a certain $$$(l, r)$$$.

Let $$$s_i = T - \sum_{j \leq i} t_j$$$. If $$$\ell$$$ is the last crossword completed, at most $$$s_\ell$$$ of the crosswords up to $$$\ell$$$ can take an extra second, and at least $$$s_{\ell+1} + 1$$$ of the crosswords up to $$$\ell + 1$$$ must take an extra second.

The number of possibilities to check for any fixed $$$i$$$ is linear (the extra seconds up to $$$\ell$$$ and the extra seconds up to $$$\ell + 1$$$ differ by 0 or 1). Also, since $$$s_i$$$ is decreasing, the number of possibilities for all $$$i$$$ put together is still linear.

Well. I would have read question twice. If I read this.
Because this problem is standard nim game and expecting it as D would have been surprise for me.

This one?

No it's more similar! the same question in codeforces here

generator :)

Use lazy propagation and segment tree. That's the hint.

Make bipartite graph with vertices on the left corresponding to horizontal segments, and vertices to the right — to vertical ones. If two segments intersects, there is edge between corresponding vertices. Now lets iterate over all pairs of vertices on the left. Lets there are K common vertices on the right, then we need to add K * (K — 1) / 2 to the answer. Complexity is $$$O(N^3)$$$, but it is easy to see, that we can optimize this with bitsets, and overall complexity would be something like (N / 2) * (N / 4) * (N / 32), which seems to be fast enough (it is around 0.5 billion simple operarions)

if k%3==0: Bob wins if and only if (n%k)%3==0 && (n%(k+1))!=k.

k = 3 is not the only special case. Any k which satisfies k % 3 == 0 is a special case.

Thank you all for your input! It seems as though I was simplifying the problem too much.

What problem are you meaning?

The best way to solve D has already be given. Generate a few cases and observe the pattern. You can generate cases like this: A position i is marked 'W' if there is a winning strategy if it starts at i, otherwise it is marked 'L'. You can calculate all 'marks' as: if all positions that you can reach from here are marked 'W', then that means no matter what move you do, your opponent has a winning strategy so mark the current position 'L'. Otherwise, mark it 'W'.

I don't think so. Try updating it.

It is strange. To me it says 50 years too. To a friend of mine it says 11 months.

To me it says 11 months ago

Maybe you should place sync_with_stdio just before you start input/output else it will mess up because of synchronization?

you have written IOS after (cin >> t ) . This is happens because of that. You should write IOS before taking all input.

The thing is, you need to consider all rows that have least tiles, because your program chooses the first one and that might not be optimal since there could be another row that could have the same amount of white paint, but that other row might intersect with another column,with minimum white tiles, on a white cell which means that by painting that white cell on which they intersect, you reduce the amount of white paint on both the column and the row with the least amount of white paint. Hope I helped.

That's only a part of it. The rest is snipped off and replaced with ... at the end which happens to look like part of the grid.

No; hacking will not affect your official ranking in an educational round.

No points, just satisfaction xD. (In educational rounds)

everyone is official and it is rated for div2 only

It doesn't appear there until the ratings have been updated.

I didnt solve it so maybe I am not objective, but its nothing special. Still, of course its better than theoretical game theory problems which involve grundy numbers or something. I dont think anyone loves that.

Sorry guys, I dont understand why you are downvoting me. Is it a lot of bots from HubyBee?

Fix $$$k$$$, and for each $$$m<=n$$$, $$$f(m)=A$$$ if Alice will win if the strip were to begin at $$$m$$$, and $$$B$$$ otherwise. Obviously $$$f(0)=B$$$ and for the rest, $$$f(m)=A$$$ if and only if exactly one of $$$f(m-1), f(m-2), f(m-k)$$$ is equal to $$$B$$$. (For the rest of the proof we will not deal with the size of $$$m$$$ with respect to 1, 2, $$$k$$$, the proof will still be the same with all those constraints added, just a bit messy).

We shall proceed by inducing on $$$m$$$ in each case of whether $$$3\mid k$$$ or otherwise. In either case, we observe that $$$f(m)=B$$$ means $$$f(m+1)=f(m+2)=A$$$ (reason being explained above). We claim that for the first case, $$$f(m)=B$$$ iff $$$3\mid m$$$, with base case $$$m=0$$$ explained. Now for inductive step, if $$$3\nmid m$$$ then either $$$3\mid m-1$$$ or $$$3\mid m-2$$$ and therefore $$$f(m-1)=B$$$ or $$$f(m-2)=B$$$, which follows $$$f(m)=A$$$. Otherwise $$$3\mid m$$$ and we notice that neither of $$$m-1, m-2, m-k$$$ are divisible by 3, and therefore by induction hypothesis $$$f(m-1), f(m-2), f(m-k)$$$ are all $$$A$$$, so $$$f(m)$$$ must be $$$B$$$.

Now $$$3\mid k$$$ is tricky: the first $$$k-1$$$ values follow from the previous case, but $$$f(k)=A$$$. We, instead, consider modulo $$$k+1$$$ and the first $$$k+1$$$ values (0, 1, ..., $$$k$$$) should be clear. Now let $$$m\ge k + 1$$$, which means we should consider $$$f(m-1), f(m-2), f(m-k)$$$. For clarity, consider $$$m_0$$$ as the remainder of $$$m$$$ when divided by $$$k$$$. The induction claim, as suggested by others, is that $$$f(m)=B$$$ if and only if $$$m_0=0, 3, \cdots , k - 3$$$. We have the following cases:

$$$m_0=0$$$, and $$$m-1, m-2, m-k$$$ are congruent to $$$k, k-1, 1$$$ modulo $$$k+1$$$, and by induction hypothesis it follows that all $$$f(m-1), f(m-2), f(m-k)$$$ are all $$$A$$$ so $$$f(m)=B$$$.

$$$m_0=1, 2, k$$$: obvious from the previous case.

The rest of the cases: since $$$3\le m_0 < k$$$, $$$m-1, m-2, m-k$$$ are congruent to $$$m_0-1, m_0-2, m_0+1$$$ modulo $$$k+1$$$. If $$$3\nmid m_0$$$ then either $$$m_0-1$$$ or $$$m_0-2$$$ is divisible by 3 and less than $$$k$$$, so either $$$f(m_0-1), f(m_0-2)$$$ is $$$B$$$ and this case is done. Otherwise, $$$f(m_0-1)$$$ and $$$f(m_0-2)$$$ are both $$$A$$$ so we only consider the last one, $$$f(m_0+1)$$$, which is also equal to $$$A$$$ since $$$3\nmid m_0+1$$$. This concludes the proof.

Sorry for the poor organization, I am writing in a hurry (though it's fun to do so :P )

I think he should be banned.what do you think?

You can solve it in O(K*(K-1)/2) bitset operations, where K = min(horizontal, vertical) so in the worst case, K = N/2. Considering each AND operation runs in N/64 more or less, it's a good complexity ~ 250.000.000 operations which run in aprox 1600 ms

Think only about i-1 and i-2. A means Alice wins and B means Bob wins. This is the winning pattern, starting from n==0: BAABAABAABAABAA. Basically, if pos%3==0 the ans is Bob. This happens because you only reach positions that Alice wins form this pos%3==0 positions. When k%3==0, the lowest position that change is pos==k, and it is easy to see the reason why ( you cant go to pos-k because it is < 0). Then, a part of the winning pattern will become: AAApos, id of pos == k+1. So both pos-1 and ipos-2 will reach A, so the ans should be B. And we know that pos-k changed from B to A. So the unique ans to pos is B now. This is the same as restarting the winning pattern, so, this winning pattern in the range [0, k] will be the same as [k+1, 2*k] and so on. I know that this solution is not rigorous mathematical, but I hope it will help you!

Imagine you are in Cell(x, y), now you have to make sure all cells in this row and column must be black. This means some white cells need to be painted. Now how many white cells are to painted? For this, just store the count of white cells in each row and column. Now if at (x, y), cells to be painted, X (lets say) =(White Cells in Row 'x' + white cells in Column 'y'); just make sure if current cell is white, you subtract 1 from X because it will be counted in both row as well as column. Just find minimum of 'X' from all cells in O(n*m); Hope it helps.

I was thinking about it too, but I coudln't find any solution.

what do you mean ? don't you want to input the grid that's o(nm)

I am not able to understand why you people are downvoting. Is the solution not clear to you/ Is there mistake somewhere??

You can point it out if there is any.