Codeforces Round #169 — Unofficial Editorial

I really enjoyed this round, the tasks required more thinking than coding and that's always a good thing. I'd like to share my solutions to the problems here. Hope you enjoy them!

A — Lunch Rush

This problem was the easiest one in the competition, and the solution is just the simple implementation of what is given in the task statement — calculate the fun level for each restaurant, and output the maximal value.

My code: http://www.codeforces.com/contest/276/submission/3180631

Time complexity: O(n)

Memory complexity: O(1).

B — Little Girl and Game

The key thing to notice in this task is, if we can arrange the characters of the string we have into a palindrome, then there can be at most one character with an odd amount of occurences. This easily gives us the answer: if there are <= 1 characters with an odd amount of occurences in the initial string, then the winner is the first player. Otherwise, the answer is dependant on whether the amount of characters with odd amounts of occurences is even or odd; if it's even then the second player wins, otherwise the first player wins (since the one who is forced to get this amount to one first is going to lose).

My code: http://www.codeforces.com/contest/276/submission/3181475

Time complexity: O(n)

Memory complexity: O(n).

C — Little Girl and Maximum Sum

In this problem the sensible thing to do is to count the amount of times we are going to add some index of this sequence; then the maximal number gets assigned to the index that is added the most, and so on. In order to count the amount of times we referenced each index, we can use the Binary Indexed Tree structure to store cumulative sums with update and retreival times of O(log n) (a great tutorial for this structure can be found here: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees).

My code: http://www.codeforces.com/contest/276/submission/3182445

Time complexity: O(n log n)

Memory complexity: O(n).

D — Little Girl and Maximum XOR

A XOR of two numbers has the value of the i-th bit set to 1 if and only if their values on this bit differ (i.e. one is zero and the other is one). We can be certain that we can pick two numbers with differing bits on the i-th position and conform to the rest of our solution, if the difference between R and L is greater than or equal to 2^i (because the zeroth bit changes state every 2^0 values, the first one every 2^1 values and so on). When this difference is lesser than 2^i, we use another key observation: within one of those blocks of length 2^i, the sequences of values where the i-th bit is zero and where it is one are contiguous; i.e. we just have to check whether the i-th bit of R differs from the i-th bit of L, and then we know whether or not they're in the same subsequence with respect to that bit. If they are not, we can add 2^i to our solution. We carry on until 2^i is lesser than or equal to R.

My code: http://www.codeforces.com/contest/276/submission/3183526

Time complexity: O(log n)

Memory complexity: O(1).

E — Little Girl and Problem on Trees

A key observation on this problem is that when we perform the operation 0 on any node which isn't the root, we increase the nodes at [depth[X] — d .. depth[X] + d] along its chain. Of course, if depth[X] <= d, this will also affect other chains, namely, all depths lesser than d — depth[X] + 1 will be increased as well. To handle this we can store information about each chain in a BIT structure — one for each chain (this structure was mentioned already in solution for task C), and also store information about the global depth updates in another BIT. When we query a particular node, we simply add up the BIT value of its relevant chain and of its depth.

My code: http://www.codeforces.com/contest/276/submission/3187958

Time complexity: O(q log n)

Memory complexity: O(n).