Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/kurniady/kurniady.net/wp-includes/formatting.php on line 74
Warning: Illegal string offset 'before_widget' in /home/kurniady/kurniady.net/wp-content/plugins/mycustomwidget/my_custom_widget.php on line 812
Warning: Illegal string offset 'after_widget' in /home/kurniady/kurniady.net/wp-content/plugins/mycustomwidget/my_custom_widget.php on line 813
Warning: Illegal string offset 'before_title' in /home/kurniady/kurniady.net/wp-content/plugins/mycustomwidget/my_custom_widget.php on line 814
Warning: Illegal string offset 'after_title' in /home/kurniady/kurniady.net/wp-content/plugins/mycustomwidget/my_custom_widget.php on line 815
Deprecated: Function eregi_replace() is deprecated in /home/kurniady/kurniady.net/wp-content/plugins/mycustomwidget/my_custom_widget.php on line 1081
In this page I will try to explain the solutions I made during the competition for the problems that I solved, and some ideas I got about the problems that I do not solve. Please download and view the problem statements (available from Felix Halim’s site) before reading, otherwise you may get lost on what I am talking about. I will explain it by the order we got it accepted.
The first problem to solve is problem A. The problem can be simplified as this “Given a list, return the least number of swaps needed to make it an ordered list”. I remembered a similar problem in Balkan Olympiad in Informatics (BOI) 2004 or 2005 (not sure which year), but that problem allows repeated characters (which makes it far far more difficult than this one) and was to be solved with Euler Path algorithm (Fleury’s algorithm). It’s not the case with this problem though… My idea was actually very simple, and I was not sure about its correctness at the time of competition (although I am, now).
- To know the real order, we have to copy the list and sort it (which is easy with STL sort algorithm)
- We need a function to find the intended location of an (fortunately, unique) element. I implemented a simple linear-searching method with complexity O(N). Actually, we can precompute the location of each character and store it in a map, which makes the function call O(1) and the precomputation should run in O(N).
- For each misplaced characters, intuitively it must be swapped into its correct location.
- Thus, we just loop from left to right, and swap the misplaced characters accordingly.
Here is the code I made during the competition. It got Accepted on the first try. The complexity is O(N^2 + N log N).
A.cpp (CPP 1KB)
This problem is actually more straightforward than problem A. The solution is nothing but to simulate what the problem statement explained. We created a two-dimensional array to simulate the encryption process and just print out by column in the correct order.
Here is the code I made during the competition, accepted on the first try as well. I believe the complexity is O(N^2).
D.cpp (C++ 1KB)
Intuitively, this problem can be solved in O(N^4) with simple bruteforce on the boolean matrix. This solution will not be sufficient though, because although only 100 million iterations is needed per test case (which should run below 1 second), the input may contain several test cases. In fact, at the beginning we are thinking of submitting the bruteforce version first, but we did not because we saw team NoMoreAC have a rejected run (red mark in the scoreboard) for this problem.
The idea for the O(N^3) solution is as follow.
- For each row, we create a set that contains the column number of the pillars in that row.
- Then, for each pair of rows, we do a set intersection on the column numbers. The STL set_intersection algorithm do just that, in O(N).
- A possible rectangle can be formed when both rows have more than one columns with a pillar in common. The number of rectangles can be calculated as K*(K-1)/2 for each pair, where K is the number of elements in the intersection.
Here is the code, with complexity O(N^3).
G.cpp (C++ 1KB)
Problem F was actually just another Dijkstra-or-A* style of problem, just like problem E - Taxi in the preliminary round. The only hard part is about how to determine the time required to travel from one node to the other, given the edge’s rush hour, required time, and starting time. I implemented some recursion in this function, to help simplify the conditionals. Altogether, the algorithm should run in approximately O(E log E) where E is the number of edges. The code can be found below.
F.cpp (C++ 3KB)
I was lucky. This problem is can be solved with Tree-DP, which I have mastered since 2005’s IOI. This problem is can be solved with a Tree-DP approach simpler than problem Rivers in IOI 2005, just about the same difficulty with problem I of ACM ICPC Regional - Kaohsiung Site 2006. The idea is :
- Represent the tree as some edge list, bidirectional.
- Do the recursion taking any node in the tree as parent.
- In any node, there is just three kind of return value :
- The number of nodes from this node downwards.
- The minimum total cost if the median is located in this node downwards.
- The minimum total cost if the median is not located in this node downwards.
The solution in code can be seen below. The complexity is O(N).
Hb.cpp (C++ 2KB)
For you who are not used to this kind of Tree-DP, I suggest thinking about the solution for the 1-dimensional subcase first (i.e. if the tree is linear), then expand to the tree version. The solution of the judges are a little bit different, just similar to the one explained by Felix Halim.
We are very lucky to have this problem accepted. It seems that our algorithm contains a lot of prunning that luckily have passed the judges’ test cases. The idea is very simple :
- Think of this formula : GCD(N!, k) = GCD(N,k) * GCD((N-1)!, k/GCD(N,k)) and just break when k have reached 1.
- Merely based on that formula, we coded a very short solution. However, it exceeds the time limit (as we tried in the first submission) when K is a prime number.
- Thus, I tried this prunning : if k is a prime (check with an efficient method of using precomputed prime list below sqrt(k)) then, there is only two possible outputs : k, if N>=k, and 1, if N<k
The code can be found below.
Bb.cpp (C++ 2KB)
Later on I found that I was lucky : there was no input which have k as a big prime number multiplied by some small numbers (such as 2). The solution above will exceed the time limit for this case. Therefore, I tried to create another optimizations. The fully optimized code can be found below.
Bd.cpp (C++ 2KB)
There is a different solution, as explained by Felix Halim here.
I once found a quite similar problem in Topcoder SRM (forgot which one). I know the solution requires some O( D ) Dynamic Programming, where D is the number of digits. However, seeing that it involves some Roman numbers (which is really tricky), I decided not to code for this problem. Dennis made the brute-force solution (which runs 50 million looping at maximum, multiplied by some big constants) which got a TLE. However, I found a very interesting trick during the last minutes : if just we can precompute all of the values, and store it in a group of 1000s range, then we can put the numbers in the coding (precomputed) which will require some only 50.000 elements in the array. For each query, we will need at most 2000 loops to retrieve the value. However, 5 minutes was not enough to code this trick and thus we did not solve the problem.
I remembered a similar (but not exactly the same) problem in Topcoder SRM. However, I did not think of any solution. The only thing I think of is that it is involving something like Euler path (which can be solved with Fleury’s algorithm), but I did not think of the edge-deletion methods. Thus I did not solve the problem, and did not code it at all.
As you might have noticed, some of my solution are not the same with the solutions made by the problemsetters, and there are some other alternative solutions as well. Felix Halim did a nice job on explaining these solutions in his writeup.
(Note: the codes posted are for educational purposes only. For other purposes, you need my permission.)