# | User | Rating |
---|---|---|

1 | tourist | 3851 |

2 | jiangly | 3634 |

3 | Um_nik | 3539 |

4 | slime | 3498 |

5 | ksun48 | 3493 |

6 | djq_cpp | 3486 |

7 | maroonrk | 3471 |

8 | MiracleFaFa | 3466 |

9 | Radewoosh | 3442 |

10 | Petr | 3426 |

# | User | Contrib. |
---|---|---|

1 | -is-this-fft- | 183 |

2 | awoo | 181 |

3 | YouKn0wWho | 177 |

4 | Um_nik | 175 |

5 | dario2994 | 172 |

6 | Monogon | 170 |

6 | adamant | 170 |

8 | maroonrk | 169 |

9 | errorgorn | 166 |

10 | antontrygubO_o | 165 |

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/17/2022 13:40:39 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

well, not so "Insipirational" of you, asking solution in here. lel ps- see their editorial o_O

What the. Since when did hiring tests start giving out editorials?? lmao

correct! lmao

$$$first$$$ $$$problem$$$ — if a player can choose any subset then the the most optimall way is too choose the whole row and replace it by it's divisor : $$$1$$$ then a player can't choose this row cos the divisors of $$$1$$$ are only $$$[1]$$$ and the statement says that : $$$A$$$ $$$proper$$$ $$$diviso$$$r $$$of$$$ $$$a$$$ $$$number$$$ $$$N$$$ $$$is$$$ $$$any$$$ $$$divisor$$$ $$$of$$$ $$$N,$$$ $$$not$$$ $$$equal$$$ $$$to$$$ $$$N.$$$ so we can't choose that row once again. Therefore we only need to check if the number of rows is odd : if it's , then player 1 win, otherwise player 2 win.

UPD : Oh what i wrote doesn't mean what i wanted to say... — $$$Replace$$$ $$$every$$$ $$$row$$$ $$$with$$$ $$$number$$$ $$$1$$$ $$$(which$$$ $$$is$$$ $$$a$$$ $$$divisor$$$ $$$of$$$ $$$any$$$ $$$number)$$$ $$$and$$$ $$$then$$$ $$$a$$$ $$$player$$$ $$$which's$$$ $$$turn$$$ $$$can't$$$ $$$choose$$$ $$$that$$$ $$$row$$$.

It won't work if the matrix is->

4

2

Why ? If we choose the subset $$$[4]$$$ and we change it to a divisor of $$$4$$$ different than $$$4$$$ which can be $$$1$$$ and the same with $$$2$$$...

Process : player 1 choose the first subset and replace it by $$$[1]$$$ , now player 2 can't choose that row : player two choose second row and replace it by $$$[1]$$$, player 1 now can't choose first row or the second so player 2 wins.

Player 1 can win by changing the element in 1st row to 2. Now, player 2 have to change either 1st row or 2nd row. After that, player 1 will pick the remaining row and win.

lol codenation

Time to show some unity, codeforces! The comment is at -69 upvotes. Let us keep it that way!

shame on you.... if you are red so you will joke everywhere ?

lol

Here is my solution to problem 1: We can do two reductions to make this problem become a game of NIM (see more in here, but i'll explain it later).

Let's define f(n) the maximum number of times you can do the operation of replacing n with a proper divisor of it. For the number 24 for example, which is 2^3*3^1, f(24) = 4. Notice that we can change 24 to a number x such that f(x) can be either 3 (8 for example), 2 (4 for example), 1 (2 for example) and 0 (that number would be 1). As this tells us more about the problem than the number in question than the actual number, let's use f(A[i][j]) instead of A[i][j] (we can find it using the sieve of erastothenes in O(10^6*log(10^6)) + N*M).

Since we can use any subset on a row, let's use the same idea again. We define g(A[i]) the maximum number of operations we can do in a row, and from a g(A[i]) we can reduce it to a g(x) such that g(x) can be equal to any integer from 0 to g(A[i]) — 1.

This is exactly NIM. We have many piles of rocks (in this cases, the piles are the rows and the ammount of rocks are the g(A[i])) that we can take any non zero ammount of rocks out of and the loser is the one that can't do any moves anymore. For a game of nim, if someone starts the game in such a way that the bitwise XOR of all piles is 0, they lose. Otherwise, they win. You can read about the proof here, but the idea is that from a state where the bitwise XOR is different from 0, you can make the bitwise XOR 0, but from XOR = 0 you can only make XOR different from 0, and since the losing state has bitwise XOR = 0, then we can keep taking rocks out in a way that guarantees a win.

Take the bitwise xor of all g(A[i]) and print 1 or 2 accordingly.

Why do we have to take f(A[i][j]). I mean why is it not optimal to pick a subset and just change all numbers to 1. For ex., lets suppose i-th row had a total of m elements > 1, i.e m numbers which can be changed to 1. So the problem again reduces to NIM except the 1st step.

For each row i, there are B[i] number of numbers which we can be reduced to 1. Hence rows are piles and B[i] are number of rocks.

Let us suppose one of row is [4,6,8] then the max number of operations which I can apply on this row is 2+2+3. So for converting it to NIM we have to use f(A[i][j]) and take sum of all f(x) in the row

Exactly my question, Why do we have to consider f(x). Could you provide a little intuition behind it? I'm having a hard time figuring out the intuition.

we would have taken count of numbers >1 in a row if we are bound to convert a number to 1 in one go. But this is not the case here. Here we can reduce a number(by applying operation) f(num) times.

Consider this case: {4,2,1} (assume they are 3 different rows with 1 column, so you can only change one at a time). If we apply your idea your opponent will have {1,2,1} or {4,1,1}, which are both losing positions.

Try to work out some cases if you need more intuition, it's pretty fun and this is not the first problem is saw that uses similar ideas (not talking about the bitwise xor)

Okay. Yes, it makes sense.Thank you for clearing that up!

does not workNo, these DP transitions will give wrong answer, as while calculating DP you are only looking at the subtree which will not work in this case. For example, look at this test case and run your DP on this -

Optimal answer should be 3. But your DP will never give 3. I was also doing the same mistake of using those DP states as you did.

Ok so i did a sketch of this test case and correct me if im wrong, but not only there's a cycle but doing it on 3 seems pretty impossible.

Here is it

EDIT: also note that we're compressing the tree, so the only way for the subtrees to affect each other is through their parent, which they would need some massively suboptimal stuff to get to anyways. Maybe that's your point of concern

cycle? with 14 edges seriously? Also this test case is the 3rd test case of 734E - Anton and Tree, which is the same problem as above, and you can go there and check answer is 3.

yeah, i fucked up. Will try to come up with the right idea.

The cycle thing is because it's 5 AM here so im not at my best

After component compression, the result graph should be a bi-colored tree coloured in bipartite pattern.

We claim that the answer should be $$$\lceil D/2 \rceil$$$, where $$$D$$$ is the diameter of the tree.

Considering the diameter. Initially all edges connect different coloured vertices, and each operation at most removes 2 such edges. Moreover, if we root the tree at the centre of diameter and repeatedly operate on the root, we can reach this answer.

I think the component compression can be done in $$$O(N)$$$, and finding diameter cost another $$$O(N)$$$ time. So this solution works in $$$O(N)$$$.

Additionally, it seems that there's no need to compress the connected components: we can simply find the path with most different coloured edges. This can be done with DP in $$$O(N)$$$ time.

The first question is a direct application of

Nims Theorem. Consider each row as a pile of stones and the number of stones in that pile is equal to the sum of number of times you can replace each number of that row with a proper divisor.The second question is same as 734E - Anton and Tree

DisclaimerI had cleared this round previous year but failed to get the offer :(

Why did not they take you despite clearing the test and where do you work now?

Actually, the 2nd question is quite different than what you mentioned. In the codenation version they are changing the node values online for i = 1 to n. So, a node value changed before will affect if a later value will be changed or not, even if the path had same values of all nodes before the flip operation was applied.

It might be the case that they copied the problem, changed the problem statements(so it will not be searchable) and made logical mistake in copying.

Have you approached the second question using DP on trees on the compressed tree ? If yes, please share your approach for the same. As looking into the editorial of the problem, they have done using some pretty clever observation on the diameter which is kinda hard to realise. If you have done using DP, please share your approach.

Maybe codenation thought it would be difficult for you to work from Antarctica. XD

I had heard that most of the companies ask questions which are based at most on Codeforces D but Codenation's level is one above?

[redacted]

Please provide these types of questions more.

more problems please