British Algorithmic Olympiad 2024

Question 4. Colour Codes

A

The input is an array of 7 non-negative integers c; sum(c) is the number $n$ of letters in the colour code. It is the case that some of the letters could be repeating as in the example given.

To generate permutations straight insertion is a method that easy to code (and understand). If the string is $\tt{RRYB}$ we can pick the first character in the sequence. The one element array $\begin{array}{|c|}\hline \tt{R} \\ \hline \end{array}$ has two insertion points: before and after. However in this case both insertion points generate exactly the same permutation namely $\begin{array}{|c|c|}\hline \tt{R} & \tt{R} \\ \hline \end{array}$. As a general rule, if at an insertion point $i$, the character we are inserting is the same as the array element at that insertion point, we can skip the insertion. We can summarise the procedure using the following Python code: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
code = list(input("Enter color code:"))     # RRYB
x = code.pop(0)
perms = [[x]]                   # one color generates a single permutation
while code:
    x = code.pop(0)
    cp = perms.copy()           # copy current version of permutations
    for p in cp:
        perms.append([x]+p)     # we can always append x to the left ...
        for i in range(len(p)):
            if x == p[i]:       # ... but not at an insertion point where x repeats 
                pass
            else:
                perms.append(p[slice(0,i+1)]+[x]+p[slice(i+1,len(p)+1)])
        perms.remove(p)         # we have generated new permutations using p       
                                # so we can delete it from permutations list
del cp
print(perms)                    # [['B', 'Y', 'R', 'R'], ['Y', 'B', 'R', 'R'], 
                                # ['Y', 'R', 'B', 'R'], ['Y', 'R', 'R', 'B'], 
                                # ['B', 'R', 'Y', 'R'], ['R', 'B', 'Y', 'R'], 
                                # ['R', 'Y', 'B', 'R'], ['R', 'Y', 'R', 'B'], 
                                # ['B', 'R', 'R', 'Y'], ['R', 'B', 'R', 'Y'], 
                                # ['R', 'R', 'B', 'Y'], ['R', 'R', 'Y', 'B']]
print(len(perms))               # 12

The running time for this example was 29.7 μs ± 2.91 μs. If we had used a code like $\tt{ROYGBIV}$ the running time for all 5,040 permutations would be 10.9 ms ± 687 μs. For the extreme of $\tt{R}^{\small 4}\tt{O}^{\small 4}\tt{Y}^{\small 4}\tt{G}^{\small 4}\tt{B}^{\small 4}\tt{I}^{\small 4}\tt{V}^{\small 4}$ there are \[ \frac{28!}{4!4!4!4!4!4!4!}=66,475,579,247,327,250,000 \] permutations it would take (using 1 μs per run) 843,171 years to run the calculation.

Although the code shown above generates all permutations they are not in lexicographic order. We could use sorted to do this but it might not be acceptable. Alternatively we could write our own sorting method or use a permutation method that produces them in lexicographic order.

If the code given was $\tt{RRYB}$ we would start with $\tt{BRRY}$ and then generate the next permutation. This is a bit like counting where we start with 1 and then count 2, 3 and so on. The difference here is that we do not know how to count (permutations)! We can tell that 10 is the tenth number in the sequence $1,2,3,\ldots,100$ but if we are given $\tt{RYBR}$ we have no idea where is it in the list of all permutations of $\tt{RRYB}$.

To understand how to count the permutations of $\tt{RRYB}$ we first must develop a cycle for the first letter. There are a total of 12 permutations. If we choose B as the first letter (we always work in lexicographic order) the remaining letters are $\tt{RRY}$; there are $3!/(2!1!)=3$ permutations with these letters. We therefore have 3 permutations with B as the first letter. If we choose R as the first letter, the remaining letters are $\tt{BRY}$ and there are $3!/(1!1!1!)=6$ permutations with these letters. Finally if we choose Y as the first letter there are 3 permutations with Y as the first letter. So the permutation cycle is \[ \underbrace{ \begin{array}{|c|c|c|c|} \hline B & \phantom{B} & \phantom{B} & \phantom{B} \\ \hline \end{array} }_{\text{3 times}} \rightarrow \underbrace{ \begin{array}{|c|c|c|c|} \hline R & \phantom{B} & \phantom{B} & \phantom{B} \\ \hline \end{array} }_{\text{6 times}} \rightarrow \underbrace{ \begin{array}{|c|c|c|c|} \hline Y & \phantom{B} & \phantom{B} & \phantom{B} \\ \hline \end{array} }_{\text{3 times}}. \] If we were told to generate the 5th permutation we would know that it must start with R. Alternatively, if we were given $\tt{RYRB}$ we would at least know its somewhere between 4 and 9.

So lets say that we need to find what is the exact position of $\tt{RYRB}$. With the last three letters $\tt{YRB}$ we can generate the following cycle: \[ \underbrace{ \begin{array}{|c|c|c|} \hline B & \phantom{B} & \phantom{B} \\ \hline \end{array} }_{\text{2 times}} \rightarrow \underbrace{ \begin{array}{|c|c|c|} \hline R & \phantom{B} & \phantom{B} \\ \hline \end{array} }_{\text{2 times}} \rightarrow \underbrace{ \begin{array}{|c|c|c|} \hline Y & \phantom{B} & \phantom{B} \\ \hline \end{array} }_{\text{2 times}} \] Since Y is the second letter, $\tt{RYRB}$ must be somewhere between $3+2+2+1=8$ and $3+2+2+2=9$. Given that the last two letters are $\tt{RB}$ the correct answer is 9.

We can reverse this procedure to find the 9th permutation of $\tt{RRYB}$. Since first letter B generates a cycle of 3 permutations and first letter R a cycle of 6, the first letter must be R. The difference between 9 and 3 is 6 so we are looking for the 6th permutation of letters $\tt{RYB}$. B generates 2 and R another 2 so the second letter must be Y ($9>3+2+2$). We are left with $\tt{RB}$; $\tt{RYBR}$ is the 8th permutation so $\tt{RYRB}$ is the 9th permutation.

We can distill this methodology in the following function: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def uperms(code):   # number of permutations for letter code
    uc = [code.count(x) for x in sorted(set(code))]
    p = m.factorial(sum(uc))
    for x in uc:
        p = p / m.factorial(x)
    
    return p

code = 'RRYB'                  # code is a string of letters
n = 9                          # retrieve nth permutation
seq = []                       # seq starts as an empty array
def permi(code,n,seq):          
    if len(code)==1:           # if code has just one letter
        seq.append(code[0])    # just add it to letter sequence
        return seq             # and return nth permutation 
    else:    
        ul = sorted(set(code))      # unique set of letters (sorted)
        ntotal = 0
        for l in ul:                # for all possible first letters
            temp = list(code[:])    # generate shallow copy
            temp.remove(l)          # remove first letter (in alphabetic order)
            nperms = uperms(temp)   # number of permutations of remaining letters
            if n>ntotal and n<=nseqs+ntotal:   # if n is within current cycle ...
                seq.append(l)                  # we found the (current) letter
                return permi(temp,n-ntotal,seq) # now move on to the remaining letters
            else:                                
                ntotal = ntotal + nperms        # .. otherwise move to next cycle

The benefit from writing a function that returns the nth permutation is that it also can be used to enumerate all permutations given a set of letters. We simply can write a for loop that generates permi(code,1,seq) , permi(code,2,seq) etc. The advantage of this approach is that instead of watching our computer freeze as the algorithm tries to generate permutation 66,475,579,247,327,240,192 for $\tt{R}^{\small 4}\tt{O}^{\small 4}\tt{Y}^{\small 4}\tt{G}^{\small 4}\tt{B}^{\small 4}\tt{I}^{\small 4}\tt{V}^{\small 4}$ we can instead type 

1
2
3
4
perm = []
code = 'RRRROOOOYYYYGGGGBBBBIIIIVVVV'
n = uperms(list(code))-10 
print(''.join(permi(code,n,perm)))

and (after about 944 μs) we get $\tt{YYYYVVVVRRRROOOOGBBBGGIIIBIG}$.

B

We are given a color code of length $m$ and have a choice of $n$ different colors. Lets denote the number of color codes as $F(n,m)$; given a color choice for one of the digits of the color code we can either use all $k$ colors for the remaining $m-1$ digits where $1 \leq k \leq n$. Therefore \[ F(n,m)=\sum_{k=1}^n F(k,m-1). \] If $m=1$ (color code with only one digit) then $F(n,1)=n$ (we simply have one color code per color). This setup allows us to write the following simple code to generate the number of color codes: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def F(n,m):  # n: number of colors , m: colour code length
  if m==1:
    return n
  elif n==0 or m==0:
    return 0
  else:
    sum = 0
    for k in range(1,n+1):
      sum = sum + F(k,m-1)
    
    return int(sum)

print(F(7,6))   # 924

Comments

Post a Comment

Popular posts from this blog

CSAT 1

Image
Test Section A 1. You have a card of 10cm by 10cm. What is the largest volume in cm 3 of a box (without a lid) that can be obtained by cutting out a square of side x from each corner and then folding the flaps up? We can obtain an idea of the solution by looking at the following diagram: The box will have a base (marked in red on the diagram) with area $(l-2x)^2$ and height $x$. Therefore the volume of this box will be \begin{equation*} V=(l-2x)^x. \end{equation*} To maximize the volume first calculate \[ \dv{V}{x}=-4(l-2x)x+(l-2x)^2 \] using the product rule $d(u\cdot v)=du \cdot v + u \cdot dv$. Solve for $\dv*{V}{x}=0$ to find a (potential) maximum. If we assume that $x\neq l$ (a reasonable assumption since $x=l/2$ creates a nothing box) then \begin{align*} -4(l-2x)x+(l-2x)^2& =0 \\ l-2x-4x & = 0 \\ x & = \frac{l}{6}. \end{align*} To check that this is i...
Read more

Poor man's Daletskii-Krein

Image
Consider a second-order, symmetric tensor $A$ whose components $\def\R{\mathbb{R}}{A^j}_i \in \R$. We know that such a tensor has an eigen decomposition \begin{equation} \label{eigendecomp} A = V \Lambda V^\top \end{equation} where $V$ is an orthonormal, second-order tensor and ${\Lambda^j}_i=\lambda^j \delta^j_i$ ($\lambda^i$ is the $i$th eigenvalue of $A$). One corollary of (\ref{eigendecomp}) is \begin{equation} \label{An} A^n = V \Lambda^n V^\top . \end{equation} A function $f:\R \to \R$ that is analytic at $x=0$ is equal to its Maclaurin series \begin{equation} \label{maclaurin} f(x) = \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!} x^n \end{equation} where $f^{(0)}(0)=f(0)$ and $f^{(n)}(0)=\eval{\dv[n]{f}{x}}_{x=0}$. If we define \begin{equation} \label{def-fA} f(A):= \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!} A^n \end{equation} then $f(A)$ is also a second-order, sy...
Read more

PAT 2022

Image
1. What is the total resistance of the circuit ? 2. For which values of $x$ is $\qty(24-14x -3x^2)^{-1}$ positive? The $-1$ exponent does not change the sign. We can factorise $24-14x -3x^2$ as $(-3x+4)(x+6)$ which is positive either if $x < \frac{4}{3}, x > -6$ or if $x > \frac{4}{3}$, $x < -6$. The second condition cannot hold so we have to go with (D). 3. Molecules of oxygen in the atmosphere absorb solar radiation in bands centred at about 80 nm, 650 nm and 1000 nm. In which parts of the electromagnetic spectrum are these absorption bands? Picture from tikz.net The visible spectrum is in the very narrow band from 380 nm (violet) to 750 nm (red) so 650 nm is in the visible spectrum in the red zone. $1000 \ {\rm nm}=10^{-6} \ {\rm m}$ which is right at the edge of infrared. Finally $80 \ {\rm nm}= 0...
Read more