July 28, 2021 Single Round Match 810 Editorials

DistinctStrings

One possible approach is to actually do what the statement seems to ask: generate random strings using the provided charset until we get the correct number of distinct strings. In order to do that, we need to make sure we discard duplicates. One possible solution is to store the already-generated strings in a set. That way we’ll get the duplicates discarded without having to do any extra work.

from random import choice

def random_string(length, letters):
    return ''.join( choice(letters) for _ in range(length) )

def n_random_strings(L, letters, N):
    answers = set()
    while len(answers) < N: answers.add( random_string(L, letters) )
    return list(answers)

The hardest cases for this solution are, maybe surprisingly, the smallest ones: if L=3 and |letters|=10, there are 10^3 = 1000 possible passwords. If we are asked to generate the maximum N=200 distinct passwords, we will almost certainly see some duplicates among our random strings. However, the total number of attempts we’ll need should still be very small: we should expect to be done in fewer than 250 attempts. This is because at any moment the probability that we’ll generate a new password is more than 800/1000 = 4/5, and thus we should get an average of more than four new passwords from every five attempts to generate a new password.

There are also other approaches possible. We are not required to actually generate random strings, we just need to make sure they are distinct.

If we had letters=”0123456789”, we could simply use the first N numbers: e.g., for L=3 we could generate the password suggestions “000”, “001”, “002”, …, “009”, “010”, and so on all the way to N-1.

And once we got here, it should be obvious that we can do the exact same thing with any collection of letters. For example, given letters=”abc” we can start generating all possible strings as follows “aaa”, “aab”, “aac”, “aba”, “abb”, …

What we just did with “abc” is just counting in base-3 — just as if we used “012” instead.

Thus, we can simply iterate over all values from 0 to N-1, represent each in base-S (where S is the number of letters we have) and use the digits as indices into the string of letters we were given.

public String[] generate(int L, String letters, int N) {
    String[] answer = new String[N];
    for (int n=0; n<N; ++n) {
        answer[n] = "";
        int tmp = n;
        for (int l=0; l<L; ++l) {
            answer[n] += letters.charAt( tmp%letters.length() );
            tmp /= letters.length();
        }
    }
    return answer;
}

JoinAClub

The only conceptual step needed is to realize that this is a graph theory problem. If we represent the students as vertices and friendships are edges, the process of building a club corresponds to a general graph traversal: we start in some vertex, and vertices adjacent to the club can be added to the club.

It should be clear that the largest possible club is the largest possible connected component of the given graph. We have to find it and report one valid way of traversing it.

We can now choose one of many different ways how to do that. The most efficient ones are the standard graph traversal algorithm: either BFS (breadth-first search) or DFS (depth-first search). We can implement either of them and modify it to keep track of the order in which vertices are discovered.

However, everything is small and thus we can also afford to be inefficient and have an even easier implementation. For example, we can try starting from each vertex (N possibilities) instead of keeping track of the vertices that were already visited by traversals we already completed.

Below is one possible lazy BFS-like implementation that solves the problem in O(N^3) time.

    int[] constructClub(int N, int[] X, int[] Y, int founder) {
        // convert the input to an adjacency matrix
        boolean[][] friends = new boolean[N][N];
        for (int i=0; i<X.length; ++i) {
            friends[X[i]][Y[i]] = true;
            friends[Y[i]][X[i]] = true;
        }

        // put the founder into the club
        boolean[] inClub = new boolean[N];
        inClub[founder] = true;

        int sz = 1;
        int[] tmp = new int[N];
        tmp[0] = founder;

        // while we still have unprocessed club members:
        // take the next one and add their friends to the club
        for (int i=0; i<sz; ++i) {
            for (int j=0; j<N; ++j) {
                if (inClub[j]) continue;
                if (!friends[ tmp[i] ][ j ]) continue;
                inClub[j] = true;
                tmp[sz++] = j;
            }
        }

        // java annoyance: make an int[] of the correct size and return it
        int[] club = new int[sz];
        for (int i=0; i<sz; ++i) club[i] = tmp[i];
        return club;
    }

    public int[] maximumClub(int N, int[] X, int[] Y) {
        int[] answer = new int[0];
        for (int n=0; n<N; ++n) {
            int[] tmp = constructClub(N,X,Y,(n+2)%N);
            if (tmp.length > answer.length) answer = tmp;
        }
        return answer;
    }

WatchedSnail

Here’s an illustration of how the snail can move by 8*observationDistance in Example 2:

0                                                      100
|-------------------------------------------------------|
  *          *  *          * *          *  *           *
|----------|  |----------|  |----------|  |----------|    
   |----------|  |----------|  |----------|  |----------|

Each of the short intervals is one 20-second observation window. Each asterisk represents a short interval of time in which the snail traversed observationDistance inches.

This is also what the general solution will look like. More precisely:

  • If observationTime = raceTime, all observers watch the snail all the time, and the answer is clearly observationDistance.
  • Otherwise, let X be the largest integer such that X*observationTime < raceTime. The answer is min(observerCount, 2*X) * observationDistance.

Below we give a detailed proof that this solution works.

If observerCount = 2*X, we can divide raceTime into X equally long intervals. The length of these intervals is strictly greater than observationTime, but at most equal to 2*observationTime. Each interval will get two observers: one starting at its beginning, one ending at its end. In each of the X intervals the snail can travel 2*observationDistance inches: one observationDistance close to the beginning and the other close to the end.

If observerCount > 2*X, we do the same and just duplicate some observers.

If observerCount < 2*X, each observer can have their individual segment when nobody else watches the snail, and thus the snail can clearly do observerCount * observationDistance total distance, which is clearly optimal. (Constructing one valid collection of observation intervals can be done by placing one observer at the beginning if their count is odd and then placing the other pairs just as above, but now each pair together covers a longer interval so that the whole race is exactly covered.)

What remains is to show that in the case observerCount > 2*X the above solution is optimal — i.e., that the snail cannot traverse more than 2*X*observationDistance.

Suppose we already have some collection of intervals when the observations took place. Construct a sequence of observers as follows: observer[0] is any observer that starts at time 0, and for each i we look at all observers whose intervals intersect (at least in a point) the interval of observer[i] and we choose observer[i+1] to be the one among them whose observation starts as late as possible. We terminate the process once we reach an observer who observed the end of the race.

Now we claim that if this process saw K observers, the best the snail can do is K*observationDistance. This should be clear by taking any valid solution and shifting all movement to happen as early as possible.

Now, as defined above, let X be the largest integer such that X*observationTime < raceTime. We claim that K must be at most 2*X. To see why, note that observer[2i+2] must start strictly later than observer[2i] ended. This implies that observer[2*X] would begin strictly later than X*observationTime, and therefore end strictly later than (X+1)*observationTime — which we know to be greater than the end of the race.

IcelandRingRoad

Clearly we never want to maintain all N road segments, as maintaining any N-1 leaves the whole country connected. This is what sometimes actually happens in winter on Iceland. If one of the segments is blocked due to some disaster, you drive around the island if you really have to.

Once we choose one road segment that won’t be maintained, each pair of towns has only one path left between them, and thus everyone’s travel path is fixed.

This would give as a valid-but-too-slow solution in something like O(N(P+N)), maybe with an extra logarithm if we sort: iterate over all segments of the road, and for each segment s construct all the paths forced by segment s being blocked and compute the length of their union.

What remains is speeding up this solution using some data structures: more precisely, a segment tree. In each node of the segment tree we’ll store two things: the total length of the union of the paths within its subtree, and the number of times the entire interval represented by its subtree is covered by a path. When adding a new path that covers the interval completely we increment the counter, when removing such a path we decrement the counter, and if it decreased to 0, we recompute the length of path union by summing the answers in our children.

We can start our search by trying to block the segment between towns 0 and N-1. This gives us a collection of intervals, and we are interested in the length of their union. We can just insert all of them into the segment tree and then ask the root.

Now, what happens if we move the blocked segment to the next one — the road between 0 and 1? The paths that contained this segment will now flip. E.g., instead of the path from 0 to 6 we will have a path from 6 to N. (Vertex N is the same as vertex 0 but in the segment tree it’s easier if we treat it as a completely new vertex. Thus, our segment tree will have at least 2N leaves.)

This observation is easily generalized. Each time we move the blockage to the next road segment x-(x+1), we remove each path x-y from our collection and instead add a new path y-(x+N).

As we move the blockage around the ring road, each path will get flipped twice. Using the segment tree, each flip can be processed in O(log N) time. This gives us the final time complexity O(N + P*log N).

ToddlerToy

This is an actual toy. For actual toddlers (and a bit older kids, too).

And even though moving stuff around until you get to a solution is reasonably easy and a kid can get it done, it turns out that formulating a simple algorithm to solve this puzzle is anything but simple. As advertised before the round, the actual challenge in this problem lies mostly in implementing a good algorithm — more precisely, in coming up with an algorithm that is as clean and as simple as possible, so that we can survive its implementation.

This is a skill that’s often neglected in algorithm competitions. We all love the problems that are about big ideas, and once you get the correct big idea, you are rewarded by having a quick and easy solution. But once in a while it’s a good thing to flex another muscle group and try thinking “Okay, I know some ways how to solve this task, but can I make the solution more elegant? Get rid of as many special cases as possible?” In corporate world, the best engineers often have a negative contribution to the code base of a project when measured in the number of lines of code added. This problem is one of those that lets you practice this skill.

The reference solution is using two operations. The first of these is “rearrange a column”. In order to do that, we move all three pegs out: one to one side, the other two to the other. (Another way of doing this step is moving each of them into one of the other three columns.) And then we can return them back in any order we like.

The other operation is “move the top of column X into row Y of column Z”. In order to do this, we move out as much of column Z as needed (two pegs to the buffers on the very right and left, the third one, if needed, to the top of a column other than X and Z), we move the top of column X into its desired space, and then we return the other pegs back into the empty spots arbitrarily.

Using these two operations we can solve the puzzle as follows: for each column, for each row from bottom to top:

  • if we have an incorrect color here and the color we want somewhere higher in the column, rearrange the column to bring it here (without disturbing what’s already correct below)
  • if all available copies of the correct color are in other columns, rearrange one such column to bring the color to the top, then use the other prepared operation to bring the color to where we want it

This solution is guaranteed to solve any puzzle within ~800 moves. Can you do significantly better? Sure you can 🙂


misof


categories & Tags


UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close

Sign up for the Topcoder Monthly Customer Newsletter

Thank you

Your information has been successfully received

You will be redirected in 10 seconds