Contest debriefing

Scientific Committee
 Result at 4 th hour
Total: 57 teams
First 4 hours only A B C D E F G H I J K
10/44 0/3 42/93 3/19 55/105 52/103 26/166 5/27 7/18 17/57 0/1
Solved / Tries (22%) (0%) (45%) (15%) (52%) (50%) (15%) (18%) (38%) (29%) (0%)
Average tries 2.32 3 1.82 1.73 1.84 1.81 3.19 1.93 1.5 2.28 1
Averages tries to solve 3 -- 1.79 1.33 1.62 1.71 2.5 1.6 1.29 2.35 --
• Problem J: Association of Cats and Magical Lights
• Problem H: Association for Convex Main Office
• Problem D: Association of Computer Maintenance
• Problem B: Association for Cool Machineries (Part 2)
• Problem I: Apples, Cherries, and Mangos
• Problem K: Association of Camera Makers

• (For problems C, E, F, G, J, please listen to the online commentary by

Nathan and Jonathan. https://www.youtube.com/watch?v=o7z0IZMvpaQ .
Or search “2015 ACM ICPC Singapore Regional Live Commentary” in
youtube.com)
Association of Cats and Magical
Lights
Problem J
 a
Problem
b c d
• Input: A rooted tree of N nodes
– Color of node u is Cu (1 to 100)
e f g
– Parent of node u is Pu
• For a subtree rooted at node u, a color  is a
magic color if the subtree has odd number of
color 
• Query(u): Compute the number of magic colors
of a node u
• Update(, u): Change the color of the node u to 
 a
Example
b c d
• Query(b)=1
– black is odd & white is even
e f g
• Query(c)=2
– both black and white are odd
a
• Update(red, f)
• Query(b)=3
b c d
– black, white and red are odd

e f g
 Simple solution
• For each query Query(u),
– directly count the number of colors below node u
– Report the number of colors whose counts are
odd
• For each update Update(c, u),
– Directly update the color of the node u

• This solution is slow

 1
a

Flatten the tree2 5 7

b c d

• Assign DFS order to the tree

3 4 6
e f g

1 2 3 4 5 6 7
Node a b e f c g d

• Every subtree rooted at some node can be

represented as an interval
a b c d e f g
S 1 2 5 7 3 4 6
E 7 4 6 7 3 4 6
 1
Store each color a

as a modified Fenwick tree 2 b

5
c
7
d
• Fenwick tree allows us to find range sum
and update in O(log N) time 3 6
4
• It can be modified to answer range e f g
parity
• Since we have 100 colors, the query time and update time is O(log N)

a b c d e f g
S 1 2 5 7 3 4 6
E 7 4 6 7 3 4 6

1 2 3 4 5 6 7
Node a b e f c g d
White 0 1 0 0 1 0 0
Build modified
Black 1 0 1 0 0 1 1 Fenwick tree
Red 0 0 0 1 0 0 0
 1
a

Example 2 5 7
b c d
• Query(b) is the sum of range parity of [2 4]
– White: 1 3 4 6
– Black: 1 e f g
– Red: 1
– Ans: 3
a b c d e f g
S 1 2 5 7 3 4 6
E 7 4 6 7 3 4 6

1 2 3 4 5 6 7
Node a b e f c g d
White 0 1 0 0 1 0 0
Build modified
Black 1 0 1 0 0 1 1 Fenwick tree
Red 0 0 0 1 0 0 0
 Additional note
• Our intended solution is to represent 100 bits as
2 long long (2 * 64bits).
• Then, build a Fenwick tree for the 2 long long.
• Then, we just need to make one Fenwick tree
query.

• However, Java version for Fenwick tree of 2 long

long is slower than querying 100 Fenwick trees.

• So, we accept both solutions.

Association for Convex Main
Office
Problem H
 Problem
• Input: An integer N (N  400,000)
• Output: N pairs of 2D coordinates (xi, yi) that
form a convex hull
– such that 0xi,yi4x107.
– No three points are co-linear
(1,2)

• Example: N=4
(0,1) (2,1)

(1,0)
 How to generate a convex office?
• Example: N=16
• We form a set of N/4 right-angle triangles, all
have different slope.

3/1 2/1 1/1 1/2

• Arrange the triangles in decreasing slopes.

• Create mirror-image.
• Then, a convex office with N vertices is
formed

• Question: How to generate triangles of

different slopes?
How to generate triangles of different
slopes?
• Simple solution:
…… ……
3/1 2/1 1/1 1/2 1/3

• This solution works for small N.

• When N>20000, the width/height of all
triangles > 4x107.
 How to generate triangles of different
slopes? (II)
• Generate triangle with the shortest height + width first.
– During the generation, need to ensure the height and the width are
co-prime.
– (This guarantees that the slopes of all triangles are different.)
– E.g. We will not generate (4, 2) since (4, 2) and (2, 1) have the same
slope.
(h, w)
1/1 h
• 2: (1, 1), w
1/2
• 3: (1, 2), (2, 1), 2/1
• 4: (1, 3), (3, 1),
• 5: (1, 4), (4, 1), (2, 3), (3, 2),
• 6: (1, 5), (5, 1),
• 7: (1, 6), (6, 1), (2, 5), (5, 2), (3, 4), (4, 3),
• ……
 Note
• This is a rare question in ICPC, which asks for
corner case.

• But this type of questions is getting popular in

other competitions.

• We hope that the students can develop skill

set in this aspect.
Association of Computer
Maintenance
Problem D
 Problem
• Input:
– The prime factorization of K
– (Constraint: Number of divisors of K is ~ 1010.)
• Output: f(A) mod (109 + 7)
– such that integer A minimizes f(A) = (A + K/A)

• Example: K = 23 * 7
– A=7 minimizes f(A)=A+K/A=7+8
– We output f(A)=7+8=15
Observation

f(A) = A + 25/A

A=5 minimizes
A+25/A
Brute-force solution
A techique that requires us to verify
~105 divisors
 Example
• Initialize A=1
• For x1=1, y1=343  x1*y1 = 343
• For x2=2, y2=343  x2*y2 = 686
• For x3=3, y3=245  x3*y3 = 735
• For x4=4, y4=49  x4*y4=196
• For x5=6, y5=49  x5*y5=294
• For x6=8, y6=49  x6*y6=392
• For x7=9, y7=49  x7*y7=441
• For x8=12, y8=49  x8*y8=588
K1 K2 • For x9=18, y9=49  x9*y9=882
1 X
12005 • For x10=24, y10=35  x10*y10=840
2 X
2401
• For x11=36, y11=7  x11*y11=252
• For x12=72, y12=7  x12*y12=504
3 X
1715
4 X
343 • The biggest is A=x9*y9=882=2*32*72.
6 245
X K/A=22*51*72=980.
8 • A + K/A = 882+980=1862.
X
49
9 35
X
12 7
18 5
24 1
36
72
 Handle big number
• Multiplication of big number is slow.
• Solution: Use logarithm
– Replace X * Y by log X + log Y
• It reduces the running time.
Association for Cool Machineries
(Part 2)
Problem B
 The problem for part 1
• Give a NxN grid and a sequence of <,>,^,v
• Output X, which is the smallest repetition trail
• Example program: ^v>^<
###### ###### ###### ###### ######
# # # # # # # # # # # # # # #
# # # # # # ^ # # R# # #R # > # # R#
 
# R # # R# # # # # # #
## # ## # ## # ## # ## #
###### ###### ###### ###### ###### The
^ > < v ^ smallest
###### ###### ###### ###### ###### repetition
# # # # # # # # # # #R # # # R# trail is of
# #R # v # # # # #R # ^ # # # < # # # length 4
  
# # # R # # # # # # #
## # ## # ## # ## # ## #
###### ###### ###### ###### ######
 The problem for part 2
• Design
– a 200x200 grid and
– a sequence of <,>,^,v
• such that the smallest repetition trail is of
length > 106
 Idea
• Design a sequence (say, vv<<<^^^>>) and walls that allows the
robot to move up, down, left and right.
• E.g. ## #
#c#
#b# # a#
#a# ## #
# # # b#
# # ## #
# c#

• To make the robot move many steps, we design a difficult map.

• To make the robot move more, append ^v^v…^v to the end of the
sequence.
– E.g. vv<<<^^^>>^v^v^v^v…^v
 A difficult map for 12x12 grid
• For the 12x12 grid, 12
– ab: 5 steps vv<<<^^^>>v^
############
– bc: 6 (=n-6) steps ##l####f####
– ch: 7+6*4 = 31 steps ## k# e#
• cd: 7 (=n-5) steps  (n-11) times # m#j# g#d##
• de: 6 (=n-6) steps ## #i## #c##
• ef: 6 steps # n# # h# ##
• fg, gh: 6 (=n-6) steps  (n-8)/2 times ## # ## # ##
– hi: 10 (=n-2) steps # o# # b#
– in: 31 steps ## ###### ##
# p q r a ##
– na: 6+7+3*6 = 31 steps
### # # # ##
• no: 6 (=n-6) steps
############
• op: 7 (=n-5) steps
• pq, qr, ra: 6 (=n-6) steps  (n-6)/2 times

– ab…qra: 5+6+31+10+31+31=114 steps

• In general, the number of steps is

– 5+(n-6)+[ (n-11)(n-5)+(n-6)+6+(n-6)(n-8)/2 ]*(n-2)/5 + (n-2)(n-7)/5 +
[ (n-6) + (n-5) + (n-6)*(n-6)/2 ],
– which is O(n3).
 Generalize the nxn grid
22
• For the 22x22 grid, vv<<<^^^>>v^v^v^v^v^v^
######################
## #### #### #### ####
– by the previous formula, the ## # # # #
# # # # # # # # ##
robot needs to use 1,526 steps. ## # ## # ## # ## # ##
# # # # # # # # ##
## # ## # ## # ## # ##
# # # # # # # # ##
## # ## # ## # ## # ##
• For the 192x192 grid, # # # # # # # # ##
## # ## # ## # ## # ##
# # # # # # # # ##
– by the previous formula, the ## # ## # ## # ## # ##
# # # # # # # # ##
robot needs to use 1,968,630 ## # ## # ## # ## # ##
# # # # # # # # ##
steps. ## # ## # ## # ## # ##
# # # # # #
## ################ ##
# R##
### # # # # # # # # ##
######################
 Note
• This is just one solution.
• You may find another solution.

• This is similar to convex office.

• The question asks for designing a corner test
case.
• This is an important problem solving
technique that is rarely tested in ICPC.
Apples, Cherries, and Mangos

Problem I
 Problem
• WLOG, assume A ≥ C ≥ M
• We need to arrange them so that adjacent fruits are
different
• Example: A=2, C=1, M=1
 Solution: DP
• V(A, C, M) = no of valid ways to allocate all fruits
• VA(A, C, M) = no of valid ways to allocate all fruits given that the first fruit is Apple
• VC(A, C, M) = no of valid ways to allocate all fruits given that the first fruit is Cherry
• VM(A, C, M) = no of valid ways to allocate all fruits given that the first fruit is Mango

• Base cases:
– VA(1, 0, 0) = 1, VC(0, 1, 0) = 1, VM(0, 0, 1) = 1
– Vw(x, y, z) = 0 if x<0 or y<0 or z<0

• Recursive cases:
– VA(A, C, M) = VC(A-1, C, M) + VM(A-1, C, M)
– VC(A, C, M) = VA(A, C-1, M) + VM(A, C-1, M)
– VM(A, C, M) = VA(A, C, M-1) + VC(A, C, M-1)
– V(A, C, M) = VA(A, C, M) + VC(A, C, M) + VM(A, C, M)

• This solution runs in O(A * C * M)

• It is too slow when the number of fruits is close to 200,000
 Valid arrangement
• WLOG, assume A ≥ C ≥ M
• For any valid arrangement, apples partitions the sequence into A+1 bins
• Every bin must be some cherries or mangos
– Except for the first and the last bins
• Depending on whether first and/or last bins are empty, we have 4 cases
……

^ ^ ^ ^ ^ ^
A+1 bins: ……

^ ^ ^ ^ ^
A bins: ……

^ ^ ^ ^ ^
A bins: ……
^ ^ ^ ^
A-1 bins: ……
 Number of valid arrangements of
A,C,M

……

^ ^ ^ ^ ^ ^
A+1 bins: ……

^ ^ ^ ^ ^
A bins: ……

^ ^ ^ ^ ^
A bins: ……
^ ^ ^ ^
A-1 bins: ……
 Valid arrangement for cherries and
mangos in each bin
• Suppose we don’t have apple
• Assume we have c cherries and m mangos
• To have a valid arrangement, we need
c=m or c=m-1 or c=m+1

Same: c=m or 2 arrangements

C_major: c=m+1 1 arrangement

M_major: c=m-1 1 arrangement

How to distribute cherries and mangos
into k bins?
Final algorithm
Association of Camera Makers

Problem K
 Association of Camera Makers
• Input:
– A set of points (X1,Y1), …, (XN, YN)
– A threshold K
• Output:
– The minimum radius R such that a circle of radius R that covers K
points

• Example: Suppose K=4.

– Ans: R=2  (1,1)

  
(-2,0) (2,0) (6,0)


(0,-2)
 Can we verify if a radius-R circle cover
K points?
• VerifyRadius(R, K) is a function that returns true if a radius-R circle exists
that covers K points
• Suppose there exists a radius-R circle that contains K points
– Then, the radius-R circles of the K points should overlap
– Any point in the overlapping region can be the center of the radius-R circle.
• In particular, we can set any intersecting point as the center of the radius-R circle.

Example: R=4, K=4



 
 



 Idea for VerifyRadius(R,K)
• Let (Xi, Yi) and (Xj, Yj) be any two points
• Let Q and Q’ be the intersecting points of the radius-R circles of (Xi, Yi) and
(Xj, Yj)
• If there exist (K-2) other points whose distances from Q (or Q’) are less
than R, then
– VerifyRadius(R, K) returns true.

Example: R=4, K=4

(Xi, Yi)


 


Q’  
(Xj, Yj)

Q
 VerifyRadius(R,K)
Function VerifyRadius(R, K)
• For every pair of points (Xi,Yi) and (Xj,Yj),
– If the radius-R circles of (Xi,Yi) and (Xj,Yj) overlap,
• Let the intersecting points be Q and Q’
• Check if there are (K-2) points whose distances from Q
(or Q’) are less than R;
• If yes, return true;
• Return false;

• The running time is O(N3);

 Solution
• Note that 0 and 106 are the lower bound and upper
bound, respectively, of the radius R
• This problem can be solved by binary search using
FindRadius(0, 106)

• FindRadius(L, U)
– If (L and U are the same up to 2 decimal place) report L;
– M=(L+U)/2;
– If VerifyRadius(M, K) is true,
• FindRadius(M, U);
– Else
• FindRadius(L, M);
 Still not good enough
• Previous solution runs in
O(N3 log 108) = O(27 N3) time
• It can handle cases where N<1000
• Hence, it can solve 10 out of 16 test cases

• To solve all 16 test cases, please read the paper:

– Jiri Matousek. On enclosing k points by a circle, 1995
– Implementing this algorithm without an accelerating
grid gives an O( N2 log2 N ) solution The full algorithm
with the grid takes O( NK log2 K ) time
 Acknowledgement
(related to question setting)
• Problem setters • Scientific committee (NUS staffs)
– Hubert Teo Hua Kian (Stanford – Associate Professor Chang Ee-
University), Chien,
– Irvan Jahja, – Associate Professor Hugh
– Mark Theng Kwang Hui (SG IOI), Anderson,
– Ranald Lam Yun Shao (SG IOI), – Dr Seth Lewis Gilbert,
– Dr Steven Halim, – Professor Frank Christian Stephan,
– Professor Sung Wing Kin, Ken, – Associate Professor Leong Hon Wai
– Victor Loh Bo Huai (Facebook), • Honorary Judges
– William Gan Wei Liang (SG IOI) – Dr Felix Halim (Google),
• Scientific committee (Tester) – Suhendry Effendy (ACM ICPC
– Harta Wijaya (Garena), Jakarta Regional chief judge),
– Jonathan Irvin Gunawan, – Trinh Tuan Phuong (Quantcast),
– Nathan Azaria – Fredrik Niemelä, Per Austrin, &
Greg Hamerly (Kattis)