JUDGE TEAM ICPC 2022 ASIA YOKOHAMA REGIONAL
We thank the organizers for working hard to manage to have this on-site contest for the first time in the three years. Judges developed an easier problem set than last year for on-site contest 。 No access to the Internet 。 No simultaneous coding Note: two contestants could not join, which may affect the results of their teams.
We introduced an interactive problem for the first time. After careful discussion, we decided to use an easy interactive problem.
interactive
100 interactive
#Solved
PROPOSER: KAZUHIRO INABA AUTHOR: TOMOHIRO OKA
"Given n intervals and an integer k = [ai, bi] "Find a date assignment for each intervals "ai ≤ datei ≤ bi "The frequency of a date should be no more than k ▪#{i | date i = d} ≤ k
"n=5, k=1
"Greedy assignment "Select a house that has minimum bi •  Loop n times • i  K¶  the house not assigned yet has minimum bi . d  []  earliest date that is in [ai, bi] and count d < k datei . . count d += 1 B: Interactive
PROPOSER: MITSURU KUSUMOTO AUTHOR: MITUSRU KUSUMOTO
• The first interactive problem in this regional! • Judge has a secret number x. • You should guess it by using queries, where you specify a number α and you receive digitsum(α + x). • Query limit ≤ 75 • 0 ≤ a, x < 1018
Obtain d o = digitsum(x) by query α=0. Now assume that you query α=500. • If x is like x=..4.. or x=..3..  (“” stands for arbitrary number in decimal notation), then digitsum(x+α)=d 0+5 is returned. • If x is like x=..5.. or x=..6.., then digitsum(x+α) < do+5 is returned due to carry. Using this observation, you can identify each digit by binary search. Total query required is 1 + 18 · [log2 10] = 73. G: Remodeling
PROPOSER: TOMOHARU UGAWA AUTHOR: YUTARO YAMAGUCHI
Enhance the security of the castle by remodeling the dungeon. 15 9
Enhance the security of the castle by remodeling the dungeon. 15 9 n = h×w ≤ 2.5×105 l < 2n ≤ 5×105
Given a tree of n = h×w vertices. Given ℓ = (h − 1)×w + h×(w − 1) possible new edges. Maximize the distance between s and t by removing one edge and adding one new edge instead so that the result is also a tree. n = h×w ≤ 2.5×105 l < 2n ≤ 5×105
Maximize the distance between s and t by removing one edge and adding one new edge instead so that the result is also a tree. The new route through { u, w } consists of α + d + 1 + e + c edges. dist(s, u) + dist(t, w) + 1 = dist(s,w) + dist(t,u) − 2b + 1 < dist(s,w) + dist(t,u) + 1 n = h×w ≤ 2.5×105 l < 2n ≤ 5×105
Maximize the distance between s and t by removing one edge and adding one new edge instead so that the result is also a tree. 1.  Compute dist(s, v) and dist(t, v) for all vertices v.     Θ( n ) time 2.  For each possible new edge {u,w}, 0( ℓ ) time if dist(s, u) + dist(t, w) ≠ dist(s, w) + dist(t, u), then the minimum of them + 2 is a candidate of the answer. The new route through { u, w } consists of a + d + 1 + e + c edges. dist(s, u) + dist(t, w) + 1 = dist(s,w) + dist(t,u) − 2b + 1 < dist(s,w) + dist(t,u) + 1 PROPOSER: KAZUHIRO INABA AUTHOR: KAZUHIRO INABA
Match the left pattern to the right pattern (up to rotation), by moving exactly one coin.
Match the left pattern to the right pattern (up to rotation), by moving exactly one coin. ldea If the src & dst patterns are already on the same location, we just need to scan and spot the two differences. How to find the right… ◆ rotation? → try all 4 cases! ◆ parallel displacement?
If the lexicographically 1st coin does not move, the coin stays 1st or 2nd. If it moves, 2nd coin becomes 1st or 2nd. Try 4 offsets matching src {1st, 2nd} with dst {1st, 2nd}!!
◆ If coins aren't many (N<500), brute force search. ◆ O(N³) by testing all (src, dst) pairs. ◆ If coins are many (N>=500), one-coin move does not change the average of xy-coords too much. (Because max possible move is within ±1000.) Try the offsets matching average points within ±2!
◆ Two patterns are very similar, because after all they differ by only one coin. ◆ Exploit such similarity in some way, then you’ll reach to a solution. ◆ Many other approaches are possible. PROPOSER: AKIFUMI IMANISHI AUTHOR: AKIFUMI IMANISHI
Find the number of combinations of four integers tuple (a,b,c,d): * a,b,c,d is different * Ｌ <= a+b < R * abcd <= X * (a+1)bcd > X * a(b+1)cd > X * ab(c+1)d > X * abc(d+1) > X
Sort (a,b,c,d) by increasing order * ａ ＜ｂ ＜ｃ ＜ d * abcd <= X < abc(d+1) Find (*4) of sum of numbers of: * L <= a+b < R * L <= a+c < R * L <= a+d < R * L <= b+c < R * Ｌ <= b+d < R * L <= c+d < R Solution * abcd <= X < abc(d+1) <=> d = floor(X / abc) Algorithm: For a in 1..X^(1/4) For b in 1..X^(1/3) Binary search: Count the number of c Time complexity Algorithm:
Binary search: Count the number of c
Time complexity: 0(√XlogX)
PROPOSER: SHUICHI HIRAHARA AUTHOR: SHUICHI HIRAHARA
Given a simple polygon and points on its boundary, solve the Traveling Salesperson Problem (TSP).
Given a simple polygon and points on its boundary, solve the Traveling Salesperson Problem (TSP).
▷TSP is NP-hard, but this special case is easy. ▷Without loss of generality, the shortest tour visits the points in clockwise order.
1. Sort all the points in clockwise order. 2. Compute the shortest distance (inside the polygon) between i-th and ( i + 1)-th vertices. 3. Output the sum of the distances. E: Incredibly Cute
PROPOSER: SOH KUMABE AUTHOR: SOH KUMABE Story Count the way to cut given string into ICPC-ish substrings.
The string consists of I,C,P is ICPC-ish if - two of them appear same number of times, and - the other one appears more than them. ICPCCPPPCIICCP
1.  Input: string S. 2.  Output: #ways to cut S into ICPC-ish substrings, modulo 998244353. Solution DP[t]: #ways to cut first t letters into ICPC-ish substrings 0 (|S|²), TLE Solution ICPC Solution ICPC Solution ICPC Solution ICPC Solution ICPC Solution ICPC Solution DP[◎]=sum of DP values on these directions Solution DP[◎]=sum of DP values on these directions Use Fenwick Tree to compute the sum 0 (| S | log | S |), AC
Secret PROPOSER: MASATOSHI KITAGAWA AUTHOR: MASATOSHI KITAGAWA
A grid graph with some special edges (shutters) is given. Find the minimum number of shutters to close to satisfy There exists a path from S to T with no closed shutters on it. 1. Any path from U to T contains at least two closed shutters. 2.
…… shutter
closed shutter Solution Find the minimum cost flow in the ‘dual’ graph.
. vertex of a cell → vertex . . wall → black edge (cost 0, capacity ∞) shutter → dotted edge (cost 1, capacity 1) Remove an outer wall (edge (p,q)) of U. Remove an outer wall of S (and T). p q
Minimum U-T cut in the original graph in which S and T belongs to the same connected component Shortest p-q path with no black vertices The bold edges = the walls used in the left-hand rule from S to T
The original problem = Find the minimum cost of shutter-disjoint two p-q paths with no black vertices. = Find the minimum cost of flows through no black vertices with amount of flow 2.
PROPOSER: SHINYA SHIROSHITA AUTHOR: SHINYA SHIROSHITA
You need to schedule n  events. Each event has a polygonal line cost function whose input is the start time. You need to calculate the minimum total costs such that no two events have overlap. Cost Functions Non-overlapping Schedule
Each solution consists of a series of consecutive events sequences). We can assume that each sequence has an event whose art time is at a vertex of its cost function. Proof idea: We can slide the sequence without increasing the total cost. This slide ends with either of • Some event reaches a vertex of its cost function, or • Collide with another sequence. → We can merge both sequences and continue sliding. Some event starts at one of its vertices of the cost function
time

Dynamic Programming (DP) memorizing vertices of cost functions whose events’ start times are at the vertices ( vertices with events ). • DP State: [previous vertex w/ event][used event set]. • Events between vertices w/ events are appended to either the left or the right event. → Next slide
time
DP transitions ★: previous vertex with event
We can precompute the minimum cost for appending interval events to left/right in O ( m²3 n ) where m is the total number of the vertices of the cost functions. (3ʱ = (left, right, outside) n ) The main DP transition part can also be calculated in 0(m²3n). (3n = (used, use now, not used) n ) PROPOSER: YOICHI IWATA AUTHOR: YOICHI IWATA
Given a set of arcs with a right central angle, is it possible to construct a single loop using all the arcs?
Classify arcs into 4 groups.
|S_,_| ≡ |S_,+| ≡ |S+,_| ≡ |S+,+|   (mod 2) S_,_,S_,+,S+,_,S+,+ ≠ Ø
This can be solved in O (n³r²) time using subset sum DP, but too slow (♂
Define  S_,*  :=  S_,_  U  S_,+, ... Then  S_,_ = S_,* N S*,_, ...
⇒ there are at least two even bisections
Compute the number of even bisections in 0(n²r) time using subset sum DP. If the number ≥ 2, answer Yes; otherwise, answer No. PROPOSER: RYOTARO SATO AUTHOR: RYOTARO SATO
• Quiz Contest by n participants is ongoing • The first participant to answer the goal number of questions is winner • Participant i can answer α į of m questions not proposed yet • Participant i has to answer additional bi questions to win • Count the number of question orders such that participant i will be the winner for each i = 1, ..., n , modulo 119×2²³ + 1 • Constraints: •  1 ≤ n ≤ m ≤ 2×10 5 •  Each question is answered by exactly one participant (α₁ + … + α n = m). • Every participant has a chance to win ( b į ≤ α į ).
• Build tree structure of participants • We want to “distribute" winning probability of subtree ps from root ({1, 2, ... , n }) and finally get p { i} of each participant i p (Winner is in S | Winner is decided by i th question )
• Key idea of fast counting: Two step divide-and-conquer strategy Bottom-up DP to solve the auxiliary problem: “When will the winner be 1. decided?" Top-down DP to solve the main problem: “Who will be the winner and 2. when?," by fully utilizing previous results. • Both steps are significantly speed up by Fast Fourier Transform (FFT) and convolution! •  Note: You can use 3 as the primitive root of multiplicative group of F119×2²³+1 to find primitive 2 d -th roots (d ≤ 23) for FFT. • Overall complexity: 0 (m log n log m)
Introduce symbols: . U := (set of all participants) = {1, . . . , n} a(S) :=       ai . iES • → a(U) = m  holds. 。 f ( S , i ) := (# of perms. of a ( S ) questions s.t. the winner is decided just after i -th question) (i = 1, . . . , a(S))
• Start from {i}s for i = 1, ..., n . Merge them to make U . • f (S + T,  ·) can be calculated from only f (S,  ·) and f (T,  ·): (a(S + T)\ (a(S + T) - i\ (j + k − 1) (j − 1 + k) f ( S + T , i ) = )    f(T,k') + f(T,k) )   f(S,j') f(S,j) k a(S) α(T) − k j j'=j+1 → Convolution, O (a (S + T) log a (S + T))
• Consider uniform distribution over α(U)! permutations and introduce If the questions answered by U — S are erased, g(S, i) := P | The winner is in S | the winner is decided just after i-th question → g(S,  ·) can be calculated from ONLY f(T,  ·) AND g(S + T,  ·): (a(S + T)  −1 i+a(T)  −1) (a(S + T) −1) ( ∑ f(T,k) g(S+T,j) → Convolution again! g(S, i) =
• Finally, output α(U)! g({i},  bį) for each i .