Nov 112014
 

B. One Way Streets

Author: Suhendry Effendy
Prepared By: Suhendry Effendy, Felix Halim
(link to problem B)

If you have learned about graph algorithm, then this problem is easy for you.

This problem can be solved simply by any shortest path algorithms, e.g., Dijkstra, Bellman-Ford, or Floyd Warshall. Notice that reversing an edge is the same as having a cost to traverse the edge in opposite direction. So, we can construct the graph where traversing an edge in its direction cost 0, while traversing its opposite direction cost 1.

Floyd Warshall (FW) is a smart choice (even though Dijkstra is okay) as the number of nodes is quite small (≤ 100). However, you should be careful if you want to use FW, especially when constructing the cost matrix. Recall that there might be multi-edges (same pair of nodes connected by multiple edges) in the input. One directed edge in the input contributes to two directed edges in the graph: one with cost 0 in the same direction, and the other with cost 1 in the opposite direction. In the cost matrix, you should store only the one with minimum cost. There might be edges in both directions (A to B and B to A) in the input, in which the cost matrix for cost[A][B] and cost[B][A] both should be 0.

There are 124 submissions for this problem in which 49 managed to solve this problem. The first team who solved this problem is BerinGAS (minute 18) from University of Indonesia.


  27 Responses to “ACM-ICPC INC 2014”

  1. “One popular approach was by first sorting all the strings and pair each succesive string whenever possible”, kode saya spt itu, hanya saja pasangkan dr yg terpanjang http://ideone.com/PGjPAq

  2. komen untuk prob J

    β€œOne popular approach was by first sorting all the strings and pair each succesive string whenever possible”, kode saya spt itu, hanya saja pasangkan dr yg terpanjang http://ideone.com/PGjPAq

    • koreksi, prob G

    • Ngga, kode kamu nggak seperti itu. Approach kamu itu jadi sama dengan approach greedy yang bener (pasangin dari leaves) — string yang paling panjang saat itu pasti leaf.

      Yang dimaksud “pair each succesive string whenever possible” itu comparenya bener-bener cuma sama 1 string di sebelahnya aja (sorted); sedangkan kamu compare dengan yang panjangnya lebih pendek.

  3. a bit curious about problem H. Did you use the real Kawal Pemilu data for judge’s test case? πŸ˜€

  4. nice problem, nice editorial, pretty helpful, thx πŸ™‚

  5. saya penasaran dgn problem yg blm sempat saya kerjakan (dan AC), apakah mungkin akan diupload ke situs online judge ?

    saya dpt ide sederhana utk problem J dgn menelusuri apakah suatu nilai bisa jadi pivot (menjadi ‘L’), setelah itu cek apakah bs dr index tersebut menjadi good segment, jika tidak cetak impossible, kode saya : [[REMOVED]]

    thx koreksinya πŸ˜€

  6. How about ACM-ICPC 2014 Jakarta write up?? Will it be published?

  7. How can I get input data ?

    Thank you for sharing.

    • Ah… I didn’t notice this comment before >.< I'll not share the input data publicly. You can test your solution in some online-judges, e.g., tokilearning or joj. (I think) I have sent the test data to the admin on those sites.

 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)