Practice 2016-08-27: Solutions for Universidade de São Paulo ICMC 2016

Post date: Sep 5, 2016 11:21:11 PM

A fairly straightforward contest. I encourage everyone to implement the more interesting problems.

My code: https://www.dropbox.com/sh/q83a43tcx265emj/AACIMFPQPGKlt15_2SZzqIGla?dl=0

My solutions are as shown below:

Problem A - Giant Snail Maze

Problem Summary

You want to find the shortest path from the center to the outermost circle in a graph of N concentric circles with Q >= N radial line segments connecting them.

Solution

Simply construct the graph and run Dijkstras. Constructing the graph may take some implementation effort. First you iterate through all the "openings" and add 2 vertices for each opening: one on the (circular) rail track inside (or the exact center if it's an opening on the innermost wall) and one on the rail track outside and add an edge connecting them. Then for each rail track you add edges between adjacent vertices on the circle.

Complexity

Time complexity: O(Q log Q)

Problem B - Martian Sunrise

Problem Summary

Given a sequence of N symbols out of an alphabet of size 21, and M sets of 7 symbols, you want to cut this sequence into as few blocks as possible such that each block is a subset of the union of one/two of the sets of 7 symbols that you are given.

Solution

The solution is to scan left to right and greedily make each block as big as possible. To test if a block is possible you can brute force every pair (repeats allowed) of the sets of 7.

Complexity

Time complexity: O(21 * M^2 * N)

Problem C - Sleep Buddies

Problem Summary

Given N subsets of a set with size <= M, you want to compute the number of pairs of subsets (A, B) such that |A intersect B | / |A union B | >= k (a given real number in [0, 1]).

Solution

The observation is that M <= 10 so there's only 2^M <= 1024 possible distinct subsets. We can "group" subsets that are exactly the same together so we simply have to brute force over all pairs of the 2^M possible subsets. If A and B are different and meet criteria, we add count(A) * count(B), otherwise we add count(A) * (count(A)-1) / 2. Make sure if you count (A, B) you don't double count (B, A) as well. Also beware of integer overflow.

Complexity

Time complexity: O(N + 2^(2*M))

Problem D - Interstellar Love

Problem Summary

Given a string Z, define sequences of suffix, A = first M suffixes of Z ordered lexicographically and B = the first M suffixes of Z ordered by descending length. You want to find the longest subsequence of A such that its concatenation equals the concatenation of some subsequence of B.

Solution

Let's imagine building up the string twice, in parallel, one with strings in A (call this S) and one with strings in B (call this T). We can adapt the following strategy: if S is longer than T, then we choose some strings from B to tack onto T, making sure they match the positions in S; similarly for T longer than S.

We observe that when we are building up S and T, the only part that matters is the "extra" part after we've chopped off the shorter of S and T. We also observe that this extra part is also a suffix! This is because we always "tack on" to the shorter string.

These observations suggests the following dp with up to 100000000 states:

dp[i][j][k][s] =

s == 0: the longest solution after we've used up to the first i strings in A and the first j strings in B and the string T is longer than S by k

s == 1: same as above, except string S is longer than T by k

The base case is we've used up all the strings in A and B.

The recursive case for s == 0 involves trying to add A[i] to S (i.e. look at dp[i+1][j]), and for s == 1 trying to add B[j] to T (i.e. look at dp[i][j+1]).

WLOG let's explain the s == 0 case (as s == 1 is similar):

To determine whether we can add A[i] to S, we must test it matches the suffix of length k as much as possible (i.e. to the end of the shorter of the two). We need to do this in O(1) so we have to precompute a longest-common-prefix array lcpA[i][k] = LCP of the i-th string of A and the suffix of length k of Z.

A suffix array (available in code archive) is an algorithm/data structure that can let you compute A (i.e. sort all suffixes) and compute LCP very quickly. Since N <= 5000 you can probably think of some other way but whatever you do, do NOT try the stupid O(MN^2) method of pre-computing the LCP array as it will likely be too slow.

Complexity

Time complexity: O(N log^2 N + M^2 * N)

Problem E - Mars Explorer

Problem Summary

You have a 1D landscape of straight lines up or down. There are rocks. You have a carrying capacity defined by a simple formula dependent on the slope. You start at x = 0 and you want to move right, collect as many rocks as possible, and come back to x = 0.

Solution

WLOG we should move as far right as possible with empty load, then collect rocks on our way back since we have to come all the way back anyways. The carrying capacity is given by M <= P / s where s = dy/dx >= 0 is the slope of the segment (if s < 0 there's no limit). Actually this number is not very big: P * dx / dy <= 500 * 1000 / 1 = 500000. Furthermore, all (<= 100) rocks and the empty load are integers. This means we can do a subset sum dp: dp[i] = the possible load sizes after we've seen the i-th rock and gone to the end of its segment, on the way back.

Complexity

Time complexity: O(max(dx)/min(dy) * P * R).

Problem F - Bandejao

Problem Summary

You have K types of utensils and (N+1) of each type. You want to divide these utensils into N+1 piles such that all piles are of equal size and each pile contains only utensils of 1 type. Determine if this is possible.

Solution

Output if (N+1)%k == 0.

Complexity

Time complexity: O(1)

Problem G - Job List

Problem Summary

You want to process queries of these types:

1. add event: move item X to the top of the queue at some time t (add if X did not exist in queue at time t)

2. add event: delete item X from the queue at some time t

3. query the top or second top element of the queue at some time t

Solution

The solution is to keep a list of events and whenever you have a query for the queue, you re-simulate the events starting with an empty queue in order of time until the desired time t. The input size is small enough that you can do this. You can implement the queue with a linked-list or a balanced BST to support the "move to top" operation efficiently.

Complexity

Time complexity: O(Q^2)

Problem H - Reporting on Mars

Problem Summary

Given an array of N bits, you want to find the minimal number of bits to flip such that every subarray of length k has an even number of 1 bits.

Solution

Let's suppose we've decided what to do with the first k bits and we've fixed it such that the first k bits contain an even number of 1's. Now we want to fix the rest of the array. Do we have any choice? No! If A[0] == 0 then A[k] == 0, otherwise when we move from window [0, k-1] to [1, k] we will gain a 1 and make the number of 1's odd. Similarly if A[0] == 1 then A[k] == 1 because we have to replace the "lost" 1 when we move from [0, k-1] to [1, k]. In other words, we've concluded that in any solution, A[i] = A[i+k] = A[i+2k] = ...

Thus we simply have to decide what to do for the first k bits and then replicate that for the rest. Notice since we have to set A[i], A[i+k], A[i+2k]... to the same thing, we should set it to the majority (i.e. if there are more 1's we set all of them to 1) since cost = # bits that are different from desired. Now this gives us the minimal number of bits to flip to make A[i] = A[i+k], so either all blocks of k have even # of 1's or they have odd # of 1's. If we get the latter case, that means for the first k bits we have to flip one of them - we flip the one that costs the least to do so (i.e. where the difference between # 1's and # 0's is the smallest).

Complexity

Time complexity: O(N);

Problem I - Lazy Painting

Problem Summary

Given grid of size N x M. You want to simulate painting rectangles of size H x W with the following rule: for each unpainted cell on the left edge, BFS from that cell inside the H x W rectangle and paint all the cells you reach.

Solution

In fact you can pretty much simulate like that, provided you keep track for each cell the next unpainted cell "below" so that you don't waste time iterating over painted cells on the edge of the rectangle you want to paint. Ask Paul for code.

On the other hand you can take advantage of the fact that all rectangles are of the same size. This means, in particular, for each column you paint, you only paint over at most a single unpainted interval. For each column you store a set of disjoint intervals of unpainted cells and you paint from left to right column by column. In this case painting is simply interval union. Also you have to keep track of where you painted in the previous column so that you don't paint unreachable cells.

Complexity

Time complexity (mine): O(min(QW log Q, NM log Q))

Problem J - The Keys

Problem Summary

Given a set of independent discrete random variables S = {X1, X2, ...} each uniformly distributed over integers in [1, K], and given a sequence of N of random variables selected from S (with repeats): X_k1, X_k2, ..., X_kn, find the expected number of adjacent pairs that are different.

Solution

Let Yi = 1 if (X_k_i != X_k_{i+1}) and 0 otherwise, then we are asked to find E[Y1 + Y2 + ... + Y_{n-1}]. Because E[X+Y] = E[X] + E[Y], we can compute E[Y1], E[Y2], ... separately and add them together.

Since the X's are independent, P(X_ka != X_kb) == 0 if ka == kb, and (K-1)/K otherwise. Thus, tl;dr, output (K-1)/K * number of doors that are different from their right neighbors.

Complexity

Time complexity: O(N);

Problem K - Dire, Dire Docks

Problem Summary

Given N points on the plane you want to draw N line segments connecting them such that no two line segments cross, all points are connected, segments start and end at some (different) points, and each point is connected to no more than 4 segments.

Solution

One solution is to first do a "zig zag" across, connecting all points in lexicographic order, giving you connectedness in N-1 line segments. Then, choose two points to connect for the extra edge. It's easy to show that if 2 points lie on the same vertical line, we can then connect one of them to its neighbor with different x, and if all points have different x, then it's possible iff they are not all colinear, in which case you can connect 2 points that are separated by 1 point in the middle in the "line graph" you drew.

Complexity

Time complexity: O(N)