Challenge Problems - 2021 Sem 2, Contest 1

Sports Loans

Statement

Andrew is head of the sports club, and manages the inventory. Part of Andrew’s job is loaning footballs to people, and collecting those footballs once they have been used.

At the start of the day, Andrew has $r$ footballs in stock, and knows that $p+q$ people will approach him over the course of the day. $p$ people will request a football, while $q$ people will return a football. What Andrew does not know is the order in which these people will approach him.

Of course, Andrew wants to be able to give a football to everyone who requests one, when they request one. So for example if the first $r+1$ people want a football, Andrew can’t give a football to the last person.

Andrew wants to know the probability that the above situation does not occur today, in other words the probability that every time someone requests a football, Andrew has one in stock.

Input / Output

Input will consist of three space separated integers, $p, q$ and $r$, as defined in the problem statement. Output should be a single number, the probability that Andrew will always be able to give a football to anyone who requests it. This number should have absolute error less than $10^{-8}$.

Example Run

Input

4 1 3

Output

0.8

Since there is a 20% chance that the “return a football” event occurs before all 4 “request a football” events, which would cause problems.

Hints / Solution

Hint 1

Simulating won’t be enough, because of the sizes of p, q and r. What you should instead do is try to find a general form for the probability, based on p, q, r.

Start by trying to come up with a visualisation of this process in 2-dimensional space. What do good/bad orderings of people look like?

Hint 2

The visualisation we are looking for is one where we begin at point $(r, 0)$, and for each person, we either move to the right 1 unit (person returns a football), or up 1 unit (person requests a football).

A run is then invalid when we cross (not touch) the line $y = x$. For an invalid run, what happens when we flip all points across the line $y = x + 1$ before the intersection?

What is the total number of paths from this new starting point to $(q+r, p)$?

Solution

To handle the easy cases, if $p \leq r$, then the probability is 1 (We can’t possibly run out of footballs). If $ p > r + q$, then the probability is 0 (We can’t possibly handle everyones request). We assume neither of these is the case for the following discussion.

Let’s first view the problem through a different lens, to make the solution a bit more natural. Imagine Andrew is a point on the 2D plane. Whenever a person approaches him to give him a football, he moves one unit in the positive $x$-axis, and whenever a person approaches him to request a football, he moves one unit in the positive $y$-axis.

We can think of this as the $x$-axis representing footballs returned, while the $y$ axis represents footballs taken. Since we start with $r$ footballs, it might make sense to start Andrew at the position $(r, 0)$. Then, when Andrew is on the line $y = x$, we know that Andrew has exactly 0 balls in inventory. Therefore we want to know the probability that Andrew never dips above this line (or equivalently, that Andrew never touches the line $y = x + 1$).

Since any ordering of the $p+q$ people is equally likely, we can simply count all possible distinct paths from $(r, 0)$ to $(r+q, p)$, and the proportion of these paths which sit below the line $y = x+1$ is the probability we want. The number of all possible paths is ${p+q \choose p} = {p+q \choose q}$, since we can just pick the locations of the $p$ (or $q$) people in our ordering.

Now, counting the number of paths that avoid the line is tough, but we can do something similar by finding a bijection between invalid paths and some other collecion.

Rather than considering paths from $(r, 0)$ to $(r+q, p)$, what if we instead started from the same point, reflected on the line $y = x+1$? Then we’d be looking at paths from $(-1, r+1)$ to $(r+q, p)$. Note that every path between these two points needs to touch the line $y = x+1$. Furthermore, we can turn each of these paths into an invalid path from $(r, 0)$ to $(r+q, p)$ in the following way:

Find the first intersection of the path with the line $y = x + 1$ (Some intersection must exist).
Mirror the path along the line $y = x + 1$ before this intersection.

Since $(-1, r+1)$ is the mirrored version of $(r, 0)$, all of these new paths are distinct paths from $(r, 0)$ to $(r+q, p)$. Furthermore, since the original paths hit the line, each of the these mirrored paths also hit the line and are therefore invalid. Hopefully it’s also easy to see that every possible invalid path can be reached via this mirror method.

Therefore, the total number of invalid paths is equal to the total number of any of path between $(-1, r+1)$ and $(r+q, p)$. By the same argumentation as before, there are ${(r+q+1) + (p-r-1) \choose r+q+1} = {p+q \choose p - r - 1}$ possible paths.

Now that we know how many paths there are in total, and how many paths are invalid, we can calculate some probabilities. The probability that Andrew does run into this situation (That we have a bad path) is:

\[P(\text{bad}) = \frac{p+q \choose p - r - 1}{p+q \choose p} = \frac{(p+q)!p!q!}{(p+q)!(p-r-1)!(q+r+1)!} = \frac{\prod^r_{i=0}p-i}{\prod^r_{i=0}q+i+1}.\]

The probability the question asks for is then just $P(\text{good}) = 1 - P(\text{bad})$. Note that the cancellation above is required to fit within precision and time limits, as we can’t compute $p!$ for large enough $p$ within time.

# Read 3 ints
p, q, r = list(map(int, input().split()))
if p <= r:
    print(1)
elif p > r + q:
    print(0)
else:
    p_bad = 1
    for i in range(r+1):
        p_bad *= (p-i) / (q+i+1)
    # Be safe with 10 precision points.
    print(f"{1-p_bad:.10f}")

#include <iostream>
#include <iomanip>

using namespace std;

int main() {

    // p, q can be large, use long long.
    long long p, q, r;

    cin >> p >> q >> r;

    if (p <= r) {
        cout << 1 << endl;
    } else if (p > r + q) {
        cout << 0 << endl;
    } else {
        double p_bad = 1;

        for (int i=0; i<= r; i++) {
            p_bad = p_bad * ((double)(p-i)) / ((double)(q+i+1));
        }

        cout << setprecision(10) << fixed << 1 - p_bad << endl;
    }

    return 0;
}

Optimal Farming

Statement

Amy has just bought a farm in the outback, and wants to start selling tomatoes. Some of the crops in the farm are already tomatoes, but there are others she wants to get rid of and replace with tomatoes.

Amy has employed the help of Square Tomatoes Group™. Amy can pay the group $$s$ to plant an $s \times s$ grid of crops with tomatoes (It doesn’t matter if the existing crop was tomatoes or not, all grid squares become tomatoes. This square can also exceed Amy’s farm). Amy wants to minimise her cost to Square Tomatoes Group™ such that all crops are tomatoes.

Input / Output

Input starts with two integers $1 \leq l, w \leq 30$, the length and width of the farm, separated by space. Input then contains $l$ lines, each containing a string of $w$ characters. Each of these characters represent a grid square in the farm. This square is a tomato crop if and only if the character printed is a T.

Output should be a single integer, the minimum Amy has to pay to fill her farm with tomato crops.

Example Test

Input

3 4
PWTT
TCTT
TTTL

Output

3

Explanation: We can pay Square Tomatoes Group™ $$2$ to plant tomatoes in the top-left 2x2 area, and then $$1$ to plant tomatoes in the final bottom-right square.

Hints / Solution

Hint 1

Note that if every row and column has a square with no tomato, then the answer is rather obvious. The problem only gets interesting when an entire row/column is already tomatoes.

Hint 2

Suppose we don’t go for the easy solution of just using a massive square to cover our farm, and have a cheaper solution. Then one of the rows or columns in the farm must be untouched. How can we recurse from here?

Solution

We will generalise and compute $\text{cost}(x1, x2, y1, y2)$, the cost of converting the rectangle $[x1, x2), [y1, y2)$ all to tomatoes. The question is asking us to compute $\text{cost}(0, w, 0, l)$.

Note that we can always spend $$\text{max}(x2-x1, y2-y1)$ and cover the rectangle, by using a square that exceeds the bounds. Also, note that if a collection of squares overlaps every column of the rectangle, then the cost of planting all of these squares must be at least $x2-x1$, and similarly if every row of the rectangle is overlapped by a square, the minimum cost is $y2-y1$.

With this in mind, suppose there was a cheaper selection of squares that converts this entire rectangle to tomatoes. Then from the logic above, there must be some column or row which is not touched by these planted squares (A column or row that is already all tomatoes). This column/row separates our rectangle in two, and so we can solve the subproblem of $\text{cost}$ on each of these rectangles.

For example, in the input given, we have a $3 \times 4$ rectangle. The easy solution is to cover the entire thing with a $4 \times 4$ square, costing $$4$.

But, column 2 is all tomatoes, so we can solve the subproblem on the left and right hand sides of this column, and see if doing this is cheaper. Continuing along, we find the left subproblem costs $$2$, and the right subproblem costs $$1$, and so the final result is $$3$.

We can achieve this within the time limit with Dynamic Programming.

The recursive definition is:

\[\text{cost}(x1, x2, y1, y2) := \text{min} \begin{cases} (x2 - x1) \times (y2 - y1) &\\ \text{cost}(x1, c, y1, y2) + \text{cost}(c, x2, y1, y2) & x1 < c < x2, \text{column } c \text{ from } y1 \to y2 \text{ all tomato.}\\ \text{cost}(x1, x2, y1, r) + \text{cost}(x1, x2, r, y2) & y1 < r < y2, \text{row } r \text{ from } x1 \to x2 \text{ all tomato.} \end{cases}\]

The base case being that $\text{cost}(x1, x1+1, y1, y1+1) = b$, where $b$ is 0 if it’s a tomato plant, and 1 otherwise. In order to know when an entire segment of a row/column is all tomatoes, we can also use DP, by breaking up each square into individual rows / columns.

For both of these we have $l^2w^2$ values to compute, and each of the values takes $l + w$ operations to compute (In the recursive definition, we might recurse for every row and column in the square). So the total cost is about $30^5 \approx 2 \times 10^7$

import sys
# Maximum recursion for this problem is actually like 60, but better safe than sorry.
sys.setrecursionlimit(10000)

l, w = list(map(int, input().split()))

grid = [input() for _ in range(l)]

# is the rectangle from x1 to x2, y1 to y2 all tomato? (RHS exclusive)
tomato_dp = [[[[None for _1 in range(31)] for _2 in range(31)] for _3 in range(31)] for _4 in range(31)]
def all_tomato(x1, x2, y1, y2):
    if tomato_dp[x1][x2][y1][y2] is not None:
        return tomato_dp[x1][x2][y1][y2]
    if x1 < x2 - 1:
        tomato_dp[x1][x2][y1][y2] = all_tomato(x1, x2-1, y1, y2) and all_tomato(x2-1, x2, y1, y2)
    elif y1 < y2 - 1:
        tomato_dp[x1][x2][y1][y2] = all_tomato(x1, x2, y1, y2-1) and all_tomato(x1, x2, y2-1, y2)
    else:
        # y2 = y1+1, x2 = x1+1.
        tomato_dp[x1][x2][y1][y2] = grid[x1][y1] == "T"
    return tomato_dp[x1][x2][y1][y2]

cost_dp = [[[[None for _1 in range(31)] for _2 in range(31)] for _3 in range(31)] for _4 in range(31)]
def cost(x1, x2, y1, y2):
    if cost_dp[x1][x2][y1][y2] is not None:
        return cost_dp[x1][x2][y1][y2]
    if x1 == x2 or y1 == y2:
        # Empty rectangle.
        return 0
    cur_min = max(x2-x1, y2-y1)
    # Otherwise, there is an empty row/column we can exclude. Simply solve this suproblem.
    for c in range(x1, x2):
        if all_tomato(c, c+1, y1, y2):
            cur_min = min(cost(x1, c, y1, y2) + cost(c+1, x2, y1, y2), cur_min)
    for r in range(y1, y2):
        if all_tomato(x1, x2, r, r+1):
            cur_min = min(cost(x1, x2, y1, r) + cost(x1, x2, r+1, y2), cur_min)
    cost_dp[x1][x2][y1][y2] = cur_min
    return cost_dp[x1][x2][y1][y2]

print(cost(0, l, 0, w))

#include <iostream>
#include <string>

#define FOR(i,j,k) for(int i=j; i<k; i++)
#define MAX(a, b) (a > b) ? a : b
#define MIN(a, b) (a < b) ? a : b
#define MAXN 30

using namespace std;

int l, w;

const int UNKNOWN = -1;

int DP_TOMATO[MAXN+1][MAXN+1][MAXN+1][MAXN+1];
int DP_COST[MAXN+1][MAXN+1][MAXN+1][MAXN+1];
string grid[MAXN+1];

bool tomato(int x1, int x2, int y1, int y2) {
    // Is the rectangle [x1, x2), [y1, y2) already tomato?
    if (DP_TOMATO[x1][x2][y1][y2] != UNKNOWN)
        return DP_TOMATO[x1][x2][y1][y2];
    if (x1 < x2 - 1) {
        // Look at the column x=x2-1 separately
        DP_TOMATO[x1][x2][y1][y2] = tomato(x1, x2-1, y1, y2) && tomato(x2-1, x2, y1, y2);
    } else if (y1 < y2 - 1) {
        // Look at the row y=y2-1 separately
        DP_TOMATO[x1][x2][y1][y2] = tomato(x1, x2, y1, y2-1) && tomato(x1, x2, y2-1, y2);
    } else {
        // We are a 1x1.
        DP_TOMATO[x1][x2][y1][y2] = grid[x1][y1] == 'T';
    }
    return DP_TOMATO[x1][x2][y1][y2];
}

int cost(int x1, int x2, int y1, int y2) {
    if (DP_COST[x1][x2][y1][y2] != UNKNOWN)
        return DP_COST[x1][x2][y1][y2];
    if (x1 == x2 || y1 == y2)
        // Empty rectangle. Possible in the below recursion so just return 0.
        return 0;
    // We can always cover the rectangle by using a big square.
    int cur_min = MAX(x2-x1, y2-y1);
    FOR(c,x1,x2)
        if (tomato(c, c+1, y1, y2))
            // If this column is tomato, then we can try solving the two subproblems instead by removing the column.
            cur_min = MIN(
                cur_min,
                cost(x1, c, y1, y2) + cost(c+1, x2, y1, y2)
            );
    FOR(r,y1,y2)
        if (tomato(x1, x2, r, r+1))
            // If this row is tomato, then we can try solving the two subproblems instead by removing the row.
            cur_min = MIN(
                cur_min,
                cost(x1, x2, y1, r) + cost(x1, x2, r+1, y2)
            );
    DP_COST[x1][x2][y1][y2] = cur_min;
    return DP_COST[x1][x2][y1][y2];
}

int main() {

    cin >> l >> w;
    FOR(i,0,l) {
        cin >> grid[i];
    }

    FOR(x1,0,l+1)FOR(x2,0,l+1)FOR(y1,0,w+1)FOR(y2,0,w+1) {
        DP_TOMATO[x1][x2][y1][y2] = UNKNOWN;
        DP_COST[x1][x2][y1][y2] = UNKNOWN;
    }

    cout << cost(0, l, 0, w) << endl;

    return 0;
}

Repetitive Jugglers

Statement

Alice is the leader of a juggling crew, and they are set to perform a crazy juggling trick.

In this trick, every member of the crew starts off with a different coloured ball. Every member then picks another member of the crew (possibly themselves), let us call that member their receiver.

Then, the trick begins. Every second, every crew member will throw all of the balls they are holding to their designated receiver.

The trick only stops once everyone has the same ball they started with (Note that not always does this trick stop!)

Alice wants to know, given who has chosen who as receiver, whether the game will end, and if so, how many seconds this will take.

Input

Input will consist of two lines.

The first line will contain an integer $n$, the number of members in the juggling crew.

The second line will then contain $n$ space-separated integers. The $i$th integer represents the $i$th crew member’s pick for receiver.

(So we enumerate crew members $1, 2, 3\ldots$, and if the second integer is $1$, that means that crew member $2$ has chosen $1$ as their receiver.)

It is guaranteed that if the trick does stop, it will stop before $10^{15}$ seconds have passed

Output

If the trick will never finish, print $-1$. Otherwise, print the total length of the trick, in seconds.

Example Test

Input

3
2 1 3

Output

2

After 1 second, person 1 and person 2 throw the balls at each other, and person 3 throws the ball to themselves. As such person 1 is holding person 2’s ball, and person 2 is holding person 1’s ball. Person 3 is holding their own ball.

After 2 seconds, the same action occurs, and so everyone is holding their own ball.

Hints / Solution

Hint 1

Since this trick might continue for $10^{15}$ seconds, we cannot simulate it (Especially with large $n$).

We need to figure out ahead of time when this will occur.

Notice that if one person receives 2 or more balls at any point in time, the trick will never end.

Hint 2

Only selections of “receivers” in which every member is the receiver of exactly one member will finish, and they will always finish.

For math inclined individuals, these receivers represent a permutation of the group, and we want to know how many repeated applications of this permutation are needed to take us back to the identity.

We can figure out how long this will take based on cycles that are present in the permutation.

Solution

Note that if any member recieves two juggling balls, then our sequence can never return to how it was. Therefore everyone must recieve a single ball every second. In other words, our $n$ space-separated integers must be a permutation of the numbers $1$ through to $n$. Note that in a permutation, there are multiple distinct cycles of different sizes (For example 1 passes to 3 passes to 7 passes to 4 passes to 1). Notably, everyone in these cycles has their ball every $k$ seconds, where $k$ is the length of the cycle.

Therefore, if we have cycles of length $k_1, k_2, \ldots k_a$, then the first time the entire sequence will repeat must be the least common multiple of these values $k_1, k_2, \ldots k_a$ (The first number $c$, which is divisible by all of $k1, k2, \ldots, k_a$).

So our solution just needs to find each of these cycles, and count their length. Then compute the least common multiple.

In the sample input, we have a permutation with 2 cycles (1 passes to 2 passes to 1, and 3 passes to 3). These cycles are of length 2 and 1 respectively.

Therefore every 2 seconds, members 1 and 2 will have their balls, and every second, member 3 will have their ball. Because of this, the answer is the smallest number which is divisible by 2 and 1 (2).

n = int(input())
# make it 0 -> n-1.
choices = list(map(lambda x: int(x)-1, input().split()))

# Greatest common divisor
def gcd(a, b):
    if b == 0:
        return abs(a)
    return gcd(b, a%b)

# Least common multiple
def lcm(a, b):
    return a * b // gcd(a, b)

# list(set()) will remove duplicates. If no duplicates, then we have a permutation
if len(list(set(choices))) == n:
    # Permutation
    # Find the cycle lengths
    lengths = []
    found = [False]*n
    for x in range(n):
        # Is x not already in a cycle?
        if not found[x]:
            length = 0
            # Search through the cycle.
            cur = x
            while not found[cur]:
                found[cur] = True
                length += 1
                # Move to the next person
                cur = choices[cur]
            lengths.append(length)
    # Print the lcm of all lengths.
    cur_lcm = 1
    for length in lengths:
        # The lcm of a list is simply the pairwise lcm of each element, combined.
        cur_lcm = lcm(cur_lcm, length)
    print(cur_lcm)
else:
    # Not a permutation
    print(-1)

#include <vector>
#include <iostream>
#include <map>

using namespace std;

typedef long long ll;
typedef vector<ll> vll;

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

int main() {

    int n;
    cin >> n;

    vll nums(n);
    for (int i=0; i<n; i++) {
        cin >> nums[i];
        // Make it 0 -> n-1.
        nums[i]--;
    }

    // Check for duplicates
    bool bad = false;
    map<int, int> dup_check;
    for (int i=0; i<n; i++) {
        dup_check[i] = 0;
    }
    for (int i=0; i<n; i++) {
        dup_check[nums[i]]++;
        if (dup_check[nums[i]] > 1) {
            // Someone recieves 2.
            bad = true;
        }
    }
    if (bad) {
        cout << -1 << endl;
    } else {
        vll lengths;
        vll found(n, false);
        for (int i=0; i<n; i++) {
            if (!found[i]) {
                int length = 0;
                int cur = i;
                while (!found[cur]) {
                    found[cur] = true;
                    length++;
                    cur = nums[cur];
                }
                lengths.push_back(length);
            }
        }
        ll cur_lcm = 1;
        for (ll l: lengths) {
            cur_lcm = lcm(cur_lcm, l);
        }
        cout << cur_lcm << endl;
    }

    return 0;
}

Challenge Problems - 2021 Sem 2, Contest 1

Sports Loans

Statement

Input / Output

Example Run

Hints / Solution

Optimal Farming

Statement

Input / Output

Example Test

Hints / Solution

Repetitive Jugglers

Statement

Input

Output

Example Test

Hints / Solution

Further Reading

DataStructureLess Competition 2023 Editorial

Union Find / DSU

Least Common Ancestor (LCA)

Trending Tags