QAQ

That's not KIND!

also, please update the colors, MikeMirzayanov.

Thanks, I'll do it tomorrow before the round.

nice observation, never thought about this.

Please return my passport. I couldn't buy beer for six months.

RIP passport...

Practice. Lots of it.

learn and practice every day

I think I will also reach pupil after this contest xd

Every tester says the same thing.

sad != said

There are literally thousands of blogs related to your question (Google?) and why are you asking this here in the contest announcement blog? :/

P.S: registered 7 months and still new KEKW

please anta.baka, neckbotov

Elimination Round will feature 7 problems, preliminary costs are 500 — 1000 — 1750 — 2000 — 2250 — 2750 — 3250.

Div. 2 will feature 6 problems, preliminary costs are 500 — 1000 — 1750 — 2000 — 2250 — 2750.

Div. 1 will feature 6 problems, preliminary costs are 750 — 1000 — 1250 — 1750 — 2250 — 3000.

good luck

just you.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

Same :((

This is why you are not improving. You should try C

No.

Tell me test 4 (after contest)

1
5 4
1 1
2 2
5 3
4 5

This is what i fixed to pass pretest 5 personally

try 6 5 1 2 2 3 3 1 5 6 6 5

Yes, initialise ans = m, for every cycle increment ans, for every rook at (i, i) decrement ans

Yep, I passed the pretest. Don't know about system test though.

Yeah, any rook on the diagonal contributes 0 to the answer.

Any rook not on the diagonal contributes 1 to the answer.

Additionally, any cycle contributes 1 to the answer.

This is optimal because moving a rook already on the diagonal off the diagonal is a waste of moves. Any rook not on the diagonal needs at least 1 move to get on the diagonal. And any cycle of $$$n$$$ pieces needs $$$n+1$$$ to resolve (you need to move a piece to a free column/row to remove the cycle, put $$$n-1$$$ pieces on the diagonal, then move back the original piece to the diagonal, for a total of $$$n+1$$$ moves)

ignore all points on diagonals. for every other point, connect every 2 sharing x or y.

for each connected component, check if at least 1 point can be moved to diagonal in 1 move.

if so, ans += no of points in the component. otherwise, ans += no of points in component + 1

Some hack tests:

5 4

1 2

2 1

4 5

5 4

Then the answer is 6.

For each rooks $$$(x, y)$$$, add an edge between $$$x$$$ and $$$y$$$.

For each connect component, if it is a tree, the answer of this component is the number of rooks. And if it is a cycle, the answer of this component is 1 + the number of rooks.

If I am right , how to compute? Using basis?

It turns into "compute probability that the resulting Grundy number is $$$x$$$, for each $$$x$$$. You can write a classic recurrent probability formula $$$p(x) = \frac{(x = 0)}{N+1} + \sum_{i=1}^N \frac{1}{N+1} p(x \oplus g_i)$$$ and turn it into Gaussian elimination since the Grundy numbers of vertices are $$$0 \le g_i \lt 512$$$ (approx. $$$\sqrt{M}$$$).

C is a graph problem.

How? :/

mine is also the same I don't know why it's getting the wrong answer

For each $$$(i,i)$$$, connect the rook in row $$$i$$$ with the rook in column $$$i$$$ with an edge. Discard self-loops. The resulting graph is a union of cycles and paths, the answer is number of vertices + number of cycles.

how does that make Div2B worse if lot of people solved it fast and you didn't

Same bruh.... it was only after I saw the brute force implementations that I realized that only a maximum of 2520 numbers needed to be checked. :") I should've moved on to C. :"(

The lcm of numbers from 1to9 is 2520 so it does not take more than 2520 for each test case if one does by simply increasing n and checking its fair or not

I was worried as well, but i've tried generating several cases and noticed that the number of iterations would always be pretty small, hence a brute force would pass.

LCM of first 9 natural numbers is 2520. So brute force will work.

Because Div-2 C seems more interesting.

I don't think it requires some advanced shit. I think it's just something simple that we did not quite figure out.

Congratulations for not copypasting modulos.

I should've used Zashikhin prime. I'm deeply sorry for your disappointment which I believe is immeasurable.

Why templates are evil Karma lol

Do you also ignore other parts of statements when solve? I wouldn't write it in this way if you weren't so aggressive. You should try to be more polite

I found C pretty easy. The last 2 signs obviously have to be + and -, but then for any string, we can always proceed from the last operation and "merge" a sign into the next sign if they're different, so that lets us turn any sequence of — to one -, any sequence of + (except the last, which is fine here) to +, and when we're left with +-+-+, that can be reduced to + as well. The rest is some careful implementation.

LCM of all digits from 1-9 is 2520. So max 2520 iterations

Numbers that divide all possible digits occur at most every 9! numbers, which is 300k

Yes https://codeforces.net/blog/entry/85746?#comment-735295

Suppose that all Grundy numbers are in the range $$$[0, 2^d)$$$. Then, let $$$c_i$$$ be the number of vertices with Grundy number $$$i$$$, by definition, all $$$c_i$$$'s are nonnegative integer and their sum is $$$n$$$. Let $$$p_{k, i}$$$ be the probability that after $$$k$$$ steps of the first type the current Grundy number is $$$i$$$ (including the fact that $$$k$$$ steps may not even happen, so $$$p_{k, i}$$$ go to zero as $$$k$$$ increases). Then, we have a very simple formula: $$$p_{0, 0} = 1$$$, $$$p_{0, i} = 0$$$ for $$$i \neq 0$$$ and $$$p_{k + 1, i} = \sum\limits_{j=0}^{2^d - 1} \dfrac{p_{k, i} c_{i \oplus j}}{n + 1}$$$.

In other words, $$$p_{k + 1} = (p_k \cdot c) / (n + 1)$$$, where by $$$\cdot$$$ I mean the Hadamard product of vectors. Because $$$p_0 = 1$$$, we get $$$p_k = c^k / (n + 1)^k$$$ (again, $$$c^k$$$ here means the $$$k$$$-th Hadamard power of $$$c$$$). Hence, the probability to end with Grundy number $$$0$$$ is the $$$0$$$-th coefficient of $$$\dfrac{1}{n+1} \sum\limits_{k=0}^{+\infty} \dfrac{c^k}{(n+1)^k}$$$. Indeed, to finish, we need to make $$$k$$$ steps of the first type (summands on the right) and then a step of the second type (multiplier on the left) for some $$$k$$$.

Now, we can find the Hadamard transform $$$H(c)$$$ of $$$c$$$. Because Hadamard transform is linear
($$$H(\alpha f + \beta g) = \alpha H(f) + \beta H(g)$$$, if $$$\alpha$$$ and $$$\beta$$$ are numbers) and multiplicative ($$$H(fg) = H(f) H(g)$$$), we can get the coefficients of $$$H \left (\dfrac{1}{n+1} \sum\limits_{k=0}^{+\infty} \dfrac{c^k}{(n+1)^k} \right)$$$ just by replacing each coefficient $$$x$$$ of $$$H(c)$$$ by $$$\dfrac{1}{n+1} \sum\limits_{k=0}^{+\infty} \dfrac{x^k}{(n+1)^k} = \dfrac{1}{n+1} \cdot \dfrac{1}{1 - x/(n+1)}$$$.

Finally, just apply inverse Hadamard transform to $$$H \left (\dfrac{1}{n+1} \sum\limits_{k=0}^{+\infty} \dfrac{c^k}{(n+1)^k} \right)$$$ that we just found. The probability of Bob's win is the $$$0$$$-th coefficent of the result.

There are no issues with division by $$$0$$$ here: because $$$c_i$$$'s are nonnegative integers with sum $$$n$$$, the coefficients of $$$H(c)$$$ are integers from the range $$$[-n, +n]$$$. Hence, $$$1 - x/(n+1)$$$ can't be $$$0$$$ modulo $$$998244353$$$, because otherwise $$$n + 1$$$ and $$$x$$$ are equal modulo $$$998244353$$$, meaning that $$$998244353 \leqslant 2n + 1$$$. In fact, this solution proves that there are no bad tests (tests, where the denominator of the answer is divisible by $$$998244353$$$): there are no bad tests exactly because there are no issues with division by $$$0$$$ in this solution.

This solution works in $$$O(n + d \cdot 2^d)$$$, if the input is just $$$n$$$ numbers from the range $$$[0, 2^d)$$$.