Practice 2016-07-16: Solutions for BAPC 2011

Post date: Sep 5, 2016 10:11:09 PM

Here is my solution sketch. Posted here for a more permanent record.

My code: https://www.dropbox.com/sh/aip77j9snwy42nq/AAB60RyfFQu2GDO4juwhNBNba?dl=0

Problem A - Popping Balloons

Problem Summary

You are given a bunch of balloons (circles in 2D) and you want to fire minimum number of shurikens to pop all of them (draw minimum number of lines from origin to stab all circles).

Solution

Each balloon gives an angular interval where a line would pop it. Thus you have a bunch of angular intervals and you want to find minimum number of places to stab all of them.

In any optimal solution we can wiggle any line until it hits the end point of an interval, so let's only consider end points as possible places to stab. Let's try all the possible places to place our first line.

Once we picked our first line, we can proceed to remove all intervals that it intersects. This breaks circularly overlapping intervals and reduces the problem to the linear case.

For the linear case, we can sort intervals by their end points and then greedily choose to place the next line at the end point of the next interval that's not removed.

The argument goes like this: given any optimal solution, it must have some line going through the interval that ends first. Since all other intervals end later, it will only help if we move this line to the end of the interval. Now we remove all intervals stabbed by this line and repeat the same argument again. Do this enough times and we transform any optimal solution into our greedy solution.

Complexity

Run time: O(n^2) or O(n^2 log n)

Problem B - Quick out of the Harbor

Problem Summary

You want to find the shortest path from starting cell to the boundary cell. Each cell has cost 0 (if it's a dot) or d (if it's a @). It costs 1 to move to neighbor cell.

Solution

All costs are non-negative. Standard Dijkstra applies.

Total of moving to next cell is 1 if it's a dot and d+1 if it's a @.

Complexity

Run time: O(hw log hw)

Problem C - Finding the Treasure

Problem Summary

You are given a bunch of islands (points in 2d). You are given a bunch of island pairs ai and bi such that that if you look from the treasure island you can see ai to the left of bi and the angle between them is < 180 degrees. You have to find all possible candidates for the treasure island.

Solution

Each pair of island defines a line and restricts candidates to one side of the line. Thus if you put all the lines together you will form a convex envelope or polygon of the feasible area. My algorithm first builds this envelope and then test every single island to see if it's inside.

Building the envelope

We can build the upper hull and lower hull separately. If treasure island must be above line, then line is in lower hull; if it must be below line, then line is in upper hull. To build the lower hull, we can vertically flip all the lines and then use the same code for upper hull, so WLOG I will only describe the upper hull case.

In the upper hull, slope decreases as we move from left to right. Sort all lines by decreasing slope. If there are parallel lines we keep the lowest one as that will exclude the other ones. This phase is O(n log n)

Add the first line to the hull. For each new line after, we linearly search backwards from the last line we added to find which line segment in hull it intersects while removing all the lines we skipped along the way and insert the new line. We can do this easily by also keeping a list of vertices on the hull and find the two adjacent vertices that are on different sides of the new line. Each line is pushed and popped only once so this phase is O(n).

Filtering the islands

For each island we test if it's below the upper hull and above the lower hull. The test is simple: binary search on the vertices to find the two adjacent vertices that the island is in-between, then test if the island is strictly above (lower hull) or below (upper hull) the line. There are n islands and binary search is log n, so O(n log n).

Complexity

Run time: O(n log n)

Problem D - Bad Wiring

Problem Summary

You have n <= 100 lights, some are on and some are off. You are given parameter d <= 15 and n light switches, i-th switch changes the (up-to) 2d+1 lights in [i-d, i+d]. You want to find minimum number of moves to turn off all lights.

Solution

First, we notice that you only want to flip each switch at most one time. Observe that only d+1 switches 0, ..., d affect light 0. Let's brute force by trying all <= 2^16 possible ways of turning the first d+1 switches that will turn the first light off.

After deciding what to do for switches 0 to d, the only switch left that will affect the next light (light #1) is switch #d+1, so there's only one possible way to use switch d+1: flip it if light #1 is on, don't flip it if it's already off. The same goes for switch d+2, d+3, ..., n-1. We sequentially flip these switches from left to right as necessary and then see if all lights are turned off in the end and count how many we flipped. The answer is minimum count of all tries that ended up with all lights turned off.

Complexity

Run time: O((2d+1)n 2^d)

Problem E - Undercover Pirate

Problem Summary

You are given a balance and n objects, all of which have the same weight except one, who has different weight (but you don't know if it's heavier and lighter). You can ask the judge to put some objects on both sides of the balance and tell you which side is heavier or if they are the same weight. You can ask the judge at most ceil(log_3 (2n+3)) times and you want to determine which object is different and whether it's heaver or lighter than the rest of the objects.

The sample input gives you a big hint by showing you what to do for the n = 12 case.

Solution

Initial case

Initially you divide the objects into 3 groups of roughly equal size and weigh groups 1 and 2.

If they are equal, then you know group 1 and 2 are good and bad one is in group 3 -> apply case 2.

If they are not equal then you know e.g. group 1 is heavier/lighter than group 2 -> apply case 4.

Example: n = 12, AAAA BBBB ????, 3 moves

Weigh AAAA vs BBBB

GGGG GGGG ???? -> case 2 on ????

HHHH LLLL GGGG -> case 4 on HHHH LLLL

(G = good, H = heavy, L = light)

Case 2: you don't know if the bad one is heavier or lighter but you know some other ones are good.

If you have k moves left then you weigh 3^(k-1) (or the whole group if it's less than that) with equal numbers of good ones.

If they are different then you know whether it's heavy or light -> apply case 3.

If they are equal then you know it's in the ones you didn't weigh -> apply case 2.

Example: n = 13, ????????? ????, 3 moves

Weigh ????????? vs. GGGGGGGGG

Equal -> case 2 on ????

Left heavy -> case 3 on ?????????, bad = heavy

Right heavy -> case 3 on ?????????, bad = light

Case 3: you know the bad one is heavy or light. Divide into 3 equal groups, weigh the first two. If equal, recurse on the third group. Otherwise you know which of first two groups are bad (as you know if it's heavy or light) so recurse on the bad one.

Example: n = 9, AAA BBB CCC, bad = heavy, 2 moves

Weigh AAA vs. BBB

Equal -> case 3 on CCC

Left heavy -> case 3 on AAA

Right heavy -> case 3 on BBB

Case 4: you know one group heavier than other. Suppose you have k moves left.

Case 4a: If one group has >= 2* 3^(k-1) then weigh 3^(k-1) of them (e.g. heavy) on both sides. If equal -> case 4 or 3 on remaining. If unequal -> recurse case 3 on wrong one as you know bad one is (e.g. heavy).

Example: n = 8, HHHHHH LL, 2 moves

Weigh HHH vs. HHH

Equal -> case 3 on LL, bad = light

Left heavy -> case 3 on HHH (left side), bad = heavy

Right heavy -> case 3 on HHH (right side), bad = heavy

Case 4b: fill out left and right side with equal # of H's as many as possible, then fill up with equal # of L's as many as possible until each side is 3^(k-1). If equal -> case 4 or 3 on the rest. If unequal, then we recurse case 4 with heavy on heavy side and light on light side.

Example: n = 26, 13H 13L, 3 moves

Weigh 6H3L vs. 6H3L

Equal -> case 4 on 1H7L

Left heavy -> case 4 on 6H3L (6H from left, 3L from right)

Right heavy -> case 4 on 3L6H (3L from left, 6H from right)

Complexity

Run time: O(log n)

Problem F - Ultimate Finishing Strike

Problem Summary

In a room, you are given starting position and position of enemy. You want to move in a straight line, bouncing off the walls exactly b times, before finally hitting your enemy (you can fly over your enemy multiple times in your path). You want to find all possible ways of doing this that minimizes the total distance traveled.

Solution

Observe that bouncing off a wall = going straight into an adjacent room with reflected coordinates. If we initially go up and right, bounce horizontally p times and vertically q times, then this is equivalent to going in a straight line to a room that is "p rooms to the right and q rooms up". The room is reflected horizontally if p is odd, and vertically if q is odd.

In other words, in this super grid of rooms, the constraint is |p| + |q| = b. All such rooms lie on the edge of a diamond in this grid and there are max(1, 4b) of them. We try all of them, for each destination room we figure out the global xy coordinates of the enemy. We then take minimum of total distance traveled which is reduced to straight line distance.

Complexity

Run time: O(B)

Problem G - Doubloon Game

Problem Summary

You are given a stack of S coins. You and your opponent play a game where at each turn you can remove exactly 1, k, k^2, ... coins as long as enough are available. You start first. The one who takes last coin wins. You want to find if it's possible to win and if so the minimum number of coins to take to win.

Solution

A simple brute force is to compute dp[S] = min { k^i | dp[S - k^i] > 0 }. Since S can be 10^9 this will TLE. However you will begin to see a pattern...

k = 1: 0 1 0 1 0 1 0 1...

k = 2: 0 1 2 0 1 2 0 1 2...

k = 3: 0 1 0 1 0 1 0 1...

k = 4: 0 1 0 1 4 0 1 0 1 4...

k = 5: 0 1 0 1 0 1 0 1...

k = 6: 0 1 0 1 0 1 6 0 1 0 1 0 1 6...

If k odd: each moves changes parity, so you win if S is odd as you can change from odd to even (e.g. get to 0 = even) but not even to even. You remove 1 coin as your first move.

If k even: you win if S % (k+1) is odd or k. If it's odd you remove 1 coin, if it's == k you remove k coins.

The reason this works is that 1, k, k^2, k^3, ... = -1 or 1 under mod k+1. Thus, if you give opponent state S where S % (k+1) is even and != k, then whatever they do it will be come odd or k under mod k+1.

Complexity

Run time: O(1)

Problem H - Walking the Plank

Problem Summary

You have to simulate pirates going from pirate ship to commercial ship, take cargo, come back from commercial ship to pirate ship, put down cargo, repeat until all cargo taken and last pirate returns to ship. Each of the 4 actions take some time >= 1.

Only one pirate can move between the ship at any given time. If both ships have pirates queuing up, commercial ship side goes first.

Queue on pirate ship is ordered by arrival-at-queue time (earlier first), then by time taken on pirate ship to place cargo (slower first).

Queue on commercial ship is ordered by arrival-at-queue time (earlier first), then by time taken on commercial ship to grab cargo (slower first).

Solution

There are only ~400k events because there are only 100k pirate-trips. We can simulate this directly as long as we jump from event to event quickly and don't simulate every time tick. Use priority queues and sets to do this efficiently.

Complexity

Run time: O(n log n)

Problem I - Parking Ship

Problem Summary

You have a bunch of pirate homes (points) and pirate ships (intervals) and you want to place as many pirate ships in front of their owner's homes (each interval has a home point, you want to place intervals such that you don't overlap and you maximize the number of intervals contain their home point).

Constraint: captain's ship is centered on his home. This just divides the problem into two separate instances: one to the left of captain and one to the right.

Solution

WLOG assume we are to the right of the captain.

To know whether we can place j ships using ships from the first i pirates, we can try placing j ships using ships from the first i-1 pirates, or first place j-1 ships using ships from the first i-1 pirates ensuring it doesn't overlap home of ith pirate, and then place ith ship in front of ith pirate.

dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + len[j] if dp[i-1][j-1] <= x[i])

= minimum coordinate of last ship if we place j ships in front of their homes using ships from first i pirates.

Complexity

Run time: O(n^2)

Problem J - Treasuring Map

Problem Summary

Given an integer that is not necessarily perfect square, n = a^2, you want to find if there are integers b and c that satisfy a^2 + b^2 = c^2, and if so output the least pair sorted lexicographically (i.e. minimum b).

Solution

n = c^2 - b^2 = (c-b)(c+b)

We can try all possible integer values for c-b, of which there are a <= 10^4.5 choices. Having chosen c-b, we check if c+b is integer, then we compute c and b and check if they are integer.

Complexity

Run time: O(sqrt(n))