Louis Abraham's Home Page

The Twelve Labors of GSA Ultra 2018

19 Aug 2018

On July 27th, my friend Victor asked me if I was participating in GSA Ultra. Of course, I had forgotten and had other plans but there was still time so I gave it a shot.

I was really surprised by the diversity of the problems, and I really liked the fact that this contest was only in Python. Although it is the leading language in the industry, and my favorite one, it is notably underused in algorithm contests.

The input was not read from a file, but instead presented as arguments to a function, and the pythonic use of tuples shows that the team behind GSA Ultra genuinely likes Python.

The originality of this contest is that it features 12 problems whose answers fill a crossword-ish grid of numbers instead of passing through tests. However, bigger tests are hidden and ensure you wrote performant code. I don’t know if it is a bug or a feature, but I think some exceptions were silently ignored, and I fixed what I thought caused an error only because the overall running time seemed suspiciously fast to me.
Overall, I think this “weak supervision” recreates the real-life challenge of having to put a code on production in the real world where anything can go wrong.

Because the challenges were genuinely interesting, I decided to publish my analysis and solutions.

Table of contents

1 Down: “Having a ball”

Statement

You are given $N$ labeled boxes and $N$ $(1 \le N \le 10^4)$ balls labeled $1$ to $N$ where each box contains exactly one ball. The $i^{th}$ box contains ball $i$.

You want to generate as many different configurations as possible by swapping the balls present in the boxes. A swap consists of choosing two boxes, say $x$ and $y$, and putting the ball present in box $x$ in box $y$ and vice versa. One configuration is considered different from another if at least one ball is in a different box.

The list of possible swaps you can perform is represented by $M$ pairs of integers $(x_i, y_i)$ where $1 \le M \le 10^5$, denoting that you can make a swap between boxes $x$ and $y$ if $(x, y)$ or $(y, x)$ is present in these $M$ pairs. You can apply a permitted swap as many times as you like.

Write a function that takes the following inputs:

and outputs the number of different configurations achievable. Since the answer could be huge, output the answer modulo $10^9 + 7$.

For example, the output of $\textrm{solution(3, ((1, 2),))}$ would be $2$, since the two possible configurations are $[1, 2, 3]$ and $[2, 1, 3]$ (which can be formed by swapping the balls in first two boxes in the initial configuration).

Analysis

It is clearly a counting problem on permutations. More precisely, it asks the cardinal of the permutation set generated by a set of swaps. Using the cycle decomposition, we observe that it is possible to permute all elements of a cycle (proof by induction). It is then clear that the answer is \(\Pi_{c \in cycles} (\#c)!\).

From a formal point of view, the cycles are the transitive closure of the “permutability” relation, or equivalently, from a graph theory point of view, the cycles are the connected components of the graph of this relation.
We now have reformulated the problem in a classical algorithm problem, the connected components, and my favorite method for this when the graph is not oriented is the union-find datastructure.

The complexity is about $\mathcal{O}(N + C * M)$ where C is a small constant (less than 5) depending on the inverse Ackerman function.

Code

from math import factorial
from collections import Counter
from functools import partial, reduce
from operator import mul

MOD = 10**9 + 7


def find(t, a):
    if t[a] != a:
        t[a] = find(t, t[a])
    return t[a]


def union(t, a, b):
    t[find(t, b)] = find(t, a)


def solution(n, c):
    *t, = range(n)
    for a, b in c:
        union(t, a-1, b-1)
    co = Counter(map(partial(find, t), range(n)))
    return reduce(mul, map(factorial, co.values()), 1) % MOD

2 Down: “Flower power”

Statement

Anna is visiting a botanical garden and notices a row of $N$ beautiful flowers ($3 \leq N \leq 2000$). The colour of each of the flowers is \(\textrm{yellow}\), \(\textrm{red}\) or \(\textrm{blue}\). Anna says that a subsequence of contiguous flowers is “super-colourful” if both of the following conditions are satisfied:

For instance, the subsequence \(\textrm{(red, red, blue)}\) is not super-colourful as \(\textrm{yellow}\) does not appear. Nor is \(\textrm{(red, red, blue, yellow, yellow)}\) as \(\textrm{red}\) and \(\textrm{yellow}\) appear the same number of times. However, \(\textrm{(red, blue, red, red, yellow, yellow, red)}\) is super-colourful.

Even if two flowers have the same colour, a careful observer will know that they are still two different flowers. Two subsequences of contiguous flowers are said to be “different” if they start or end at different flowers.

Write a function that takes as input a string $S$ of length $N$. Each character of $S$ is $`Y\textrm’$, $`R\textrm’$ or $`B\textrm’$. The $i^{th}$ character of $S$ describes the colour of the $i^{th}$ flower in the row: the characters $`Y\textrm’$, $`R\textrm’$ and $`B\textrm’$ denote $\textrm{yellow}$, $\textrm{red}$ or $\textrm{blue}$ respectively. Your function should compute the number, $C$, of different super-colourful subsequences of contiguous flowers there are in the entire row of flowers, and return $10000 + C$.

Analysis

Even if there is probably a dynamic algorithm in linear time, the structure of the problem (in particular the second condition) would IMO make it complicated. The constraint on $N$ is sufficiently low for a $\mathcal{O}(N^2)$ algorithm to be practical. The rest is a simple question of implementation.

Code

from itertools import accumulate


def solution(s):
    n = len(s)
    Y = [0] + list(accumulate(c == 'Y' for c in s))
    R = [0] + list(accumulate(c == 'R' for c in s))
    B = [0] + list(accumulate(c == 'B' for c in s))

    def issc(i, j):
        s = [A[j] - A[i] for A in (Y, R, B)]
        return all(s) and len(set(s)) == 3
    ans = sum(issc(i, j) for i in range(n) for j in range(i, n+1))
    return 10000 + ans

3 Down: “Fearful symmetry”

Statement

A string is a palindrome if it reads the same backwards as forwards. For instance, $``cabac”$ and $``beeb”$ are palindromes, but $``abb”$ is not.

Given a string $T$, we define the “score” of $T$ as the length of the longest palindrome that can be constructed by using some of the characters of $T$. For instance, the score of $T = ``abc”$ is 11, corresponding to the possible palindromes $``a”$, $``b”$ or $``c”$. The score of $T = ``aacggg”$ is $5$, corresponding to the palindrome $``gacag”$.

Write a function that takes as input a string $S$ consisting of $N$ characters $(200 \leq N \leq 5000)$, each from the set $\{`a\textrm’, `b\textrm’, `c\textrm’, `d\textrm’, `e\textrm’, `f\textrm’, `g\textrm’\}$. Your function should split $S$ into four non-overlapping pieces such that:

For instance, if $S = “abccaa”$ then the total minimum score is $4$. Spliting $S$ into the four pieces $``abc”, ``c”, ``a”, ``a”$ gives the total score $1 + 1 + 1 + 1 = 4$. It is easy to see that it is not possible to obtain a lower score. Observe that if the string was instead split as $``a”, ``b”, ``cc”, ``aa”$ then the total score would be $1 + 1 + 2 + 2 = 6$.

Analysis

This was a confusing statement.
First of all, the only palindrome property used is that they contain at most one letter with an odd number of occurences, so the score is almost equal to the string length. Because of this, one wants to maximize a new score function: the length minus the statement score. This score is at most equal to 6.
This new score depends only on the characters repartition modulo 2. Since the alphabet size is very small, it is possible to compute this number for any substring with sets operations by simply precomputing the cumulative union modulo 2. It is also very fast to represent the subsets with small integers (between $0$ and $2^7 - 1 = 127$).

Now it is easy to translate this problem into a dynamic programming solution: do one pass per split mark. At pass $i$, compute the maximum score with $i$ marks for the string ending at each position. It sounds like a quadratic algorithm, but you have a trick: instead of maximizing over the history of positions, maximize over the history of subsets. It is possible because the score of the last piece depends only on the subset it delimits, which depends only on the subsets of the bounds.

The final complexity is $\mathcal{O}(3 * 2^7 * N)$.

Code

from collections import defaultdict


def diff(i, j):
    return max(0, sum(map(int, bin(i ^ j)[2:]))-1)


def solution(s):
    val = []
    v = 0
    for i, c in enumerate(s):
        c = ord(c) - ord('a')
        v ^= 1 << c
        val.append(v)
    last = val.pop()

    score1 = [None] * len(val)
    for it in range(3):
        maxscore1 = defaultdict(int)
        if it == 0:
            maxscore1[0] = 0
        score2 = []
        for i in range(len(val)):
            s2 = max((diff(val[i], k) + s for k,
                      s in maxscore1.items()), default=None)
            score2.append(s2)
            if score1[i] is not None:
                maxscore1[val[i]] = max(maxscore1[val[i]], score1[i])
        score1 = score2
    return len(s) - max(s + diff(val[i], last)
                        for i, s in enumerate(score1)
                        if s is not None)

4 Down: “Fibonarcos”

Statement

Jimmy’s dangerous “just one more episode” mentality when binge-watching his favourite TV shows has led him to investigate the Fibonacci sequence, a series of numbers in which each number (Fibonacci number) is the sum of the two preceding numbers and first two numbers are $1$ i.e. the series $1, 1, 2, 3, 5, 8, \ldots$

Now, he’s curious which natural numbers can be expressed as the product of powers of Fibonacci numbers only. For example, $5$ (which is just the Fibonacci number $5$), $9$ (which is $3^2$), and $12$ (which is $2^2 \times 3$) can all be expressed as the product of powers of Fibonacci numbers whereas $11$ can’t be. Formally, whether a number is expressible as ${f_1}^{p_1} \times {f_2}^{p_2} \times \ldots$ where $f_i$ is a Fibonacci number and $p_i > 0$, for all $i$.

Write a function that takes two positive integers $L$ and $R$ $(1 \le L \le R \le 10^{18}$, $1 \le R - L + 1 \le 10^6)$ as inputs, and outputs the number of integers in this range (both $L$ and $R$ inclusive) which cannot be expressed as the product of powers of Fibonacci numbers.

For example, the output of $\textrm{solution(3, 9)}$ is $1$, as $7$ is the only integer in the range which cannot be expressed as the product of powers of Fibonacci numbers.

Analysis

This is a really nice problem because it requires good analytical skills to make simple estimations, as the algorithms is tricky and the complexity is not easily expressible.

The first trick is to ignore the bound on $R - L$. By just answering the queries for $L=0$, it makes the problem easier to code. The second trick is to count the numbers that can be expressed as the product of Fibonacci numbers.

This problem is tricky because in general, counting the numbers that can be expressed as the product of the elements of a list is much harder, as even deciding if a number can be expressed like that is hard. It looks like integer programming, which is NP-complete, so I wouldn’t be surprised to know that it is impossible to solve the counting problem efficiently. But what if the numbers of the list are prime? Then the decision problem is trivial, you just have to test that all prime factors are in the list.

Hopefully, the Fibonacci numbers have an interesting property, that is a consequence of Carmichael’s theorem: every Fibonacci number has a prime factor that is not a factor of any smaller Fibonacci number except $1$, $8$ and $144$. And we can just ignore $8$ and $144$ as $8 = 2^3$ and $144 = 2^4 * 3^2$. Thanks to this property, every number can be expressed as the product of Fibonacci numbers (excluding $8$ and $144$) in at most one way.

Bruteforcing the factors would be hard to do (at least with a trivial algorithm), but we can design a nice recursive algorithm. Choose a number $f$ in the list. Divide by each power of $f$, relaunch the algorithm without $f$ on each of these values and sum. Once you wrote the base cases, the algorithm is very simple to code.

The reason the complexity is hard to compute is simply that the number of recursive calls is equal to the answer (no joke). When I wanted to test the complexity, I ended up writing the solution.

I still wasn’t satisfied because my solution ended up taking too long. For example, f(10**18) takes $16$ seconds on my computer. The usual trick to speed up the computations of recursive functions (that cannot work iteratively) is to memoize them. Memoizing all values takes too much memory (for the constraints), but it runs f(10**18) in 4 seconds. A LRU cache shows no improvement for small cache sizes.
What is interesting is that most of the function calls are concentrated on the small values (which is intuitive). I finally decided on the following criterion: memoizing for the small inputs. Calling f(10**18) with the thresholds $10^3$, $10^4$ and $10^5$ fills the dictionnary with $3786$, $19120$ and $98376$ values and returns in $9.1$, $6$ and $4.9$ seconds, so $10^4$ appears to be the sweet spot.

Code

def fibo(n):
    l = []
    a, b = 1, 2
    while b <= n:
        if b not in (8, 144):
            l.append(b)
        a, b = b, a+b
    return l


fib = fibo(10**18)

mem = {}


def f(n, i=len(fib) - 1):
    if (n, i) in mem:
        return mem[n, i]
    nn = n
    if n == 0:
        return 0
    if n == 1:
        return 1
    if i == -1:
        return n >= 1
    ans = 0
    k = fib[i]
    while n:
        ans += f(n, i - 1)
        n //= k
    if nn < 1000:
        mem[nn, i] = ans
    return ans


def solution(l, r):
    return r-l+1 - (f(r) - f(l-1)) + (l == 1)

5 Across: “Recreation through recreating”

Statement

You are given two strings $A$ and $B$ consisting of lowercase characters from the English alphabet. The maximum length of each string is $10^5$.

Your aim is to generate $A$ by concatenating a minimum number of copies of $B$. Before concatenating a copy of string $B$ you can choose to remove any number of characters from that copy.

It is guaranteed that it is possible to create string $A$ using a finite number of copies of string $B$ in this way.

Write a function that takes two strings $A$ and $B$ as inputs, and outputs the minimum number of copies of string $B$ required to make string $A$.

For example, the output of $\textrm{solution(‘xyxy’, ‘xyy’})$ would be $2$. We can generate string $\textrm{‘xyxy’}$ by concatenating two modified copies of $\textrm{‘xyy’}$ as follows:

Analysis

This is an easy problem once you realize you can be greedy: when looking for a character from $A$, just take the next that appears either in the current $B$ or the following.

It is just important to first build a data structure that allows to skip characters and just jump to the right position. index[i][c] is how many characters you have to read starting from position $i$ in $B$ to find character $c$.

Code

def solution(a, b):
    la = len(a)
    lb = len(b)
    index = [[float('inf')] * 26 for _ in range(lb)]
    for i in reversed(range(len(b))):
        c = ord(b[i]) - ord('a')
        index[i][c] = 0
    for _ in range(2):
        for i in reversed(range(lb)):
            for j in range(26):
                index[i][j] = min(index[i][j],
                                  index[(i+1) % lb][j] + 1)
    ans = 0
    i = 0
    for c in a:
        c = ord(c) - ord('a')
        i += index[i][c] + 1
        while i >= lb:
            i -= lb
            ans += 1
    ans += bool(i)
    return ans

6 Down: “Alan and Ada”

Statement

Ada is excited about directed acyclic graphs (DAGs). Today, she’s learning how to topologically sort a DAG. She has written her own version of the algorithm (in pseudocode) as follows:

 1 // Notes:
 2 // "n" is the number of nodes in the DAG
 3 // "edges" is a tuple denoting the edges in the DAG
 4 // the nodes are indexed 1, 2, ... n.
 5 // "[]" denotes an empty array.
 6 // "{}" denotes an empty set.
 7 // "x.append(v)" appends "v" at the end of array "x".
 8
 9 def TopoSort(n, edges):
10     ans = []        // array which will contain the output
11     in_deg = []     // in_deg[i] denotes the number of incoming edges at node i
12     open_nodes = {} // a set of nodes
13
14     // initialize "in_deg"
15     for i = 0 to n-1:
16         in_deg.append(0)
17
18     for each edge (u -> v) in edges:
19         in_deg[v]++
20
21     // add nodes with indegree 0 to the set
22     for i = 0 to n-1:
23         if in_deg[i] == 0:
24             open_nodes.add(i)
25
26     while open_nodes is not empty:
27         u = random value from set open_nodes
28         remove u from open_nodes
29
30         ans.append(u)
31
32         for each edge (u -> v) that begins at node u:
33             in_deg[v]--
34             if in_deg[v] == 0:
35                 open_nodes.add(v)
36
37     return ans

The above algorithm is a randomised algorithm, since in line $27$ we introduce randomness by picking a random element from the set. Because of this, the value of the $\textrm{open_nodes}$ set can be different across different runs of the algorithm on the same input graph.

Ada’s colleague Alan comes along and gives to her a DAG and a set of integers $V = {v_1, v_2, …, v_k}$. He says that he’ll run the randomised algorithm once. Now, he asks Ada to tell him the probability of the $\textrm{open_nodes}$ set being equal to $V$ at any point in the algorithm’s execution. Ada argues that calculating this probability is very difficult, but she can instead tell Alan if the probability is zero or non-zero.

Write a function that takes a tuple of $T$ test cases as input. Each test case is a tuple of:

Your function should output the integer $\sum_{i=0}^{T-1} 2^i \times f(i)$, where $f(i)$ is $1$ if the required probability for the $i^{th}$ index test case is non-zero, else $f(i)$ is $0$. Since the value could be very large, return it modulo $10^9 + 7$.

For example, the output of

\[\begin{align}&\textrm{solution((} \\ &~~~~\textrm{(5, ((1, 3), (2, 3), (3, 4), (2, 5), (5, 4)), (1, 5)),} \\ &~~~~\textrm{(5, ((1, 3), (2, 3), (3, 4), (2, 5), (5, 4)), (1, 2, 5))} \\ &\textrm{))}\end{align}\]

is $2^0 \times 1 + 2^1 \times 0 = 1$. In both test cases the graph has $5$ nodes and $5$ edges.

For the first test case, the initial value of $\textrm{open_nodes}$ is \({1, 2}\). If node $2$ is chosen to be removed, the value of $\textrm{open_nodes}$ would be \({1, 5}\). Hence, there is a non-zero probability of achieving Alan’s value.

For the second test case, the initial value of $\textrm{open_nodes}$ is again \({1, 2}\). The test case necessitates that nodes $5$ and $2$ be simultaneously present in $\textrm{open_nodes}$ at some point in the algorithm’s execution. But in order for node $5$ to be present in $\textrm{open_nodes}$, node $2$ would have to be removed. Hence, it’s never possible to achieve Alan’s value.

Analysis

A DAG defines a partial order. The problem can be restated as deciding whether $K$ forms an antichain of the DAG.

To decide if $K$ is an antichain, let’s try to find a contradiction. A contradiction can only appear if there are two vertices $a$ and $b$ such that $a < b$. Stated in an other way, any vertex must be either smaller or bigger than some elements of $K$, or not in the same connex component. Thus, a contradiction can only appear if there exist a node that is both smaller and bigger than some nodes in $K$.

The problem is solved by a simple graph traversal that labels the nodes as smaller or bigger by propagating the information from $K$, and is solvable in linear time.

Code

def solve(n, E, s):
    forw = [[] for _ in range(n)]
    back = [[] for _ in range(n)]
    for a, b in E:
        forw[a-1].append(b-1)
        back[b-1].append(a-1)
    Q = list(ss-1 for ss in s)
    arr = [None] * n
    for u in Q:
        arr[u] = 0
    while Q:
        u = Q.pop()
        if arr[u] in (0, 1):
            for v in forw[u]:
                if arr[v] is None:
                    arr[v] = 1
                    Q.append(v)
                elif arr[v] in (-1, 0):
                    return False
        if arr[u] in (-1, 0):
            for v in back[u]:
                if arr[v] is None:
                    arr[v] = -1
                    Q.append(v)
                elif arr[v] in (0, 1):
                    return False
    return True


def solution(t):
    return sum(1 << i for i, args in enumerate(t) if solve(*args))

7 Across: “A cryptic crossword clue”

Statement

\[``\textrm{Commercial in side or front of building."}\]

The answer to the above cryptic will be a word in hexadecimal. Write a function that returns the value to the above cryptic, converted to base $10$.Your function does not have to perform any calculation - it can just return an integer literal.

Analysis

Using other numbers in the grid, I bruteforced a Scrabble dictionnary and found the word FACADE.

Code

def solution():
    return int('FACADE', 16)

8 Down: “Barb the builder”

Statement

Barb the builder has been presented with a request to build a house with rectangular rooms.

Now, Barb’s idea is to represent the house as a matrix consisting of $N$ rows and $M$ columns where each cell has unit area. The rows are numbered $1$ to $N$ from top to bottom; columns are numbered $1$ to $M$ from left to right.

Her plan is to create vertical and horizontal intersecting walls in some rows and columns. For example, if we denote empty cells with the character $\texttt{.}$ and a wall block with the character $\texttt{*}$, the following depicts the case when $n=m=5$ and Barb decides to create walls in the $2^{nd}$ and $4^{th}$ rows and similarly for columns:

\[\texttt{.*.*.}\\\\\texttt{*****}\\\\\texttt{.*.*.}\\\\\texttt{*****}\\\\\texttt{.*.*.}\]

This would create rooms of closed areas (consisting of at least one empty cell) and open areas which have at least one open boundary. In the above example, we can see that there is only one room of $1$ area unit.

Now, the client comes to Barb and gives her an integer $K$ and asks Barb to calculate the area of the $K^{th}$ smallest room in the building.

Write a function which takes the following inputs:

and outputs the area of the required room. It is guaranteed that there exists at least one room and that $K$ doesn’t exceed the number of rooms.

For example, the output of $\textrm{solution(5, 5, (2, 4), (2, 4), 1)}$ should be $1$.

The answer into the crossword will be the output of your function for the downloadable input file included with this question (in case you’re curious).

Analysis

After some substractions, the problem can be restated as having two sets $A$ and $B$ of size $N$ and requesting the $k_{th}$ element of the set $P = \{a*b \mid a,b \in A \times B\}$.

A similar question appeared in the Problem B of Google Code Jam Kickstart Round D 2017. You can read the contest analysis (subproblem 2). They describe a solution in time $\mathcal{O}(\log(\textrm{range of answer})*N*\log(N))$.

The important idea is to use binary search on the answer. This technique is very efficient if directly computing the result is hard, but some kind of counting in easier. Given a number $x$, how many elements of $P$ are less than $x$? It appears that if you sort the two arrays and print the grid, the elements less than $x$ will be over an anti-diagonal.

For example, with $A = [\textrm{1,2,3]}$, $B=[\textrm{4,5,6]}$ and $x=11$, I indicated the anti-diagonal with the symbol @:

   1  2  3
 +--+--@@@@
4| 4| 8@12|
 +--+--@--+
5| 5|10@15|
 +--@@@@--+
6| 6@12|18|
 @@@@--+--+

Instead of another binary search like in the Code Jam editorial, it is possible to find this antidiagonal in linear time (just by “walking”).

This gives a solution in time $\mathcal{O}(N\log(\textrm{range of answer}))$. A friend found a very neat solution in time $\mathcal{O}(N\log(N))$ that uses a trick similar to the median of medians, but I’m still not sure about the implementation details so we are glad the problem uses integers.

Code

To avoid the corner cases, I added float('inf') to the lists.

def solution(n, m, r, c, k):
    r = sorted(b-a-1 for a, b in zip(r, r[1:]) if b-a-1)
    c = sorted(b-a-1 for a, b in zip(c, c[1:]) if b-a-1)
    r += float('inf'),
    c += float('inf'),

    def nle(x):
        """number of elements <= x
        """
        ans = 0
        i, j = 0, 0
        while r[i] * c[j] <= x:
            i += 1
        ans += i
        for j in range(1, len(c)):
            while i and r[i-1] * c[j] > x:
                i -= 1
            ans += i
        return ans

    # nle(x - 1) < k <= nle(x)
    # smallest x s.t. k <= nle(x)
    # biggest x s.t. nle(x - 1) < k
    a = 0
    b = c[-2] * r[-2] + 1
    while b-a > 1:
        x = (a+b)//2
        if nle(x - 1) < k:
            a = x
        else:
            b = x
    return a

9 Down: “Truly a mazing mouse”

Statement

You have made a maze for your beloved pet mouse. The maze is divided into $N \times N$ squares of unit size, arranged into $N$ rows and $N$ columns. One of the squares contains your mouse’s goal: a piece of cheese. Each of the squares is of one of the following types:

The mouse starts without any keys. Let the tuple $(i, j)$ denote the square at row $i$ and column $j$. The mouse can move from one square to another only if those two squares share a side, and if all the conditions specific to the destination square (as listed above) are satisfied. The mouse completes the maze when it picks up the cheese.

More formally, if the mouse is at square $(i, j)$, it can move to some of the following squares under the conditions provided above and for the squares which are within the maze: $(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)$. The maze is surrounded by a high wall so that if the mouse is at a corner of the maze, it cannot leave it. Furthermore, the mouse needs exactly one second to move from square to square. The mouse starts from the start square $S$ at time $0$. The mouse moves optimally through the maze.

Write a function that takes two parameters as input: an integer $N$ $(3 \leq N \leq 100)$, which specifies number of rows and of column in the maze, and a tuple $M$.

$M$ is a tuple containing $N$ strings, where the $i^{th}$ string in $M$ represents the $i^{th}$ row of the maze. Each string consists of $N$ characters, with the $j^{th}$ character of the string representing the square in the $j^{th}$ column of the corresponding row. Each character of each string will be from the set $\{`S\textrm’, `.\textrm’, `W\textrm’, `R\textrm’, `G\textrm’, `B\textrm’, `C\textrm’\}$, denoting a square type as described above. It will always be possible for the mouse to complete the maze successfully.

Given this representation of the maze, your function should return the minimum time in milliseconds the mouse needs to complete the maze.

The answer into the crossword will be the output of your function for the downloadable input file included with this question (in case you’re curious).

Example input

20
..R..B.B.B.G.R..W.W.
W.W.W.W.W.W.W.W.W.W.
.W.W.W.W.W.W.W.W.W.W
.R..................
.R..G......B...B....
.R...............G..
.R...........B......
....................
....R.....S.........
................W...
...............W....
.......G......W.....
............WW......
...........W........
..........W....W....
...........W..R.W...
.......C....W.B..W..
.W.W.W.W.W.W.W.G..W.
..WWWRW.W.W...W....W
..GGRBBBB......W....

Analysis

This kind of shortest path problem with some constraint can often be reduced to a shortest path on an extended graph.

Here, instead of looking a shortest path on the graph of the $(i, j)$ coordinates, we look for a shortest path on the graph of the $(keys, i, j)$ where $keys$ represents the keys the mouse has already collected ($8$ possibilities).

We use Dijkstra’s algorithm with a binary heap that runs in time $\mathcal{O}(N\log(N))$. Here, the number of nodes is $N=100*100*8$.

Code

I added walls to handle the border cases.

from collections import defaultdict
from heapq import heappop, heappush


def solution(n, m):
    n += 2
    m = ('W'*n,) + tuple('W'+s+'W' for s in m) + ('W'*n,)
    i, j = next((i, j) for i in range(n)
                for j in range(n) if m[i][j] == 'S')
    Q = [(0, 0, i, j)]
    dist = defaultdict(lambda: float('inf'))
    while Q:
        d, keys, i, j = heappop(Q)
        if keys == 7 and m[i][j] == 'C':
            return d * 1000
        if dist[keys, i, j] <= d:
            continue
        dist[keys, i, j] = d
        if m[i][j] in 'RGB':
            keys |= 1 << 'RGB'.index(m[i][j])
        for ii, jj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if m[ii][jj] != 'W':
                heappush(Q, (d+1, keys, ii, jj))

10 Across: “Horse-chestnutting around”

Statement

Alice and Bob like playing games together. One day, they collect $N$ chestnuts on a pile ($5 \leq N \leq 20000$) and come up with the following game:

For instance, if $N = 7, A = 5, B = 6, X = 4, Y = 3$, the game could proceed as follows:

Notice that in the first move Alice cannot take 1 or 2 chestnuts, as doing so would leave a number of chestnuts divisible by $A$ or $B$. Also, observe that it does not matter that at the start of Bob’s first move, the number of chestnuts on the pile is divisible by $X$ - it only matters whether this is the case at the end of his turn.

Write a function that takes as parameters five tuples \(T^{N}, T^{A}, T^{B}, T^{X}, T^{Y}\). Each tuple has five values and together they represent five rounds of the game that Alice and Bob have played. Specifically, \(T^{N}_{i}, T^{A}_{i}, T^{B}_{i}, T^{X}_{i}, T^{Y}_{i}\) ($0 \leq i \leq 4$) represents the values of $N, A, B, X, Y$ respectively for the $i^{th}$ round.

Your function should return $W + 123$ where $W$ is the number of rounds that Alice won. Assume that rounds are independent and that both players play optimally.

For example, if Alice won in 3 out of 5 rounds, you should return 126.

The answer into the crossword will be the output of your function for the downloadable input file included with this question (in case you’re curious).

Analysis

The game is an impartial game under the normal play convention, thus by the Sprague-Grundy theorem is equivalent to a nimber.

Therefore, when both players play optimally, you can label any state as winning or losing for Alice. Since the base cases are simple, the answer is computed by a recursive function. Because of the memory limitations, a dynamic solution was more appropriate. The answer is computed in time \(\mathcal{O}(N)\).

Code

from itertools import starmap


def dyn(n, a, b, x, y):
    arra = [None] * (n + 1)
    arrb = [None] * (n + 1)
    arra[:4] = False, True, True, True
    arrb[:4] = True, False, False, False
    for k in range(4, n+1):
        arra[k] = max((arrb[k-i] for i in [1, 2, 3]
                       if (k - i) % a and (k - i) % b), default=False)
        arrb[k] = min((arra[k-i] for i in [1, 2, 3]
                       if (k - i) % x and (k - i) % y), default=True)
    return arra[n]


def solution(t_n, t_a, t_b, t_x, t_y):
    return 123 + sum(starmap(dyn, zip(t_n, t_a, t_b, t_x, t_y)))

11 Down: “Squared away”

Statement

John loves mathematics. Yesterday in school he learnt about square integers, and now he can’t stop thinking about them. As a reminder, integer $n$ is “square” if there exists some integer $x$ such that $n = x \times x.$ At some point, John realises that some integers could be described as “almost-square”. An integer is almost-square if it is square after one digit is removed.

For instance, $1231$ is an almost-square integer, as removing the digit $3$ results in $121$ and $121$ is square ($121 = 11 \times 11$). Observe that $20$ and $200$ are almost-square integers as well, as removing 2 from them gives 0 ($0 = 0 \times 0$). However, $1254$ is not almost-square as none of $254,$ $154,$ $124,$ or $125$ is square.

Write a function that takes a single integer input $A$ ($500 \leq A \leq 10000$) and returns the number of almost-square integers $S$ in the range $10 \leq S \leq A$.

The entry into the crossword will be the return value of your function when it is called automatically with input $1234$.

Analysis

A straightforward implementation is sufficient.

Code

def issquare(i):
    return round(i**.5)**2 == i


def isas(n):
    n = str(n)
    return any(issquare(eval((n[:i] + n[i+1:]).lstrip('0') or '0'))
               for i in range(len(n)))


def solution(a):
    return sum(map(isas, range(10, a+1)))

12 Across: “Mission: Demolition”

Statement

You are tasked with demolishing a building and decide to model the distribution of your explosives one-dimensionally as points on a line. The $N$ explosives ($1 \leq N \leq 200$) are described by two tuples $X$ and $R$. For each explosive $i$, integer $X_i$​ ($0 \leq X_i \leq 10000$) is the x-coordinate of the explosive and integer $R_i$​ ($1 \leq R_i \leq 10000$) is its explosive strength.

Once an explosive is detonated it explodes. Explosive $i$ can be detonated in one of two ways:

You will only successfully demolish the building if you detonate all the explosives that have been laid. For the sake of efficiency, you want to find out the minimum number of detonators that must be used in order to detonate all of the explosives.

For instance, if $N = 4$, $X = (2, 6, 7, 10)$ and $R = (1, 3, 2, 5)$ then it suffices to detonate the first and the fourth explosive. Note that detonating the fourth explosive would further trigger the detonation of the second and the third.

Write a function that takes as input the integer $N$, the tuple $X$ and the tuple $R$. Your function should calculate the minimum number, $D$, of denonators that must be used in order to detonate all the explosives and return $D \times 10000$.

You may assume that $R$ and $X$ will both be of length $N$ and that no two elements of $X$ will have the same value.

The answer into the crossword will be the output of your function for the downloadable input file included with this question (in case you’re curious).

Analysis

Obviously, the explosives form a directed graph. If any explosive of a strongly connected component is detonated, all explosives in it will be detonated as well. In this matter, all explosives in a strongly connected component are equivalent for our problem.
If we quotient our graph by this equivalence relation, we obtain the graph of the strongly connected components. I reproduced the following figure and caption from Wikipedia.


A directed graph (blue and black) and its condensation (yellow). The strongly connected components (subsets of blue vertices within each yellow vertex) form the blocks of a partition giving rise to the quotient.

Thus, the answer remains unchanged and we can consider the quotient graph that is a directed acyclic graph. In this kind of graphs, the answer is simply the number of source vertices, or vertices with indegree zero.

The DAG can be computed using Tarjan’s strongly connected components algorithm. The graph has at most $N^2$ edges, thus the complexity is $\mathcal{O}(N^2)$. The last part of the algorithm is linear.

Code

I used the iterative implementation of Tarjan’s algorithm from the library TryAlgo of which I am a contributor.

from tryalgo.strongly_connected_components import tarjan


def solution(n, x, r):
    graph = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if abs(x[i] - x[j]) <= r[j]:
                graph[j].append(i)
    sccp = tarjan(graph)
    color = [None] * n

    for i, l in enumerate(sccp):
        for j in l:
            color[j] = i

    indeg = [0] * len(sccp)

    for i, l in enumerate(graph):
        for j in l:
            indeg[color[j]] += color[i] != color[j]
    return indeg.count(0) * 10000