brucewayne123's blog

problem C APAC practice 2017
By brucewayne123, history, 8 years ago, In English

https://code.google.com/codejam/contest/5254486/dashboard#s=p2 i am unable to solve the large subtask of this problem.. i solved the small one using brute force.. please help me understand the logic behind this problem.. thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I will try to explain my approach which I used to solve it. Since, the three operations involved are all bitwise operations, the final result of each bit in the answer depends only on its own initial value and not on any other bit. So, we can try to find the probability of getting a '1' in each bit. Since, the maximum value can be 10**9, I used 32 bits.

Now, for finding the probability of getting a '1' in a particular bit, can be solved using DP. Lets have an array P[2] in which P[0] denotes the probability of the bit being 0 and P[1] denotes the probability of the bit being 1. Initially, before passing it to any of the machines, the values of P[0] & P[1] will either be 0.0 and 1.0 or 1.0 and 0.0 respectively based on whether the particular bit is 1 or 0 in the given value x. Now we run it through all the N machines.

Now to find P[0] and P[1] after we pass it through a machine, we need to use the same bit in 'k' for which we are finding the answer since only this bit determines the answer. Also, the machine can either do 'AND', 'OR' or 'XOR' operation and so using these information we can find the new P[0] and P[1] value after we pass through a single machine. We repeat this process for all N machines and for all 32 bits. So, the total complexity will be O(N).

After we find the individual probability of each bit, the answer will be sum of pow(2,i)*P[i][1] for 0≤i≤31. Here P[i][1] denotes probability of ith bit being '1'.

My C++ code

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

    thanks for such a nice and clear explanation.. :)

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

    Thanks for the explanation but i couldn't understand the login used inside for loop for N machines to calculate n0, n1; Thanks;

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Consider the following block in the code:

      if(bitk[i]){
	n0 += p[0] * (a/100.0);
	n1 += p[1] * (a/100.0);
 
	n1 += p[1] * (b/100.0) + p[0] * (b/100.0);
 
	n0 += p[1] * (c/100.0);
	n1 += p[0] * (c/100.0);
}

      If the current bit we are considering in 'k' is a '1' then this block will be executed. As we know there are 3 operations — AND, OR and XOR. When we AND '1' with 'x', it becomes 'x'. So, with probability p[0]*(a/100) '0' will become '0' itself and with probability p[1]*(a/100) '1' will become '1' itself.

      Next we will consider the OR operation with probability (b/100). When we OR '1' with 'x' we get '1'. So, the new probability of '1' will be (b/100)*(sum of p[0] and p[1]) since both '0' and '1' will result in '1' when ORed.

      Finally, when we XOR '1' with 'x' we get '1-x' and so n0 will be p[1]*(c/100) since '1' will change to '0' when we XOR it and vice versa for n1.

      With similar logic we do the else part when the current bit is not set in 'k' and we are done. Hope it is clear now.

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

very well explained! thanks a lot!

→ Reply