Nov 082013
 

E. Railroad

Author: Derianto Kusuma
(link to problem E)

This is my favorite problem in this contest. This problem is interesting and it has a beautiful solution, well, at least that’s what I thought.

In order to get the minimum number of trains needed to cover (test) all segments, we need to find the maximum number of parallel segments, i.e. segments which cannot be tested by a same train. The minimum number of trains needed is exactly equal to this maximum number of parallel segments.

railroad
Figure 1

Figure 1 shows an example of a maximum number of parallel segments (shown by the red line labelled “max north-south cut”), which is 5 in this example.

Then the next question is, how to find this number?

The key point to solve this problem is: the graph is planar. First, let’s construct a DAG G where each face (enclosed area) in the planar graph becomes a node in G, and for each two faces which are adjacent to each other, draw a directed edge from the face which lies in the north to the other face which lies in the south. There will be no west-east faces because the tracks are constructed using only fork and join operation.

Figure 2 shows the faces in the planar graph. In this example, there are 7 faces numbered from 1 ato 7. Figure 3 shows how to draw a directed edge from fork and join operation.

faces in planar graph
Figure 2

fork and join
Figure 3

DAG
Figure 4

Figure 4 shows the DAG constructed from Figure 2.

Once we obtain the DAG, the problem becomes easy: we need to find the longest path in the DAG. This path will start from the north-most face to the south-most face (face 1 and 2 in Figure 2). The blue path in Figure 3 corresponds to this longest path; the length of the path is 5 (count the number of edges along the path)

The longest path found in the previous step corresponds to the maximum number of parallel segments which cannot be tested using a same train, which turn out to be the answer to the problem.

Flow-based algorithm
Using a minimum flow algorithm in this problem will give you a Time Limit Exceeded even though the answer will be correct. For those who are not familiar with minimum flow problem, the problem is similar to maximum flow, but in addition to the capacity, each edge also has a lower-bound (required minimum) flow. You have to find a flow with minimum value from s to t such that each edge has a flow between its lower-bound and its capacity.

This problem can be reduced to minimum flow problem simply by introducing a lower-bound equal to 1 to all edges (all segments) in the graph while its capacity is infinite. Then find a minimum flow from segment 1 to segment N.

The problem with this approach is, you will need a maximum flow algorithm in order to solve this (at least that is our current knowledge). I never heard any maxflow algorithm with O(N) or O(N lg N) complexity, so using this approach with N = 100,000 surely will take time. Risan implemented this approach and run the program in his laptop. He waited for ~40 minutes to process all cases before it terminates.


  12 Responses to “ACM-ICPC 2013 Jakarta – Problems and Analysis”

  1. are you sure there isn’t mod operation ?

    and this : j = j + 1, why it isn’t j = j-1 ?

    • Ah, you’re right, it should be j =j – 1 (updated).

      MOD operation is not needed, What we really need is whether a two substrings have a same hash value or not, not the hash value itself. There are only addition and multiplication operators, so overflowing the result doesn’t matter.

  2. ^that comment above is for pasti pas

  3. Halo Mr. Suhendry.
    Saya ingin sekali bisa berkompetisi di ACM ICPC. Saya Mahasiswa tingkat 2 di salah satu perguruan tinggi di bandung. Tapi skill koding saya tidak terlalu bagus. algoritma sorting saja masih bingung. Gimana ya kiat nya untuk belajar algoritma yg baik dan benar agar bisa nanti suatu saat ke ACM ICPC?

  4. How to determine which prime number should be used? I tried some prime numbers and the result is not as expected.

    • (Problem F). Just use large prime number (larger is better, its chance to collide is smaller). I used 1000003 and it’s fine.

      • I have implemented it and submitted on Live Archive, but got WA 😀
        Is there something wrong with my implementation? Could you please check it? http://pastebin.com/ECJX9yEa

      • I didn’t read your code, but it failed the first sample input: PASTIPAS.

        • Yes and it works if I do MOD operation, but still WA on Live Archive. Does your solution with above algorithm still work on LA? Maybe you/others have added more test cases to break that hash function? Or my implementation wrong?

        • I’m the one who send the data to LA and I’m pretty sure LA’s admin was quite busy to do any changes on the dataset.

          BTW, I’ve just noticed an error in F’s pseudocode. There is one line which is wrong. Try to figure that out! 🙂

          hint: pay attention to the rolling hash (when you do the multiplication with prime number); you might want to check other resources on rolling hash.

  5. ^ problem F Pasti Pas!

  6. Problem H can be solved by Dynamic Programming,here I find two states,one is index of the current question,another is wrong answers used/left so far, and then minimize the answer. But this solution does not work,though sample test case gives correct output. I saw another boolean state in some accepted codes in HUST, which tries both minimizing and maximizing. Can you please explain why another state is needed here?

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)