Inspirational's blog

By Inspirational, 11 days ago, In English

1st problem :

2nd problem :

Link to these problems

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
10 days ago, # |
  Vote: I like it -13 Vote: I do not like it

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

»
10 days ago, # |
Rev. 3   Vote: I like it -29 Vote: I do not like it

$$$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$$$.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    It won't work if the matrix is->

    4

    2

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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$$$...

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
10 days ago, # |
  Vote: I like it -70 Vote: I do not like it

lol codenation

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
10 days ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

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.

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
10 days ago, # |
Rev. 4   Vote: I like it +5 Vote: I do not like it

does not work

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, 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 -

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

    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.

    • »
      »
      »
      10 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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

»
10 days ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

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

Disclaimer
  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

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

»
9 days ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

[redacted]