Inspirational's blog

Help in these Codenation hiring test problems
By Inspirational, 3 years ago, In English

1st problem :

2nd problem :

Link to these problems

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

Comments Comments (27)
| Write comment?
»
3 years 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

→ Reply
»
3 years 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$$$.

→ Reply
»
3 years ago, # |
  Vote: I like it -70 Vote: I do not like it

lol codenation

→ Reply
  • »
    »
    3 years 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!

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

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

    → Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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

      → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
        • »
          »
          »
          »
          »
          3 years 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.

          → Reply
    • »
      »
      »
      3 years 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)

      → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

does not work

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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

      → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
        • »
          »
          »
          »
          »
          3 years 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

          → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
3 years 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
→ Reply
  • »
    »
    3 years 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?

    → Reply
  • »
    »
    3 years 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.

    → Reply
  • »
    »
    3 years 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.

    → Reply
  • »
    »
    3 years 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

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

[redacted]

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please provide these types of questions more.

→ Reply