I was wondering about the problem C from Div 1 of Codeforces Round #177 (Problem link: 288C - Polo the Penguin and XOR operation). Why does the greedy solution work?
The greedy solution is as follows:
- For every index 'i' from 0 to N, pick an unused number 'n' such that i^n (i xor n) is maximum.
I know it works because I got accepted with that. I was hoping someone could prove it.
in XOR operation there is three cases:
1) 1 xor 1 = 0
2) 0 xor 1 = 1
3) 0 xor 0 = 0
to get accepted you should avoid to make (case 1) because it reduces the final sum because it deletes both 1's bits the other two cases don't reduce the final sum.
in other words you must choose a permutation such that for each i (0<= i <=n) i+Pi == i xor Pi
when you avoid making (case 1) the answer is always: 1+2+3 ... + n + 1+2+3 .... n =n*(n+1)/2 + n*(n+1)/2 = n*(n+1)
prove:
in all numbers no 1's bit have changed to 0'bit so the answer equal to the sum of all numbers that used in a XOR operation (i.e 0,1,2,3,4 ... n and the numbers of the permutation)
notice that: let A and B be two integers (A xor B) always don't exceed A+B.
Nice explanation. This proves why the answer is N*(N+1).
But I still wonder why greedy works. If the solution is to avoid case 1, then for i = 0, I could very well choose just any 'k' from 1 to N, but in the greedy solution, P[0] = N always.
What I'm saying, I'd like a proof that with the greedy solution, there will never be a case for a certain index 'i' that there will be impossible to avoid case 1 with the remaining numbers.
I don't know why a greedy solution don't lead in some step that impossible to avoid case 1 with remaining numbers.
but logically, you should choose such two numbers that saves as many 1bits as possible in one XOR operation.
in other words, for each k from log(n)+1 to 0 you should find all pairs of numbers (a,b) such that a xor b = 111..11 (k ones) (this is in binary representation) , this way it is always possible to avoid case 1 , it's logical way to save as many 1bit as possible in each XOR operation ,but I don't have the prove.
Let's find for every number from n to 0 the partner number, so xor of pair is maximum. For this invert bits in number. Number with inverted bits less than number with uninverted bits, because the head bit inverted. For example pair of 4 is 3 (001 -> 110) and pair of 5 is 2 (101 -> 010). Xor of the pair = 2 ^ (number of head bit in uninverted number) — 1. When we find a partner of the number we won't consider it in the future. I think, code tell more: 3468570
Why does it work? Obviously n ^ pair(n) >= k ^ pair(k) (where n > k). So, when we consider numbers from n to 0, on every steps we get maximum xor, that we can add to the answer.
I appologies for poor knowledge of english language.
This was the first solution I thought for this problem, but I quickly discarded it as being wrong, because you'll get duplicates for not considering more significant bits.
For example, the partner number for 4 is 3 (100 -> 011) and the partner number for 12 is also 3 (1100 -> 0011). One solution to this problem that came to mind was "OK, let's consider all bits from 2^0 to 2^(log)N for every number". But again, it was wrong, because if you're working, for example, with N = 8, then the partner number for 2 is 13 (0010 -> 1101), which is > N, so I thought this solution was never gonna work.
And it looks like by not considering an index when it already had a pair assigned, you avoided the problem of getting duplicates and magically ended up with a perfect match for every value of N. I'm still wondering how is it you never get duplicates...
Anyway, good job ;)
Note: This operation comes native in C++ and other languages. It's an operator called "bitwise complement". In C++, it's '~', though you'll then have to get rid of the leftmost bits you don't want by doing a "bitwise and" with (2^log(N) — 1).