I could not solve the D. Perfect Security
in last night's codeforces contest.
In the morning I finally understood that the problem was actually a Trie problem. To solve the problem I used a structure name trie which has two trie type structure zero and one and a counter name cnt. For each trie node the cnt stores the number of zeros or ones in that node.
As problem says to minimum XOR values. So, the search operation traversing the same bit node ( bit 1 for one and 0 for zero trie type node ) of the Trie tree. If the search operation fail to found the same bit node with a positive counter values, then the operation check for reverse bit node with positive counter.
If the conditions are not satisfied, it stops the search operation. For Trie type node one turned on the return value bit position. value | = (1 << position) .
The search operation always reduce the traversing nodes counter by 1, So no need to delete operation for each keys.
In the morning I finally understood that the problem was actually a Trie problem. To solve the problem I used a structure name trie which has two trie type structure zero and one and a counter name cnt. For each trie node the cnt stores the number of zeros or ones in that node.
As problem says to minimum XOR values. So, the search operation traversing the same bit node ( bit 1 for one and 0 for zero trie type node ) of the Trie tree. If the search operation fail to found the same bit node with a positive counter values, then the operation check for reverse bit node with positive counter.
If the conditions are not satisfied, it stops the search operation. For Trie type node one turned on the return value bit position. value | = (1 << position) .
The search operation always reduce the traversing nodes counter by 1, So no need to delete operation for each keys.
Comments
Post a Comment