Commentaries on
Problems
JUDGE TEAMICPC 2019 ASIA YOKOHAMA REGIONAL

Predicted # of Correct Answers

Estimated vs. Solved @Freeze

#Solved vs #Teams @FreezeCommentaries
Decreasing order of #solved teams(tie-breaked by judge's estimation)
A --> B --> H --> E --> G --> I --> C --> D --> F --> K --> JA:Fast Forwarding

Story3x triples the video playing speed.
1/3x reduces the speed to one-third.
Button state is checked each 1 second.
How quick can you fast-forward thevideo to the start of your favorite scene?

Key Observations
No need to consider pressing [1/3x] before any [3x].

1+3+3+1+3+1 = 1+3+3+3+1+1
3x

1/3 3x 1/3

3x

1/3

No need to consider pressing [3x] later than sooner.

1+3+3+3+9+3 = 1+3+9+3+3+3
3x

3x 1/33x

3x 1/3

Solution
No need to search all button pressing patterns!

Greedily press [3x] for a first few seconds(until it overruns the target scene.)

3x 3x 3x

1/3

1/3

1/3

1+3+9+27+(…+27)+(…+9)+(…+3)+(…+1)
Then the timing of [1/3x] easily follows fromthe remainder of the divisions by 3, 9, 27, …

B: Estimating
the Flood Risk

StoryMr. Boat wants to know the average altitude of his land in orderto estimate the flood risk.

As no steep slopes are in his estate, he thought that it would beenough to measure the altitudes of only limited number of sites
and approximate the altitudes of the rest based on them.
Your job is to write a program that computes total of altitudes of
all the mesh-divided areas.
If there are multiple possibilities, among which one that gives thelowest average altitude should be considered.

Solution
The range of the altitude of each area (x, y) is the intersection of [ zi - d, zi+d ]for all measured area (xi, yi) of altitude zi, where d is the Manhattan distance
between (x, y) and (xi, yi).

upper boundlower boundIf there exist one or more area in which the range of the altitude is empty,
answer "No".

H:Parentheses
EditorProblemGiven text editing commands● Append (● Append )● Delete last character
Count the number of balanced substrings
Examples(())
answer = 2()()
answer = 3(()()) answer = 4

Solution● Count the difference of the answer after
commands● Separate with unmatching left parens● Divide into minimal balanced strings. This is a stackAppend left paren (stack.Push(0)Append right paren )stack.Pop()
stack.Top() += 1
answer += stack.Top()Append right paren ), no sep
When there is no separator, the size of stack is one.
stack.Top() = 0

Delete Last Character● Append commands run in O(1)● Rollback also runs in O(1)x = stack.Pop()
stack.Top() += 1
answer += stack.Top()

stack.Push(x)stack.Top() -= 1
answer -= stack.Top()Problem E:
Reordering the Documents

Reorder documents via two extra piles
１
３
４
２
６
５

Documents with larger seq. num.
should be piled above
to allow moving them to the
document box in order

Height limit

６２１

Temporary Piles

５
４
３

１
２
３
４
５
６

The document with the largest seq# moved so far (M) must be
on top for the temporary piles to be properly ordered⚫ If the next document to move has # less than M, thedocument should not be placed upon M. No choice here.
⚫ If the next document to move has # larger than M, thedocument can be moved to either of the temp. piles.
The height limit should be respected in both cases.
Height limit

２
５
６

５
２
１

５
２
６
４
３

⚫ If any remaining documents have # less than both tops of thetemporary piles, they can never be handled properly.
⚫ The min. seq. # below each doc can be computed beforehandwith O(n).

⚫ With this info, moves leading to a problem in future can be
avoided beforehand.
１(2)
３(2)
４(2)
５(2)
２(6)
６(∞)

４
５
２
６

４
３
１

４

Solution: O(mn)⚫ For docs on the pile, compute the min. doc # be low: O(n)⚫ Build a table t of the different possible ways to move docs,
indexed by the height of the pile with the larger # doc on top.
Initiate it as [0]=1 and other elements 0: O(m)⚫ For each doc, from the top, update the table: O(mn)➢ If its # is less than the largest so far, no changes are needed➢ If it is larger, it may be placed on either of the temp. piles.
Initiate a new table n with all its items 0
For i = 1..m,◦ n[i] += t[i]◦ n[i+1] += t[k-i]; move to the pile with smaller top; move to the pile with larger top, k is # docs so far➢ Copy n to t

Pile height constraints should be checked during the operation

G:Ambiguous
Encoding

Problem Description
Find the shortest length of ambiguous binary sequences
made from the given code set.

01

Charactersto encode. . . ‘A’
. . . ‘B’

100

...

‘C’

1101

110

...

‘D’

?

Code Set
1

Encoding ofString to Binary Seq.
“AAB” -> 1 1 01?

“DA” -> 110 1

Ambiguous!
(You can’t decode
this correctly)Naïve Way to Find Amb. Seq.
Code Set
001
01
01
11010

01
0111

0111
0111
•Start from a pair of codes s.t. one is a prefix of the other.

Naïve Way to Find Amb. Seq.
Code Set
001
01
11010
11010

01110100111

0111•Start from a pair of codes s.t. one is a prefix of the other.
•Put a code whose prefix is the remainder, orNaïve Way to Find Amb. Seq.
Code Set
001
01
01
11010

0111010011101

0111•Start from a pair of codes s.t. one is a prefix of the other.
•Put a code whose prefix is the remainder, or
Put a code that is a prefix of the remainder.

Naïve Way to Find Amb. Seq.
Code Set
001
001
01
01
11010

0111010 01
Found an ambiguous seq.
011101001

0111•Start from a pair of codes s.t. one is a prefix of the other.
•Put a code whose prefix is the remainder, or
Put a code that is a prefix of the remainder.

•Done when the remainder is an empty sequence.

Observation
0111010 1100
0111 0101100

011011010 1100
0110110101100•Given an intermediate state of the naïve process,the shortest tail to the even length depends only on the remainder.
•So, we can do DP on remainders• You need to remember only the shortest seq. to the remainder

Solution: Shortest Path Search•V = Possible remainders :: |V| = O(216)•E = Transition by code :: |E| = O(16 * n + 16 * 216)•(R1, R2) in E  there exists a code C such thatC = R1 + R2 (at most 16 for each code), or
R1 = C + R2 (at most 16 for each remainder)•Length = min( |R1|, |C| )•Start = Remainders of all possible pairs of the given codes•Goal = Empty remainder•No path to the goal  no ambiguous sequence exists.
•So, you can use Dijkstra algorithm to solve this prob. in time

I:One-Way Conveyors

Problem Summary
Given an undirected graph and necessary moves
Make the graph directed while keeping all the necessary moves
2 ≤ 𝑛 ≤ 10000, 1 ≤ 𝑚 ≤ 100000, 1 ≤ 𝑘 ≤ 100000

Observation
If an edge is always passed in two moves with different directions,it’s definitely impossible to make the graph directed

If an edge is a bridge, it’s passed in any possible paths for the move

Directions of all bridges are determined uniquely (or not relevant)Decompose graph by bridges
Decompose the graph by bridges

The graph is a tree
Every vertex is a 2-edge-connected graphEvery edge is a bridge

2-edge connected graph
Is it possible to make a 2-edge connected graph directed
while keeping all the moves?

Always Yes!!
Robbins’ theorem
It’s possible to make a 2-edge connected graph directedthat has a path from every vertex to every other vertex

2-edge connected graph
One easy way to assign directions of edges

Perform a depth-first search
Forward edges are directed from the top to the bottom
Back edges are directed from the bottom to the top

Directions of bridges
The graph is a tree now

Each move is divided to two moves by its lowest common ancestor

Directions of bridges
For each upward (downward) move, add +1 to its edges

If an edge has a value, the edge should be upward (downward)
This can be efficiently done by adding +1/-1 to endpoints
and traversing the tree with summing the values
-1

+1
+1
+1

-1

+1
+1

Summary
1. Decompose the graph by bridges

2. Assign directions of 2-edge connected graphs
3. Divide moves on the tree to upward/downward moves by LCA
4. Validate and assign directions of the tree
1 and 2 can be done together by a depth-first search in 𝑂(𝑛 + 𝑚)

3 can be done in 𝑂( 𝑛 + 𝑘 log 𝑛)
4 can be done in 𝑂(𝑛)The total time complexity is 𝑶(𝒎 + 𝒏 + 𝒌 𝐥𝐨𝐠 𝒏)Appendix
It’s also interesting to consider how to validate answers efficiently

Given a directed graph and necessary moves
Check if all the moves are actually valid

C:Wall PaintingProblem Description
i-th robot paints j (in [li, ri])-th panel in color ci, when activated.
The aesthetic value of each panel is defined as follows:➢Left unpained:zero score➢Painted in 1 color: positive score (+x)➢Painted in 2+ colors: negative score (-y)
Maximize the sum of aesthetic values.

In case of x=7 and y=2, the sum of values is 61.

Observation
The following cases are ignorable. (There is a redundant range)- There is a range overlapped by another range.

- There is a panel which is painted 3+ times.

Solution
First, sort all robots increasing based on ri.
Let dp[i] be the maximum sum of aesthetic values when the right mostactivated robot is i-th robot.
dp[i] = max{
max_[j s.t. j < i and rj < li] dp[j] + (ri – li) * x
max_[j s.t. j < i, lj<li≤rj and ci=cj] dp[j] + (ri – rj) * x
max_[j s.t. j < i, lj<li≤rj and ci≠cj] dp[j] + (ri – rj) * x – (rj – li) * y}

Solution
Let dp[c][i] be the maximum values, when the right most activated robot is i-th robot
and their color is c. This expression can be transformed as follows:
dp[c][i] = {-∞(if color ≠ ci)

max{(max_[j, c’ s.t. j < i and rj < li], c’ ∈ {1, 2, 3}] dp[c’][j]) + (ri – li) * x(max_[j s.t. j < i, lj<li≤rj] dp[c][j] - rj * x) + ri * x(max_[j s.t. j < i, lj<li≤rj] dp[(c+1)%3][j] - rj * (x + y)) + (ri * x + li * y)(max_[j s.t. j < i, lj<li≤rj] dp[(c+2)%3][j] - rj * (x + y)) + (ri * x + li * y)}}

We can speed up the calculation by using RMQs!

(otherwise)Problem D
Twin TreesBros.

ACM ICPC 2019
YO KO H A M A

D:Twin Trees Bros.

How to check whether two trees are twin or not. →Translate
Find a leaf node of a tree.
Translate the leaf node to the origin point (0,0,0).
Rotate the edge between the leaf node and its parent around z-axis onto yzplane.
Rotate the parent node around x-axis onto z-axis.
(Optional) Rotate an ancestor node around z-axis onto yz-plane.

(1) Find a leaf node of the tree

z
ez
leaf
node

ey
ex

x

y

(2) Translate the tree so that the leaf node moves tothe origin point.
z
ez

leaf
node

ey
ex
x

y

(3) Rotate the tree around z-axis so that the parent
node moves onto the yz-plane.
zparent
node

y1
x1
x
x

y

(4) Rotate the tree around x-axis so that the parent
node moves onto the z-axis.
zparent
node

leaf
node

x

y

(5) Scale the tree so that the length of edge between
the leaf and parent nodes is 1.
zparent
node

1

leaf
node

x

parentnodey(6) (Optional) Rotate the tree around z-axis anancestor node moves onto yz-plane.
zparentnode
ancestor
node
leaf
node

y
x

(7) For each leaf node of T, transform T and compare
it with S.
Transformed Tree T

Tree SzzzCompare

y

x

x

y

z

twin

Tree TxyzTransform

x

y

x

y

Thank you very much for your attention.

F:Halting Problem

Problem Summary
Solve the Halting problem of the following program.
The program has two variables x, i.

∧_∧ ババババ（ ・ω・)=つ≡つ（っ ≡つ=つ`/ )➢In the initialization, set x = x0 and i = 1➢(an execution step) When i < N + 1,
➢if x is equal to a i, then set x = x + bi and i = ci,➢otherwise, set x = x + d i and i = ei.

➢When i becomes N + 1, the program terminates.
➢For given x0, a, b, c, d, determine whether the program halts or not.
➢If it halts, compute how many steps are executed.

Example
Sample 1 (N=2)
x=x+1x is 5?

1

x=x+1

x=x+2

x is 10?

2

3

x=x+1

x=0
i=1

true
false

Example
Sample 1 (N=2)
x=x+1x is 5?

1

x=x+1

x=x+2

x is 10?

2

3

x=x+1

x=1
i=1

true
false

Example
Sample 1 (N=2)
x=x+1x is 5?

1

x=x+1

x=x+2

x is 10?

2

3

x=x+1

x=5
i=1

true
false

Example
Sample 1 (N=2)
x=x+1x is 5?

1

x=x+1

x=x+2

x is 10?

2

3

x=x+1

x=6
i=2

true
false

Example
Sample 1 (N=2)
x=x+2

x=x+1
x is 5?

1

x=x+1

The program halts!
The number of executed
steps is 9.

x is 10?

2

3

x=x+1

x = 12
i=3

true
false

Solution (Graph)➢Make a graph➢vertex = state i (1, 2, 3, …, N+1)
➢edge = false part

➢This graph has at most one loop
in each connected component.
➢outdegree = 1 for every vertices

Solution (query)➢(query) given (x, i), find the nearest vertex
where the condition is true.
➢If the same condition becomes true twice,
the program does not halt.

➢Remove one edge in the loop.
➢one tree + one loop

➢Divide into two problems➢in the tree
➢in the loop

now
true
find hereSolution (Loop part)➢Fix a vertex v0(e.g. the root of the tree).
x is au?

➢x become x + L after one loop.
➢Reduction to v0

u➢The condition x == a u at u➢⇔ x == a’u at v0➢(in one loop)
x is a’u?

➢Make a table and do binary search here.
➢Table[a’u mod L] := {a’u: u is a vertex in the loop}➢O(log(N)) for each queryv0

Solution (Tree part)➢The idea is the same as the loop part.
➢There are two solutions of O(Nlog(N)):

1.

Use persistent binary search tree
➢ Not difficult because the insertion operation is static in this problem.
➢ O(log(N)) for each query

2.

Encode the tree to an array (like LCA ↔ RMQ)
➢ Binary search on the array.
➢ O(log(N)) for each queryK: Draw inStraight LinesDraw the specified image
Input

Solution

Draw the specified image
Input

Solution1

Draw the specified image
Input

Solution

2

Draw the specified image
Input

Solution3
OverpaintLine-paint operation: Paint 1 × 𝑘 or 𝑘 × 1
pixels either black or white.
Cost = 𝑎𝑘 + 𝑏
1

2

…

k

Single-paint operation: Paint a single pixel
either black or white.
Cost = 𝑐Overpainting
You can overpaint black ⇒ white

Overpaint

Overpainting
You cannot overpaint white ⇒ black

2
1

Overpainting
You can overpaint a pixel at most once

2
1

3

Solution

Minimum Cut !!!!!

Key observation 1
We can assume the following order ofoperations:
1. Black line-paint2. White line-paint3. Black/white single-paint (uniquely decided)

Key observation 2
Once we have painted a pixel horizontally, we
don’t have to paint it horizontally anymore.
8𝑎 + 2𝑏>4𝑎 + 2𝑏

Variables➢ 𝑏ℎ𝑖,𝑗 ≔ [paint 𝑖, 𝑗 black horizontally]➢ 𝑏𝑣𝑖,𝑗 ≔ 1 − [paint 𝑖, 𝑗 black vertically]➢ 𝑤ℎ𝑖,𝑗 ≔ 1 − [paint 𝑖, 𝑗 white horizontally]➢ 𝑤𝑣𝑖,𝑗 ≔ [paint 𝑖, 𝑗 white vertically]
condition ≔ ቊ

1 if the condition holds
0 (if the condition does not hold)Total cost of black-horizontal-line-paints𝑥ҧ ≔ 1 − 𝑥

σ𝑢𝑣 𝑐𝑢𝑣 𝑥𝑢 𝑥𝑣 can be minimized by a reduction
to s-t min-cut ☺
𝑥=1

𝑥=0

𝑠

𝑣

𝑢

𝑡

Cost of painting (𝒊, 𝒋) black𝑐 × 𝑏𝑣𝑖,𝑗 𝑏ℎ𝑖,𝑗 + ∞ × 𝑤ℎ𝑖,𝑗 + 𝑤𝑣𝑖,𝑗No black-line⇒ black-single

cannot overpaint black over white

Cost of painting (𝒊, 𝒋) white𝑐 × 𝑏ℎ𝑖,𝑗 𝑤𝑣𝑖,𝑗 + 𝑤ℎ𝑖,𝑗 𝑏𝑣𝑖,𝑗 + ∞ × 𝑏ℎ𝑖,𝑗 𝑏𝑣𝑖,𝑗black-line & no white-line⇒ white-single

cannot overpainta pixel twice

Thanks to the observation 2, we can skip
other cases (𝑏ℎ𝑖,𝑗 𝑤ℎ𝑖,𝑗 and 𝑏𝑣𝑖,𝑗 𝑤𝑣𝑖,𝑗 )J:Fun Region
Image source: https://en.wikipedia.org/wiki/Island#/media/File:Fernando_noronha.jpg

Problem
You are given a polygon.
An inside point is fun if you can reach every vertex by some spiral path.
Fun region := All fun points.
Calculate the area of a fun region.

Not funFun

Trivial Case

Convex → Fun region is entire parts

Concave?

Only one concave vertex → ?

Concave?

Fun region can be obtained by cutting the polygon
with a segment from the concave vertex.

In General

For every concave point, perform cuts.
The remained polygon is the answer.

Solution

Perform non-convex cuts from each concave point.

Each cut can be done in O(n) time.
Total complexity is O(n^2).

Correctness?

Correctness (1/7)
Point p is fun⇔ Every vertex is reachable from p by a spiral path
⇔ p is reachable from every vertex by a ccw-spiral path

Correctness (2/7)
Point p is fun⇔ Every vertex is reachable from p by a spiral path
⇔ p is reachable from every vertex by a ccw-spiral path

Let S(v) := {p | p is reachable from v by a ccw-spiral path}.

Fun region = ∩v:vertex S(v).

Correctness (3/7)
When vi+1 is non-concave, S(vi+1) ⊆ S(vi) holds. So,

I := {i | vi+1 is concave},
Fun region = ∩i∈I S(vi).
vi
vi+1

Correctness (4/7)
Assume that vi+1 is concave.
Take a line that passes vi and vi+1 and let q be a first contact point.
We can see that S(vi) does not include any points in a region enclosed by
vi+1q and the polygon. Why?

vi
vi+1
q

Correctness (5/7)
Suppose that there exists some ccw-spiral path from vi to X.
⚫The ccw-spiral path cannot cross segments vi+1q.
⚫If the path can reach X without crossing vi+1q, it implies there is a holein the input. Contradiction.

vi
vi+1
q

Correctness (6/7)
This implies that (remaining region by cuts) ⊇ (fun region).
Lastly, we will prove that “⊇” is actually “=“.

vi
vi+1
q

Correctness (7/7)“(remaining region by cuts) = (fun region)”
Suppose that (remaining region by cuts) - (fun region) is nonempty. Thismeans there exists a point X and vertex vi such that X won’t be cut and X
is not in S(vi). The boundary of S(vi) is a polygon such that each edge iseither (i) some edge of original polygon or (ii) half line passing from vj to
vk where vk is concave vertex. When X is in a region enclosed by thepolygon and half line vivk, X should have been cut by a half line from vk.
This is contradiction.

vk
S(vi)
vi=vj