1. Min-Zheng Shieh
  2. acm-icpc-topc-2016

Overview

HTTPS SSH

Taiwan Online Programming Contest 2016

Taiwan online programming contest is the subcontest of the 2016 ACM-ICPC Asia Chung-Li Regional. The problemset is for a three-hour competition.

The problem setters

  • Min-Zheng Shieh
  • Shang-Hsin Yu
  • Jyun-Jie Liao
  • Pin-Chang Pan
  • Li-Cheng Lan

Hints

Problem A

Just simulate the process. Try strtok(str,"(), ") or scanf("(%d,%d,%d)%*s", &state, &dir, &wb) if you're using C.

Problem B

Since the graphs have only three vertices, you may enumerate all possible bijective mappings. Output yes if there exists a mapping satisfying the property.

Alternative solution: Output yes if two graphs have the same number of edges.

Problem C

Use dynamic programming. Cook wins if and only there exists a strategy that Levin has no way to win. Observe that the formula (problem) will become another simpler formula (subproblem) after Cook assigns a value to a variable. There are many overlapping subproblems, so dynamic programming can be applied. There are at most O(3^n) subproblems, and we can solve the terminal cases by evaluting boolean expressions. Python users may benefit from eval(), however, they must use efficient algorithms. On the other hand, backtracking is fast enough in C/C++/Java.

Problem D

If some if-else jumps downward, then the program is bad. Assume there is no such if-else. We may treat every if-goto statements as an interval. For example, convert if (expr_100()) goto line_33; into [33,100]. Now, check whether there are two distinct intevals [a,b] and [c,d] such that a<c and c<b. If yes, then the program is bad. Otherwise, the program is good.

Problem E

Observe that the roads form a tree. To travel to all destinations, the least cost is to walk every edge twice:

  • You must reach all leaves. So you have to walk the every edge that connects a leaf twice.
  • Removing the edges connecting leaves. You can apply the above argument again. Repeat it until all edges are considered.
  • The lower bound is to walk every edge twice. Now, consider starting a depth first search from thre origin. You can see DFS visit all destinations and walk every edge twice. Moreover, DFS will return to the origin at the end.
  • We can conclude the least cost is to walk every edge twice.

The solution is:
Compute the minimum spanning tree of the destinations. The answer is two times the cost of the minimum spanning tree.

Problem F

Record the extreme values of the coordinates. You may create a grid [min_x,MAX_X]x[min_y,MAX_Y], and use flood fill algorithm to determine the number of separated area. This should be fast enough in C/C++/Java.

Alternative solution: number_of_faces = 2 + number_vertex_edges - number_of_vertices if the graph is planar and connected.

Problem G

Ask the problem setter truckski Min-Zheng Shieh.

Problem H

Just do it.

Problem J

Ask the problem setter aaaaajack Jyun-Jie Liao.

Copyrights

  • The poster is copyrighted.
  • The copyrights of the practice problemsets are owned by their problem setters.