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
Just simulate the process. Try
strtok(str,"(), ") or
scanf("(%d,%d,%d)%*s", &state, &dir, &wb) if you're using C.
Since the graphs have only three vertices,
you may enumerate all possible bijective mappings. Output
yes if there
exists a mapping satisfying the property.
yes if two graphs have the same number of edges.
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
however, they must use efficient algorithms. On the other hand, backtracking
is fast enough in C/C++/Java.
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
Now, check whether there are two distinct intevals
c<b. If yes, then the program is
bad. Otherwise, the
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.
Record the extreme values of the coordinates.
You may create a grid
and use flood fill algorithm to determine the number of separated area.
This should be fast enough in C/C++/Java.
number_of_faces = 2 +
if the graph is planar and connected.
Ask the problem setter
truckski Min-Zheng Shieh.
Just do it.
Ask the problem setter
aaaaajack Jyun-Jie Liao.
- The poster is copyrighted.
- The copyrights of the practice problemsets are owned by their problem setters.