Divide by Zero 2018 and Codeforces Round #474

Recently I've been alternating my color between blue and purple. It is still sad for me to drop again to blue. Though this is a really nice round and thought-provoking one.

A) Check the string

I got hacked on this problem in the first half hour but only was able to find the actual problem in the middle of the contest. The bold words at the beginning of the problem description is just confusing. The problem is a little tricky.

My Code: Submission #37071314

B) Minimize the error

It doesn't whether we do operations on A or B. Every time we do operation is just decreasing the largest difference between number by one.

My Code: Submission #37058431

C) Sub-sequence Counting

This problem searches for a constructive algorithm. First note that a cluster of n same numbers can have 2^n -1 different sequence. Taking advantage of that, we can create different cluster (that are far away enough from each other) from largest to smallest and form the array in a way that is similar to converting decimal to binary.

My Code: Submission #37064865

D) Full Binary Tree Queries

I didn't try to solve the problem in the contest time since I found more people did problem F and the score of F is obviously larger. However, I found after contest that this problem is far easier than F, though some thought is needed.

The key observation of this problem is that, given a certain level, as long as we know the leftmost node, we know every other node's value at the same time (since we are just doing simple rotating. )

So, for the query 1 and 2, we can just update the leftmost node of the level(s). For query 3, we can calculate the position of the node in each level, compare it with the leftmost value, and then calculate the answer.

My Code: Submission #37088198

F) Pathwalks

This is the most time-consuming problem for me in the contest time, yet I didn't manage to solve that. In this problem, I use a similar approach as the O(nlogn) way to find longest increasing sub-sequence. Yet in this problem, I use a map instead of array to solve that. In map of each node, the key of each element is the ending value (edge length) and the value of that element is the length of the longest sequence ending with the edge of that length. So the basic idea is dynamic programming: scanning the input, for each line finding the largest ending value that is the smaller than the current edge length. Given the length of previous sequence is len, then the new sequence has a length is (len + 1).

After inserting the new value into the map, we need to look up for conflicts, or, say, erase the unnecessary elements in the map. For example, (4, 7) is apparently better than (5, 3) (first: ending value, second: sequence length)since any sequence that can choose (5, 3) can also choose (4, 7) to get a longer sequence. Besides that, there is also possibility that (4, 7) itself is an inferior choice if, for instance, (3, 9) is before it.
Then we should erase (4, 7).

The benefit of using map is that we can have a complexity O(logn). Don't worry about the complexity of deleting elements since we will delete at most m elements in the map. So the overall complexity is about O(m * logn).

My Code: Submission #37081304

Another approach to solve can be segment tree, which allows a neater implementation if we have the code template. Let's see if the official tutorial will explain that.

Thanks you guys for reading!
I am glad to hear any questions or suggestions!

By RobeZH