NCPC 2017

Presentation of solutions
The Jury

2017-10-07

NCPC 2017 solutions

NCPC 2017 Jury

Per Austrin (KTH Royal Institute of Technology)

Pål Grønås Drange (Statoil ASA)

Markus Fanebust Dregi (Statoil ASA/Webstep)

Antti Laaksonen (CSES)

Ulf Lundström (Excillum)

Jimmy Mårdell (Spotify)

Luká² Polá£ek (Google)

Johan Sannemo (Google)

Pehr Söderman (Kattis)

NCPC 2017 solutions

J  Judging Moose
Problem

Classify moose based on their horns.

Some solution (guess the language)

solve(0, 0) :-
!, write('Not a moose').
solve(L, R) :-
type(L, R, Type),
Val is 2*max(L, R),
write(Type), write(' '), write(Val).
type(L, L, "Even") :- !.
type(_, _, "Odd").

Statistics: 347 submissions, 252 accepted, rst after 00:03

Problem Author: Pehr Söderman NCPC 2017 solutions

B  Best Relay Team
Problem

Pick best relay team, given runners' standing and ying start times.

Solution
1 Pre-sort runners by their ying start time

Problem Author: Jimmy Mårdell NCPC 2017 solutions

B  Best Relay Team
Problem

Pick best relay team, given runners' standing and ying start times.

Solution
1 Pre-sort runners by their ying start time

2 Try every runner on the rst leg

Problem Author: Jimmy Mårdell NCPC 2017 solutions

B  Best Relay Team
Problem

Pick best relay team, given runners' standing and ying start times.

Solution
1 Pre-sort runners by their ying start time

2 Try every runner on the rst leg

3 For every choice, ll up with 3 fastest remaining ying start

runners

Problem Author: Jimmy Mårdell NCPC 2017 solutions

B  Best Relay Team
Problem

Pick best relay team, given runners' standing and ying start times.

Solution
1 Pre-sort runners by their ying start time

2 Try every runner on the rst leg

3 For every choice, ll up with 3 fastest remaining ying start

runners

Complexity is O (n log n). Many other solutions are also possible.

Problem Author: Jimmy Mårdell NCPC 2017 solutions

B  Best Relay Team
Problem

Pick best relay team, given runners' standing and ying start times.

Solution
1 Pre-sort runners by their ying start time

2 Try every runner on the rst leg

3 For every choice, ll up with 3 fastest remaining ying start

runners

Complexity is O (n log n). Many other solutions are also possible.

Statistics: 491 submissions, 189 accepted, rst after 00:08

Problem Author: Jimmy Mårdell NCPC 2017 solutions

G  Galactic Collegiate Programming Contest
Problem

There are n teams who solve m problems in an ICPC style

programming contest. After each successful submission, print the
rank of your team.

Solution
1 Maintain a set S: the teams whose score is better than your
team's score. Your rank is |S | + 1.

Problem Author: Antti Laaksonen NCPC 2017 solutions

G  Galactic Collegiate Programming Contest
Problem

There are n teams who solve m problems in an ICPC style

programming contest. After each successful submission, print the
rank of your team.

Solution
1 Maintain a set S: the teams whose score is better than your
team's score. Your rank is |S | + 1.
2 When your team solves a problem, remove all teams with a
worse score from S.

Problem Author: Antti Laaksonen NCPC 2017 solutions

G  Galactic Collegiate Programming Contest
Problem

There are n teams who solve m problems in an ICPC style

programming contest. After each successful submission, print the
rank of your team.

Solution
1 Maintain a set S: the teams whose score is better than your
team's score. Your rank is |S | + 1.
2 When your team solves a problem, remove all teams with a
worse score from S.
3 When another team solves a problem, add it to S if its score
becomes better than your team's score.

Problem Author: Antti Laaksonen NCPC 2017 solutions

G  Galactic Collegiate Programming Contest
Problem

There are n teams who solve m problems in an ICPC style

programming contest. After each successful submission, print the
rank of your team.

Solution
1 Maintain a set S: the teams whose score is better than your
team's score. Your rank is |S | + 1.
2 When your team solves a problem, remove all teams with a
worse score from S.
3 When another team solves a problem, add it to S if its score
becomes better than your team's score.

The amortized complexity of both operations is O (log n).

Problem Author: Antti Laaksonen NCPC 2017 solutions

G  Galactic Collegiate Programming Contest
Problem

There are n teams who solve m problems in an ICPC style

programming contest. After each successful submission, print the
rank of your team.

Solution
1 Maintain a set S: the teams whose score is better than your
team's score. Your rank is |S | + 1.
2 When your team solves a problem, remove all teams with a
worse score from S.
3 When another team solves a problem, add it to S if its score
becomes better than your team's score.

The amortized complexity of both operations is O (log n).

Statistics: 578 submissions, 79 accepted, rst after 00:29

Problem Author: Antti Laaksonen NCPC 2017 solutions

I  Import Spaghetti
Problem

The dependencies form a directed graph, and the task is to nd a

shortest cycle in a directed graph.

Solution
1 Use the FloydWarshall all pairs shortest path algorithm with
diagonals initialized to ∞

Problem Author: Pål Grønås Drange NCPC 2017 solutions

I  Import Spaghetti
Problem

The dependencies form a directed graph, and the task is to nd a

shortest cycle in a directed graph.

Solution
1 Use the FloydWarshall all pairs shortest path algorithm with
diagonals initialized to ∞
2 Afterwards diagonal entry d (u , u ) gives length of shortest cycle
passing through u.

Problem Author: Pål Grønås Drange NCPC 2017 solutions

I  Import Spaghetti
Problem

The dependencies form a directed graph, and the task is to nd a

shortest cycle in a directed graph.

Solution
1 Use the FloydWarshall all pairs shortest path algorithm with
diagonals initialized to ∞
2 Afterwards diagonal entry d (u , u ) gives length of shortest cycle
passing through u.
3 Reconstruct shortest cycle using the distance matrix.

Problem Author: Pål Grønås Drange NCPC 2017 solutions

I  Import Spaghetti
Problem

The dependencies form a directed graph, and the task is to nd a

shortest cycle in a directed graph.

Solution
1 Use the FloydWarshall all pairs shortest path algorithm with
diagonals initialized to ∞
2 Afterwards diagonal entry d (u , u ) gives length of shortest cycle
passing through u.
3 Reconstruct shortest cycle using the distance matrix.

4 Alternatively, run BFS from each vertex v to nd shortest v v

cycle.

Problem Author: Pål Grønås Drange NCPC 2017 solutions

I  Import Spaghetti
Problem

The dependencies form a directed graph, and the task is to nd a

shortest cycle in a directed graph.

Solution
1 Use the FloydWarshall all pairs shortest path algorithm with
diagonals initialized to ∞
2 Afterwards diagonal entry d (u , u ) gives length of shortest cycle
passing through u.
3 Reconstruct shortest cycle using the distance matrix.

4 Alternatively, run BFS from each vertex v to nd shortest v v

cycle.

Complexity is O (n3 ) or O (n(n + m)).

Problem Author: Pål Grønås Drange NCPC 2017 solutions

I  Import Spaghetti
Problem

The dependencies form a directed graph, and the task is to nd a

shortest cycle in a directed graph.

Solution
1 Use the FloydWarshall all pairs shortest path algorithm with
diagonals initialized to ∞
2 Afterwards diagonal entry d (u , u ) gives length of shortest cycle
passing through u.
3 Reconstruct shortest cycle using the distance matrix.

4 Alternatively, run BFS from each vertex v to nd shortest v v

cycle.

Complexity is O (n3 ) or O (n(n + m)).

Statistics: 290 submissions, 52 accepted, rst after 00:30
Problem Author: Pål Grønås Drange NCPC 2017 solutions
E  Emptying the Baltic
Problem

How much water can we drain from a point at the bottom of the
sea?

Solution

Problem Author: Luká² Polá£ek NCPC 2017 solutions

E  Emptying the Baltic
Problem

How much water can we drain from a point at the bottom of the
sea?

Solution
1 Similar to Dijkstra's or Prim's algorithms:

Problem Author: Luká² Polá£ek NCPC 2017 solutions

E  Emptying the Baltic
Problem

How much water can we drain from a point at the bottom of the
sea?

Solution
1 Similar to Dijkstra's or Prim's algorithms:
1 Keep track of tentative depth of each square  upper bound on
the nal water level.

Problem Author: Luká² Polá£ek NCPC 2017 solutions

E  Emptying the Baltic
Problem

How much water can we drain from a point at the bottom of the
sea?

Solution
1 Similar to Dijkstra's or Prim's algorithms:
1 Keep track of tentative depth of each square  upper bound on
the nal water level.
2 At the start, only the drainage point has known depth.

Problem Author: Luká² Polá£ek NCPC 2017 solutions

E  Emptying the Baltic
Problem

How much water can we drain from a point at the bottom of the
sea?

Solution
1 Similar to Dijkstra's or Prim's algorithms:
1 Keep track of tentative depth of each square  upper bound on
the nal water level.
2 At the start, only the drainage point has known depth.
3 In each iteration, pick the square s with the lowest tentative
depth and mark it nal. Update tentative depth of all
neighbours of s .

Problem Author: Luká² Polá£ek NCPC 2017 solutions

E  Emptying the Baltic
Problem

How much water can we drain from a point at the bottom of the
sea?

Solution
1 Similar to Dijkstra's or Prim's algorithms:
1 Keep track of tentative depth of each square  upper bound on
the nal water level.
2 At the start, only the drainage point has known depth.
3 In each iteration, pick the square s with the lowest tentative
depth and mark it nal. Update tentative depth of all
neighbours of s .
Time complexity is O (n log n), where n = w · h is the size of the
grid.

Problem Author: Luká² Polá£ek NCPC 2017 solutions

E  Emptying the Baltic
Problem

How much water can we drain from a point at the bottom of the
sea?

Solution
1 Similar to Dijkstra's or Prim's algorithms:
1 Keep track of tentative depth of each square  upper bound on
the nal water level.
2 At the start, only the drainage point has known depth.
3 In each iteration, pick the square s with the lowest tentative
depth and mark it nal. Update tentative depth of all
neighbours of s .
Time complexity is O (n log n), where n = w · h is the size of the
grid.

Statistics: 296 submissions, 55 accepted, rst after 00:47

Problem Author: Luká² Polá£ek NCPC 2017 solutions

D  Distinctive Character
Problem

Given n bit vectors of length k , nd a bit vector whose minimum

Hamming distance is maximum.

Solution

1 k
There are a total of 2 possible bit vectors.

Problem Author: Antti Laaksonen NCPC 2017 solutions

D  Distinctive Character
Problem

Given n bit vectors of length k , nd a bit vector whose minimum

Hamming distance is maximum.

Solution

1 k
There are a total of 2 possible bit vectors.

2 Create a graph where each node is a bit vector and there is an

edge between two nodes if they dier in a single bit.
(aka the k -dimensional hypercube graph)

Problem Author: Antti Laaksonen NCPC 2017 solutions

D  Distinctive Character
Problem

Given n bit vectors of length k , nd a bit vector whose minimum

Hamming distance is maximum.

Solution

1 k
There are a total of 2 possible bit vectors.

2 Create a graph where each node is a bit vector and there is an

edge between two nodes if they dier in a single bit.
(aka the k -dimensional hypercube graph)
3 Use a single BFS with the n given vectors as sources to nd
the node whose minimum distance is maximum.

Problem Author: Antti Laaksonen NCPC 2017 solutions

D  Distinctive Character
Problem

Given n bit vectors of length k , nd a bit vector whose minimum

Hamming distance is maximum.

Solution

1 k
There are a total of 2 possible bit vectors.

2 Create a graph where each node is a bit vector and there is an

edge between two nodes if they dier in a single bit.
(aka the k -dimensional hypercube graph)
3 Use a single BFS with the n given vectors as sources to nd
the node whose minimum distance is maximum.

Time complexity is O (n + k · 2k )

Problem Author: Antti Laaksonen NCPC 2017 solutions

D  Distinctive Character
Problem

Given n bit vectors of length k , nd a bit vector whose minimum

Hamming distance is maximum.

Solution

1 k
There are a total of 2 possible bit vectors.

2 Create a graph where each node is a bit vector and there is an

edge between two nodes if they dier in a single bit.
(aka the k -dimensional hypercube graph)
3 Use a single BFS with the n given vectors as sources to nd
the node whose minimum distance is maximum.

Time complexity is O (n + k · 2k )
Statistics: 461 submissions, 40 accepted, rst after 00:17

Problem Author: Antti Laaksonen NCPC 2017 solutions

C  Compass Card Sales
Problem

Dynamically keep track of uniqueness values of cards while cards

are being sold o.

Solution

Problem Author: Pehr Söderman NCPC 2017 solutions

C  Compass Card Sales
Problem

Dynamically keep track of uniqueness values of cards while cards

are being sold o.

Solution
1 When card is sold, at most 6 other cards (the 2 adjacent
cards of each color) can change their uniqueness values.

Problem Author: Pehr Söderman NCPC 2017 solutions

C  Compass Card Sales
Problem

Dynamically keep track of uniqueness values of cards while cards

are being sold o.

Solution
1 When card is sold, at most 6 other cards (the 2 adjacent
cards of each color) can change their uniqueness values.

2 For c ∈ {R , G , B }, keep set Sc of cards ordered by angle in

color c.

Problem Author: Pehr Söderman NCPC 2017 solutions

C  Compass Card Sales
Problem

Dynamically keep track of uniqueness values of cards while cards

are being sold o.

Solution
1 When card is sold, at most 6 other cards (the 2 adjacent
cards of each color) can change their uniqueness values.

2 For c ∈ {R , G , B }, keep set Sc of cards ordered by angle in

color c.
3 When selling card, nd the ≤6 aected cards and recompute
their uniqueness values, using fast lookup in the sets Sc .

Problem Author: Pehr Söderman NCPC 2017 solutions

C  Compass Card Sales
Problem

Dynamically keep track of uniqueness values of cards while cards

are being sold o.

Solution
1 When card is sold, at most 6 other cards (the 2 adjacent
cards of each color) can change their uniqueness values.

2 For c ∈ {R , G , B }, keep set Sc of cards ordered by angle in

color c.
3 When selling card, nd the ≤6 aected cards and recompute
their uniqueness values, using fast lookup in the sets Sc .
4 Keep all cards in another ordered set ordered by uniqueness
value for fast extraction of next card to sell.

Problem Author: Pehr Söderman NCPC 2017 solutions

C  Compass Card Sales
Problem

Dynamically keep track of uniqueness values of cards while cards

are being sold o.

Solution
1 When card is sold, at most 6 other cards (the 2 adjacent
cards of each color) can change their uniqueness values.

2 For c ∈ {R , G , B }, keep set Sc of cards ordered by angle in

color c.
3 When selling card, nd the ≤6 aected cards and recompute
their uniqueness values, using fast lookup in the sets Sc .
4 Keep all cards in another ordered set ordered by uniqueness
value for fast extraction of next card to sell.

Complexity is O (n log n) with balanced search trees or similar.

Problem Author: Pehr Söderman NCPC 2017 solutions

C  Compass Card Sales
Problem

Dynamically keep track of uniqueness values of cards while cards

are being sold o.

Solution
1 When card is sold, at most 6 other cards (the 2 adjacent
cards of each color) can change their uniqueness values.

2 For c ∈ {R , G , B }, keep set Sc of cards ordered by angle in

color c.
3 When selling card, nd the ≤6 aected cards and recompute
their uniqueness values, using fast lookup in the sets Sc .
4 Keep all cards in another ordered set ordered by uniqueness
value for fast extraction of next card to sell.

Complexity is O (n log n) with balanced search trees or similar.

Statistics: 105 submissions, 14 accepted, rst after 01:10
Problem Author: Pehr Söderman NCPC 2017 solutions
K  Kayaking
Problem

Assign pool of weak/normal/strong people to 2-person kayaks (of

dierent speed factors) to maximize speed of slowest kayak.

Solution

Problem Author: Ulf Lundström NCPC 2017 solutions

K  Kayaking
Problem

Assign pool of weak/normal/strong people to 2-person kayaks (of

dierent speed factors) to maximize speed of slowest kayak.

Solution
1 Binary search over the answer.

Problem Author: Ulf Lundström NCPC 2017 solutions

K  Kayaking
Problem

Assign pool of weak/normal/strong people to 2-person kayaks (of

dierent speed factors) to maximize speed of slowest kayak.

Solution
1 Binary search over the answer.
2 Check feasibility by greedily assigning people to kayaks
kayaks requiring strong+strong or strong+normal get that
kayaks that can handle weak+weak or weak+normal get that
pair up remaining weaks with strongs and normals with
normals and check if this can make all kayaks fast enough

Problem Author: Ulf Lundström NCPC 2017 solutions

K  Kayaking
Problem

Assign pool of weak/normal/strong people to 2-person kayaks (of

dierent speed factors) to maximize speed of slowest kayak.

Solution
1 Binary search over the answer.
2 Check feasibility by greedily assigning people to kayaks
kayaks requiring strong+strong or strong+normal get that
kayaks that can handle weak+weak or weak+normal get that
pair up remaining weaks with strongs and normals with
normals and check if this can make all kayaks fast enough
Time complexity is O (n log n) for n people.

Problem Author: Ulf Lundström NCPC 2017 solutions

K  Kayaking
Problem

Assign pool of weak/normal/strong people to 2-person kayaks (of

dierent speed factors) to maximize speed of slowest kayak.

Solution
1 Binary search over the answer.
2 Check feasibility by greedily assigning people to kayaks
kayaks requiring strong+strong or strong+normal get that
kayaks that can handle weak+weak or weak+normal get that
pair up remaining weaks with strongs and normals with
normals and check if this can make all kayaks fast enough
Time complexity is O (n log n) for n people.

Statistics: 82 submissions, 23 accepted, rst after 00:46

Problem Author: Ulf Lundström NCPC 2017 solutions

A  Airport Coee
Problem

Find fastest way of walking distance L. At certain points xi we can

choose to get a future temporary speedup (by buying a coee), at
the cost of cancelling any current speedup.

Solution

1 Let S (i ) be best time if we start from i 'th cart.

Problem Author: Johan Sannemo NCPC 2017 solutions

A  Airport Coee
Problem

Find fastest way of walking distance L. At certain points xi we can

choose to get a future temporary speedup (by buying a coee), at
the cost of cancelling any current speedup.

Solution

xi xj L
1 LetS (i ) be best time if we start from i 'th cart.
2 Easy dynamic programming: for each j > i , try buying next
coee at cart j

S (i ) = min S (j ) + Time to go from xi to xj

j >i

Problem Author: Johan Sannemo NCPC 2017 solutions

A  Airport Coee
Problem

Find fastest way of walking distance L. At certain points xi we can

choose to get a future temporary speedup (by buying a coee), at
the cost of cancelling any current speedup.

Solution

xi xj L
1 LetS (i ) be best time if we start from i 'th cart.
2 Easy dynamic programming: for each j > i , try buying next
coee at cart j

S (i ) = min S (j ) + Time to go from xi to xj

j >i

3 Alas, leads to Ω(n2 ) time  too slow!.

Problem Author: Johan Sannemo NCPC 2017 solutions

A  Airport Coee
Problem

Find fastest way of walking distance L. At certain points xi we can

choose to get a future temporary speedup (by buying a coee), at
the cost of cancelling any current speedup.

Solution

xi xj L
1 From each xi , three categories of choice for best next cart xj :
During cooldown, during drinking, and after nishing the coee

Problem Author: Johan Sannemo NCPC 2017 solutions

A  Airport Coee
Problem

Find fastest way of walking distance L. At certain points xi we can

choose to get a future temporary speedup (by buying a coee), at
the cost of cancelling any current speedup.

Solution

xi xj L
1 From each xi , three categories of choice for best next cart xj :
During cooldown, during drinking, and after nishing the coee

2 Before/After drinking: best to pick smallest such j

(get next coee as soon as possible)

Problem Author: Johan Sannemo NCPC 2017 solutions

A  Airport Coee
Problem

Find fastest way of walking distance L. At certain points xi we can

choose to get a future temporary speedup (by buying a coee), at
the cost of cancelling any current speedup.

Solution

xi xj L
1 From each xi , three categories of choice for best next cart xj :
During cooldown, during drinking, and after nishing the coee

2 Before/After drinking: best to pick smallest such j

(get next coee as soon as possible)
3 During drinking: best to pick largest such j
(keep drinking coee as long as possible)

Problem Author: Johan Sannemo NCPC 2017 solutions

A  Airport Coee
Problem

Find fastest way of walking distance L. At certain points xi we can

choose to get a future temporary speedup (by buying a coee), at
the cost of cancelling any current speedup.

Solution

xi xj L
1 Only need to consider three values of j when computing S (i ).

Problem Author: Johan Sannemo NCPC 2017 solutions

A  Airport Coee
Problem

Find fastest way of walking distance L. At certain points xi we can

choose to get a future temporary speedup (by buying a coee), at
the cost of cancelling any current speedup.

Solution

xi xj L
1 Only need to consider three values of j when computing S (i ).
2 Can use binary search over cart positions to nd them in
O (log n) time.

Problem Author: Johan Sannemo NCPC 2017 solutions

A  Airport Coee
Problem

Find fastest way of walking distance L. At certain points xi we can

choose to get a future temporary speedup (by buying a coee), at
the cost of cancelling any current speedup.

Solution

xi xj L
1 Only need to consider three values of j when computing S (i ).
2 Can use binary search over cart positions to nd them in
O (log n) time.
Overall complexity O (n log n).
(Exercise: can be improved to O (n) time.)

Problem Author: Johan Sannemo NCPC 2017 solutions

A  Airport Coee
Problem

Find fastest way of walking distance L. At certain points xi we can

choose to get a future temporary speedup (by buying a coee), at
the cost of cancelling any current speedup.

Solution

xi xj L
1 Only need to consider three values of j when computing S (i ).
2 Can use binary search over cart positions to nd them in
O (log n) time.
Overall complexity O (n log n).
(Exercise: can be improved to O (n) time.)

Statistics: 65 submissions, 7 accepted, rst after 02:50

Problem Author: Johan Sannemo NCPC 2017 solutions
H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 1

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 1
1 Sort all rays and points by angle.

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 1
1 Sort all rays and points by angle.

2 For each point, compare distances to its two neighboring rays

(Use sweep approach or binary search to nd the two rays quickly)

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 1
1 Sort all rays and points by angle.

2 For each point, compare distances to its two neighboring rays

(Use sweep approach or binary search to nd the two rays quickly)
3 Caveat! If using doubles, need to be careful with .
(Turns out, distances can dier by ≈ 10−13 without being equal.)

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 1
1 Sort all rays and points by angle.

2 For each point, compare distances to its two neighboring rays

(Use sweep approach or binary search to nd the two rays quickly)
3 Caveat! If using doubles, need to be careful with .
(Turns out, distances can dier by ≈ 10−13 without being equal.)
4 Can also check this using only integer computations.
(But, despite small coordinates, need 64 bits.)

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 1
1 Sort all rays and points by angle.

2 For each point, compare distances to its two neighboring rays

(Use sweep approach or binary search to nd the two rays quickly)
3 Caveat! If using doubles, need to be careful with .
(Turns out, distances can dier by ≈ 10−13 without being equal.)
4 Can also check this using only integer computations.
(But, despite small coordinates, need 64 bits.)
5 Points with a unique neighboring ray can be immediately
assigned to that ray (if it has capacity left).

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 2
1 For remaining points (having two closest rays) we get a
bipartite matching problem between points and rays.

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 2
1 For remaining points (having two closest rays) we get a
bipartite matching problem between points and rays.

2 Graph is very simple (either a cycle, or a collection of paths)

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 2
1 For remaining points (having two closest rays) we get a
bipartite matching problem between points and rays.

2 Graph is very simple (either a cycle, or a collection of paths)

3 Approach 1: solve using max ow (merging all points with the
same angle into a single node with capacity = #points)

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 2
1 For remaining points (having two closest rays) we get a
bipartite matching problem between points and rays.

2 Graph is very simple (either a cycle, or a collection of paths)

3 Approach 1: solve using max ow (merging all points with the
same angle into a single node with capacity = #points)
1 Time complexity with Ford-Fulkerson is O (p 2 ) where p is the
number of train lines adjacent to some remaining person.

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 2
1 For remaining points (having two closest rays) we get a
bipartite matching problem between points and rays.

2 Graph is very simple (either a cycle, or a collection of paths)

3 Approach 1: solve using max ow (merging all points with the
same angle into a single node with capacity = #points)
1 Time complexity with Ford-Fulkerson is O (p 2 ) where p is the
number of train lines adjacent to some remaining person.
2 However p is hard to analyze. Turns out that
p ≈ max coordinate = 1000, so this approach is fast enough.

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 2
1 For remaining points (having two closest rays) we get a
bipartite matching problem between points and rays.

2 Graph is very simple (either a cycle, or a collection of paths)

3 Approach 2: greedyish solution

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 2
1 For remaining points (having two closest rays) we get a
bipartite matching problem between points and rays.

2 Graph is very simple (either a cycle, or a collection of paths)

3 Approach 2: greedyish solution
1 First cut the cycle anywhere to get a path, solve path with
simple greedy

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 2
1 For remaining points (having two closest rays) we get a
bipartite matching problem between points and rays.

2 Graph is very simple (either a cycle, or a collection of paths)

3 Approach 2: greedyish solution
1 First cut the cycle anywhere to get a path, solve path with
simple greedy
2 Make a second greedy pass to adjust assignment across the
point where we cut the cycle.

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 2
1 For remaining points (having two closest rays) we get a
bipartite matching problem between points and rays.

2 Graph is very simple (either a cycle, or a collection of paths)

3 Approach 2: greedyish solution
1 First cut the cycle anywhere to get a path, solve path with
simple greedy
2 Make a second greedy pass to adjust assignment across the
point where we cut the cycle.
3 Time complexity is O (n log n).

Problem Author: Johan Sannemo NCPC 2017 solutions

H  Hubtown
Problem

Given a set of rays from in 2D (0, 0), and some points, assign max
#points to a ray of minimum angular distance from the point,
subject to ray capacities.

Phase 2
1 For remaining points (having two closest rays) we get a
bipartite matching problem between points and rays.

2 Graph is very simple (either a cycle, or a collection of paths)

3 Approach 2: greedyish solution
1 First cut the cycle anywhere to get a path, solve path with
simple greedy
2 Make a second greedy pass to adjust assignment across the
point where we cut the cycle.
3 Time complexity is O (n log n).

Statistics: 17 submissions, 0 accepted

Problem Author: Johan Sannemo NCPC 2017 solutions
F  Fractal Tree
Problem

Given a huge tree with potentially 100000

230 vertices, nd distances

between pairs of vertices.

Solution

1 A copy of F30 will have at least 230 vertices

(assuming F0 has at least 2 leaves)

Problem Author: Johan Sannemo NCPC 2017 solutions

F  Fractal Tree
Problem

Given a huge tree with potentially 100000

230 vertices, nd distances

between pairs of vertices.

Solution

1 A copy of F30 will have at least 230 vertices

(assuming F0 has at least 2 leaves)

2 If k > 30, only relevant part is bottom-left copy of F30 and the
path to this subtree.

Problem Author: Johan Sannemo NCPC 2017 solutions

F  Fractal Tree
Problem

Given a huge tree with potentially 100000

230 vertices, nd distances

between pairs of vertices.

Solution

1 A copy of F30 will have at least 230 vertices

(assuming F0 has at least 2 leaves)

2 If k > 30, only relevant part is bottom-left copy of F30 and the
path to this subtree.

3 Reduces the problem to k ≤ 30.

Problem Author: Johan Sannemo NCPC 2017 solutions

F  Fractal Tree
Problem

Given a huge tree with potentially 100000

230 vertices, nd distances

between pairs of vertices.

Solution
F0 F2
1

2 3

4 5

a=

1 Representation of vertex a in the big tree:

Problem Author: Johan Sannemo NCPC 2017 solutions

F  Fractal Tree
Problem

Given a huge tree with potentially 100000

230 vertices, nd distances

between pairs of vertices.

Solution
F0 F2
1 1

2 3
2 3

4 5
4 5

a = (5,

1 Representation of vertex a in the big tree:

1 Record sequence (a1 , a2 , . . .) of leaves picked in each copy of
F0 when going from root to a

Problem Author: Johan Sannemo NCPC 2017 solutions

F  Fractal Tree
Problem

Given a huge tree with potentially 100000

230 vertices, nd distances

between pairs of vertices.

Solution
F0 F2
1

2 3

1
4 5
2 3

a 4 5

a = (5, 2,

1 Representation of vertex a in the big tree:

1 Record sequence (a1 , a2 , . . .) of leaves picked in each copy of
F0 when going from root to a

Problem Author: Johan Sannemo NCPC 2017 solutions

F  Fractal Tree
Problem

Given a huge tree with potentially 100000

230 vertices, nd distances

between pairs of vertices.

Solution
F0 F2
1

2 3

4 5
1

2 3

a = (5, 2, 3) 4 5

1 Representation of vertex a in the big tree:

1 Record sequence (a1 , a2 , . . .) of leaves picked in each copy of
F0 when going from root to a
2 Finally add which node a corresponds to in last copy of F0 .

Problem Author: Johan Sannemo NCPC 2017 solutions

F  Fractal Tree
Problem

Given a huge tree with potentially 100000

230 vertices, nd distances

between pairs of vertices.

Solution
F0 F2
1

2 3

4 5

a = (5, 2, 3)

1 Representation of vertex a in the big tree.

2 Can nd this representation in O (k log n ) time using binary
search and precomputation of subtree sizes.

Problem Author: Johan Sannemo NCPC 2017 solutions

F  Fractal Tree
Problem

Given a huge tree with potentially 100000

230 vertices, nd distances

between pairs of vertices.

Solution
1 What is distance between (a1 , . . . , ap ) and (b1 , . . . , bq )?

Problem Author: Johan Sannemo NCPC 2017 solutions

F  Fractal Tree
Problem

Given a huge tree with potentially 100000

230 vertices, nd distances

between pairs of vertices.

Solution
1 What is distance between (a1 , . . . , ap ) and (b1 , . . . , bq )?
2 First remove any common prex
(moving into the same subtree does not aect distance)

Problem Author: Johan Sannemo NCPC 2017 solutions

F  Fractal Tree
Problem

Given a huge tree with potentially 100000

230 vertices, nd distances

between pairs of vertices.

Solution
1 What is distance between (a1 , . . . , ap ) and (b1 , . . . , bq )?
2 First remove any common prex
(moving into the same subtree does not aect distance)
3 Then, when a1 6= b1 , distance is
p q

d ( a1 , b 1 ) + h(a ) + h(b )
X X
i i

i =2 i =2
4 d (a1 , b1 ) = distance between a1 and b1 in F0
(can compute it using a lowest common ancestor (LCA) algorithm)
5 h(x ) = depth of node x in F0

Problem Author: Johan Sannemo NCPC 2017 solutions

F  Fractal Tree
Problem

Given a huge tree with potentially 100000

230 vertices, nd distances

between pairs of vertices.

Solution
1 What is distance between (a1 , . . . , ap ) and (b1 , . . . , bq )?
2 First remove any common prex
(moving into the same subtree does not aect distance)
3 Then, when a1 6= b1 , distance is
p q

d ( a1 , b 1 ) + h(a ) + h(b )
X X
i i

i =2 i =2
4 d (a1 , b1 ) = distance between a1 and b1 in F0
(can compute it using a lowest common ancestor (LCA) algorithm)
5 h(x ) = depth of node x in F0
Statistics: 5 submissions, 0 accepted
Problem Author: Johan Sannemo NCPC 2017 solutions
Random numbers
253 teams

611 contestants

2819 total number of submissions

10 programming languages used by teams

Ordered by #submissions: C++ (1016), Java (865),

Python (763), C (67), C# (65), Haskell (16), Prolog
(9), Scala (8), Go (6), Ruby (4)

438 number of lines of code used in total by the shortest

jury solutions to solve the entire problem set.
(Signicantly smaller than previous years  no killer
problem in terms of implementation this year.)

NCPC 2017 solutions

Random facts
All but two of the problems have near-linear solutions

Exceptions:

NCPC 2017 solutions

Random facts
All but two of the problems have near-linear solutions

Exceptions:
D (Distinctive Character)  O (n + k · 2k ) solution
I (Import Spaghetti)  O (n 3 ) solution.

NCPC 2017 solutions

Random facts
All but two of the problems have near-linear solutions

Exceptions:
D (Distinctive Character)  O (n + k · 2k ) solution
I (Import Spaghetti)  O (n 3 ) solution.

Two weeks ago, 3 people had written solutions to H

(Hubtown). A day later, it had turned out that the 3
solutions were all wrong, with 3 completely dierent bugs, and
that the test case generator had also been buggy.

NCPC 2017 solutions

Random facts
All but two of the problems have near-linear solutions

Exceptions:
D (Distinctive Character)  O (n + k · 2k ) solution
I (Import Spaghetti)  O (n 3 ) solution.

Two weeks ago, 3 people had written solutions to H

(Hubtown). A day later, it had turned out that the 3
solutions were all wrong, with 3 completely dierent bugs, and
that the test case generator had also been buggy.
Two days ago, one of those Hubtown solutions again turned
out to be wrong, more data was added.

NCPC 2017 solutions

Random facts
All but two of the problems have near-linear solutions

Exceptions:
D (Distinctive Character)  O (n + k · 2k ) solution
I (Import Spaghetti)  O (n 3 ) solution.

Two weeks ago, 3 people had written solutions to H

(Hubtown). A day later, it had turned out that the 3
solutions were all wrong, with 3 completely dierent bugs, and
that the test case generator had also been buggy.
Two days ago, one of those Hubtown solutions again turned
out to be wrong, more data was added.

The jury wrote Python solutions for all problems except C

(Compass Card Sales). But mostly in Python 2, which is
faster than Python 3 on Kattis due to using pypy instead of
CPython. The Python solutions are always the shortest (often
by a wide margin).

NCPC 2017 solutions

What now?

Northwestern Europe Regional Contest (NWERC):

November 26 in Bath (UK).
Teams from Nordic, Benelux, Germany, UK, Ireland.

Each university sends up to two teams to NWERC to ght for

spot in World Finals (April 2018, in Beijing, China)

NCPC 2017 solutions