Practice 2016-08-20: Solutions for Samara VII (2014)

Post date: Sep 5, 2016 11:06:15 PM

I solved all problems except problem I, with some help from Paul and Andrew.

My code: https://www.dropbox.com/sh/s86b6xf58i9vb6w/AABtLkkIo9eP9UmGqgUJIimRa?dl=0

My solutions are below:

Problem A - Golden Dragons

Problem Summary

You want to find if graph B is a subgraph of the complement of A, up to an isomorphism. There are weird constraints like n >= 3ab where a is max degree of A and b is max degree of B.

Solution

Here's a greedy algorithm that doesn't work by itself:

For each vertex in A (in some arbitrary order), randomly pick any unassigned vertex from B that doesn't cause any conflicts (i.e. its edges in B to assigned vertices in B don't correspond to edges in A).

To make the greedy work, we can simply run it a bunch of times, shuffling the order we do the greedy in each time.

Implementation note: you have to make the greedy reasonably efficient so you can run it as many times as possible under the time limit (use clock() or System.nanotime() to detect when you are near time limit); you can use an adjacency matrix to test if (u, v) is edge in A, and you can keep an extra adjacency list of edges in B involving at least one already assigned vertex, so you reduce the number of edges you are testing.

Complexity

Time complexity: O(n * (n+k))

Alternate Solution

There is also a magical deterministic greedy algorithm that works but we have no idea why. This algorithm is to um start with some arbitrary assignment and greedily swap vertices with conflicts to make it conflict-free without introducing new conflicts.

Problem B - Time of Trial

Problem Summary

You have a bunch of deadlines a_i and a bunch of intervals of length b_i. You want to place b_i such that they don't overlap and that b_i ends before its corresponding deadline a_i. (The blocking spells are essentially decided beforehand, so if some b_i end after a_i it is possible to defeat it by first casting a_i).

Solution

This can be solved by greedy: you schedule the intervals with earliest deadline first. Proof: see CPSC 320 lecture notes.

Complexity

Time complexity: O(n log n)

Problem C - Born for Battle

Problem Summary

You want to find the path that minimizes the second maximum edge on the path.

Solution

When in doubt, try binary searching on the answer! Given a maximum M, you determine if it's feasible by doing a BFS where the state is (curr node, has used an edge with weight > M).

Complexity

Time complexity: O(m log 10^9)

Problem D - Make It Through Your Way

Problem Summary

You have a grid with forest and non-forest nodes. You can only travel in forest during the day and you can travel anywhere during the night. You can only move v steps during day or night.

Solution

WLOG you only have to move at night, so translation: you want to find if it's possible to get from A to B, such that you end in a forest node at most every v steps.

A dubious solution that is surprisingly fast: you do multiple rounds of BFS, each time you expand at most v steps from the forest nodes you reached in the previous BFS round, that you have never started BFS'ing from, and stop when you find the destination or the BFS did not see any new forest nodes.

Complexity

Time complexity: somewhere between O(nm) and O(v^2nm)

Problem E - Blood of Elves

Problem Summary

All stars line up at the same position at t=0. For each star, find the first t >= m such that all stars except that one line up at the same position as t = 0. Stars have orbit periods t_i.

Solution

For the k-th star, the rest of the stars line up every L = LCM(p_1, ..., p_{k-1}, p_{k+1}, ..., p_n) time steps. You can compute L efficiently for every k by using the fact that LCM(a, b, c) = LCM(LCM(a, b), c) to compute the LCM of prefix and suffix subarrays of p_i. Now, given L, you simply output the smallest multiple of L that is >= m and not a multiple of p_k. If it's > 10^9 or L is a multiple of p_k, output impossible. Beware of overflow in LCM.

Complexity

Time complexity: O(n log 10^18)

Problem F - At Hell's Threshold

Problem Summary

You have one template image and a bunch of test images all consisting of points of integer coordinates. You want to test if it's possible to scale and translate the template image to match the test images exactly.

Solution

For each image, compute the bounding box and use that to compute the scale and translation. Then, order the points lexicographically, apply the transformation to the template image, and compare point by point using epsilons. Note that scale and translation can be non-integers.

This works because the lexicographic ordering does not change when you scale and translate.

Complexity

Time complexity: O(nm)

Problem G - Eternal Champion

Problem Summary

Given 3 circles of radius r+1e-4, you want to find if their intersection is non-empty and if so output a point in the intersection.

Solution

There seems to be multiple solutions. My solution is to find if the boundary of the intersection of the first 2 circles intersects the 3rd disk (because of constant radius, the 3rd disk cannot be completely inside). The code archive now has a function called arc_x_disk that is useful for this problem.

Complexity

Time complexity: O(1)

Alternate Solution

Compute the intersections of all pairs of circles and try if any of them is in all 3 circles.

Problem H - A Ballad about the Tear

Problem Summary

You are given a string and a bunch of operations involving changing one character. You want to find the first time the string contains "desmond" as a substring.

Solution

Simply brute force all substrings of length 7 in the initial string, and then after each change of 1 character, brute force all the substrings of length 7 containing the modified character.

Complexity

Time complexity: O(n + m)

Problem I - Magic and Sword

I for impossible??

Problem J - Shards of the Past

Problem Summary

You want to determine the size of a circular doubly-linked list. Each node in the list has a bit that may or may not have been set and you can change it.

Solution

You guess that the size of the list is <= 1, 2, 4, 8, 16, ...; for each guess, you set the starting node to 1 and then traverse the amount you guessed, setting the nodes you visited to 0. If you find a 0 when you go back to starting node, you know the list is <= the size you guessed and you've set all the nodes to 0, so you then set one node to 1 and traverse and count number of steps until you see a 1 again.

Complexity

Time complexity: O(n)

Problem K - Epilogue

Problem Summary

You have 2 list of n integers, a_i and b_i. You have another 2 lists of integers d_j and t_j. For each j, you want to find the minimum i such that a_i > d_j or b_i > t_j and output which of the inequalities is true.

Solution

You can binary search for the minimum i if you compute a "maximum of prefix" array A_i = max(a_0, ..., a_i) as a_i > d_j <=> d_j < A_i <= A_{i+1} <= ...

Complexity

Time complexity: O(m log n)

Problem L - Icy Rider

Problem Summary

You have to assign m numbers a_1, ..., a_m such that they satisfy n restrictions of the form max(a_k1, a_k2, ...) == c where {k1, k2, ...} is subset of [1, m].

Solution

You simply assign a_i = min c for the restrictions that a_i appear in. This ensures <= c, so we just have to check all the restrictions to ensure it's == c.

Complexity

Time complexity: O(nm)