Skip to main content

Posts

Showing posts from March 11, 2018

Trie problem in Codeforces Round #470

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.