# Overview

Atlassian Sourcetree is a free Git and Mercurial client for Windows.

Atlassian Sourcetree is a free Git and Mercurial client for Mac.

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