## Friday, June 22, 2007

### ACM ICPC INC 2007 - Final Round Solutions

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.

Problem A

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).

1. To know the real order, we have to copy the list and sort it (which is easy with STL sort algorithm)

2. 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).

3. For each misplaced characters, intuitively it must be swapped into its correct location.

4. 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)

Problem D

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)

Problem G

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.

1. For each row, we create a set that contains the column number of the pillars in that row.

2. 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).

3. 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

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)

Problem H

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 :

1. Represent the tree as some edge list, bidirectional.

2. Do the recursion taking any node in the tree as parent.

3. In any node, there is just three kind of return value :

1. The number of nodes from this node downwards.

2. The minimum total cost if the median is located in this node downwards.

3. 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.

Problem B

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 :

1. 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.

2. 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.

3. 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.

Problem E

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.

Problem C

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.

Conclusion

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.)

Timo said...

Nice write-up kur :D

suhendry said...

ohhhhhhh "DP Problem I" lu itu DP-Tree yah :-D akhirnya gw tau :-P izhari said...

kurniady, handle kamu di TopCoder ?

btw, write-up nya bagus banget,
dah kayak misof :) hehehe...

Di Topcoder, handleku "auror" ... masih tetep kuning setelah berjuang setahun lebih... T_T

suhendry said...

kur, kalau rating lu ga merah dalam beberapa bulan ke depan... ga usah ikut ICPC aja ya :-D coaches (gw &#38; evan) udah sepakat nih :-P hehehe... Stephen Kohar said...

Hahaha,DP problem I,DP Problem A
kocak bener neh org :D
Nice writeup and story Kur!!!!
Problem B nya cicu tuh,maksa hahaha
Tapi uda keren pruningnya,worst casenya jadi tinggal O(bilangan prima paleng deket sama akar 1M) :D

suhendry : haiyah... kalu nanti gw uda merah, ntar gw multisite ya :D... yang laen pada harus merah juga donk... :P

Kohar... : iyah, pas lomba gw uda tau ada formula "ada berapa faktor x dalam n!" soalnya dulu kalo ga salah Felix pernah omongin sama loe orang... la tapi gw kaga tau formulanya, ya uda bar bar aje... :D Hi,...
do you have "test cases"?
can you give it me?

Test cases as well as the original problem statement are available in Felix Halim's site : http://felix-halim.net/story/inc07/index.php Thanh Vy said...

Hello,
I'm a student from Vietnam
I'm trying problems in INC07, luckily Felix published its problemset in English :)

I'm trapped in problem C (domino), I thought about Fleury but this problem we can't use it straight forward since it asked for Largest Euler Path...
I can't understand Indonesian, so the write-up on Felix's site I can't understand either :'( Later I read a short analysis on your blog, but still can't get the idea of domino.c (the official solution)

If you have time could you explain some details to me please?

--
Best Wishes,
-Thanh Vy I also don't understand the solution very well until now... Basically it has something to do with the Euler's path conditions such as two odd degree nodes (and others should be even) and such. Removing an edge changes the degree of the two nodes it belongs to, and somehow there is a pattern on which edges to remove to achieve the Euler's conditions. That's what I get from the explanation of the problemsetter, if I remember and understood correctly :-)

suhendry said...

For Problem C (domino), we should find a longest Eulerian Path from the graph. Or should I say, delete zero or more edges (minimum) so the graph has an Eulerian Path.

this is the idea..

Let P be the number of vertex with odd-degree in the graph.
1. if P == 0, then there is an Eulerian Tour
2. if P == 2, then there is an Eulerian Path
3. if P == 4, then delete some edges so P = 2 (remove two odd degree).
4. if P == 6, then delete some edges so P = 4, and recursively do the 3rd step (when P==4).
*note that P always an even number.

For step 3 & 4, notice that if we want to remove two odd-degree, we should form (or I'd better say: delete) a path from any two odd-degree vertex. We can use shortest path and a little bit brute force to find the least edge-removal.

by the way, you should not forget to consider the graph connectivity too :)

Suhendry Effendy Rishi said...

Hey ! man none of the solution links seem to be working 