As a way to solve Problem E from ZeptoLab Code Rush 2014, I decided to implement Treap for the first time. Treap is a randomized binary search tree that the maximum height of the tree is about O(log n) (similar to AVL tree). It’s easier to implement than a normal AVL tree. Why do I have to implement it? I need to perform these operations in O(log n): Add, Remove, Find the sum of the k smallest elements. My implementation was added here. Note that this problem E can also be solved by other data structures: Binary Indexed Tree, Cartesian... [Read More]
I’m skipping Division 1 P300, because it can be solvable after carefully thinking/coding. Division 1 P450 I would like to introduce a technique used to solve this problem. The technique is to apply a transformation (rotate the graph 45-degree clockwise) to the original graph. With the original graph, if we are at (0, 0) we can move to get any points that drop from the area above the blue lines. After applying the transformation, the claim stays true. So what is the maximum number of points we can get? Of course, we can only get the points that are in... [Read More]
I have heard about this technique so many times recently, but I haven’t gotten a chance to use it during a programming contest. I think this technique is very interesting and pretty cool, so I decide to implement it to solve a problem, QTREE. The problem is that you’re given a tree of N nodes and a number of operations. Each query can be one of the following: CHANGE a b: update the cost of the edge a to b QUERY a b: print the maximum edge cost on the path from a to b So you’re asked to perform... [Read More]
Here is my analysis of this contest. Problem A I will just give a hint for A. The idea is that disconnecting the graph requires cutting all the edges. Cutting an edge e(v1, v2) can cost either v1.value or v2.value. Of course, we want the cost to be the lower one, and we can always force it by some cutting sequence. Problem B This problem is very interesting for me. It took me a large amount of time in order to solve it. So suppose that x is the minimum number of animals among the routes areas from p to... [Read More]
Yesterday I left the post with 2 GCJ14 Round 2 unsolved problems. Here are the solutions to those problems Problem C: Don’t Break The Nile: as I said, we can use Maximum flow algorithm to solve this problem, but actually we don’t have to run the full straightforward MaxFlow algorithm. We can apply the idea of Max-flow = Min-cut to solve this problem. A way that we can find the min-cut to the graph is to draw the min-cut curve going from the west to the east side. Consider the following picture (from the sample test): The purple line is... [Read More]
Today GCJ 2014 Round 2 contains 4 problems. The top 500 contestants will advance to Round 3. In this round, at least 50 points with small penalty time are required to pass this round. And yeah! I got 413rd ranking. This was my first time that I got a GCJ t-shirt and advanced to Round 3. let’s talk about the problems. The first problem (A: Data Packing): given N files with their capacities and disc capacity, what is the minimum number of discs are required to store all the files with 2 conditions: A disc can contain only at most... [Read More]
Today I just learned a new amazing algorithm. It’s called Manacher’s algorithm, the algorithm that finds the longest palindromic substring in linear time. Previously, I never thought that it can be done faster than O(N^2) time complexity (by dynamic programming). I felt really impressive after reading this blog and knew that this algorithm was found in 1975 :) So I wanna share it HERE.
This morning, I participated in Codeforces Round #189. It’s an online programming contest for Division 1 users as usual. This contest seems crucial for me, because if I didn’t do well enough, my rating would decrease and it can cause me to fall into Division 2 which I really didn’t want it obviously. I’d been going back and forth between Division 1 and 2 for a while until I got improved and my skill now is just over Division 2. So I’ve managed to stay in Division 1 for quite a long time (I guess) and I’m trying to turn... [Read More]