Блог пользователя Sumeet_Verma_is_my_god

Автор Sumeet_Verma_is_my_god, история, 3 года назад, По-английски

Hello community,

While solving the problem Tree Array from recent Codeforces Round 728 Div2(https://codeforces.me/contest/1541/problem/D)- I came up with the following solution which is failing on example test case 3.

The steps that I followed. 1) For each node r as root, the expected value of inversions can be expressed as p/q so the expected number of inversions considering all the n nodes as root r,one at a time, should be (p_1/q_1 + p_2/q_2 + p_3/q_3+ ...p_n/q_n) mod m=((p_1/q_1)%m +(p_2/q_2)%m + ...(p_n/q_n)%m)%m.

2) Now I observe that if I fix a node r as root, then for some pairs of elements a constant order of appearance is maintained across all the possible arrays that can be made by following the mentioned process and for some pairs of elements , their order of appearance across all the possible arrays is not fixed. Specifically, if we consider a pair of nodes (a,b) then a will always appear before b if b is in the subtree of a. And if the value of node a is greater than that of node b, then this inversion shall exist across all the possible arrays that can be made considering the node r as root as mentioned earlier. For other pairs, where one node is not in the subtree of other, in some cases, they will appear as inversions and in some cases, they will not. So ,for a particular node r as root, I count the number of pairs of elements which will always give an inversion across all the possible array combinations and mark that count as 'constant'. And I also count the number of pairs of nodes, for which no such fixed order is maintained and call that count as 'variable'. Suppose the value of 'variable' is x. We can visualize it as : there are x bits where each bit denotes a particular pair whose order is not fixed. So if the bit is set, it means that pair has occurred as an inversion otherwise not. If we consider all the values from 0 to ((2^x)-1), then for each such value, the number of set bits in that value + 'constant' will give us inversion count of one of the arrays that is possible if we take the node r as root as mentioned above and follow the process as mentioned in the question. So, we can easily obtain , for a particular node r, what are the possible inversion counts that we can get from all arrays formed by following that process as mentioned in the question and also how many times each such inversion value occurs while we are considering node r as root. Let's take the case of example 3 illustrated in the problem : Suppose if we fix 4 as root, then upon performing dfs we get 4,1,2,5,3. Now for each of the pairs (4,1),(4,2),(4,3),(4,5),(1,2),(1,3),(1,5),(2,5) the relative order of the first and second elements in the pair will always be maintained across all arrays we can get by following the process for 4 as root node, as we shall always the enter the node containing the first value of the pair before the node containing the other value because a node cannot be marked unless its parent has already been marked. Therefore the 'constant' has the value 3 here as among all the pairs mentioned earlier, in only the first 3 pairs do we have an inversion. For each of the pairs (2,3),(5,3), their relative order of appearance will not be fixed as for a particular pair, one of the nodes is not in the subtree of the other. So , here, the value of 'variable' is 2. Now, if we consider each of the values from 0 to 3 i.e (2^2-1), then 'constant' + number of set bits will give us the following : 3+0(when none of the bits is set),3+1(when one bit is set),3+2(when two bits are set) gives us 3,4,5 respectively which are all the possible values that inversion count can have when we consider all possible arrays for root 4 as node. The frequency of each of these values can be counted by finding how many times each count of set bits appears across all the values. So for the above example, from 0 to 4, two values has set bit count 1(2C1), one value has set bit count 2(2C2) and one value has set bit count 0(2C0). So 4 occurs twice as inversion count,3 occurs once as inversion count and 5 occurs once as inversion count. Therefore for node 4 as root node, we have p=4*2+3*1+5*1 and q=1+2+1=4. Therefore expected value of inversions for node 4 as root node will be p/q i.e 16/4=4. Similarly ,we can do for other nodes as roots.

Unfortunately, this solution is failing on the same test case with which I illustrated above. Can anyone of you kindly find any fallacy in this approach? It would be really of great help. The editorial explanation seems tough to understand and my logic feels very intuitive for me although the answer is coming wrong.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

The mistake in your thought process is that you consider all 'variable' bits to be equally likely, and equally likely to be true or false.

If you take the tree 2-3-1-4, and root it at 3, the probabiliy that you will pop 2 before you pop 4 is (1/2) + (1/2*1/2) (1/2 to pop it immediately, and then 1/2 to pop it if you pop 1 first instead).

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Apologies Sir, but why should the 'variable' bits not be equally likely and also not be equally likely to be true or false because as per question, marking any of the unmarked nodes that are connected to the set of marked nodes is equiprobable?

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Because a variable bit is something like 'I pop node number 4 before I pop node number 2', but node number 2 is connected to the set of marked nodes earlier than node number 4, and thus has more chances to be selected.

      A more extreme example: 1-root-?-?-?-?-?-?-?-2. When rooted at the root, can you see why it is much more likely that 1 will be popped before 2, than the other way around?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Well, the thing I figure out is that if from an lca, node a has more distance than node b, then node a is more likely to get popped earlier than node b. But the reason is very unclear to me. Am I missing some basic aspects of probability?

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Maybe. You can take the example above: 1-root-?-?-?-?-?-?-?-2, and I will pop nodes into the array by flipping a coin. If it lands heads, I will pop to the left, if it lands tails, I will pop to the right. The only way to pop 2 before 1 is by having the coin land tails 8 times in a row. If at any point it lands heads instead, I will pop 1 before 2.