We need to count sequences of $$$n$$$ tens and $$$m$$$ thirties such that at every prefix, the number of tens is at least twice the number of thirties.

Define $$$f(n,m)$$$ as the number of valid sequences with $$$n$$$ tens and $$$m$$$ thirties:

with base $$$f(0,0) = 1$$$.

For $$$n=8$$$, $$$m=4$$$ we compute $$$f(8,4) = 55$$$.
Total sequences are $$$\binom{12}{4} = 495$$$.
Hence probability $$$= \tfrac{55}{495} = \tfrac{1}{9}$$$.

Therefore the final answer is $$$1/9$$$. The required output is $$${1 + 9 = 10}$$$.

Trivial
Easy
Average
Hard

Let $$$A$$$ be the set of elements in $$$L$$$ that were chosen to add $$$1$$$ and $$$B$$$ be the set of elements in $$$L$$$ that were chosen to subtract $$$1$$$ from. Each $$$x \in L$$$ can pair with at most two other elements in $$$L$$$ to sum to $$$26$$$: one in $$$A$$$ and one in $$$B$$$.

However, consider $$$13$$$.
If it was chosen to add $$$1$$$ to, it becomes $$$14$$$. But

has at most one way to be formed: $$$13-1$$$ is not possible because we already added $$$1$$$ to $$$13$$$.
If we did not add $$$1$$$ to $$$11$$$, we lost $$$2$$$ pairs.
If we added $$$1$$$ to $$$11$$$, it could pair up with only $$$13+1$$$, unless we subtracted $$$1$$$ from $$$15$$$, where $$$15-1$$$ can only pair with $$$11+1$$$. Hence we lose another pair here.

Similarly, if $$$13$$$ was chosen to subtract $$$1$$$ from, we also lose $$$2$$$ pairs.

Thus there are at most

total ordered pairs in $$$L$$$ which sum to $$$26$$$, so the answer is

An explicit construction for this is to increase the following by $$$1$$$:

and decrease the following by $$$1$$$:

This was the worked-out example for $$$n = 25$$$.

For general $$$n$$$, the exact same reasoning shows that the maximum number of pairs is

so the probability is

and the expected output is

For $$$n = 2025$$$, the expected output is $$${2 \cdot 2024 + 2025^2 = 4104673}$$$.

Trivial
Easy
Average
Hard

Let’s count the expected number of moves taken in each column.

Case 1: First (left-most) column

We’re picking a random path, so the red dot in the first column can show up in any row with equal probability. The row itself doesn’t really affect the number of paths going forward (since we always have to place $$${5^3}$$$ red dots after this one), so we just compute the average number of moves needed to reach any point in that column.

That’s: $$${\frac{0 + 1 + 2 + 3 + 4}{5} = 2}$$$

Case 2: Any of the middle columns

Same kind of logic as before, but now we look at how far we’d need to move from the previous red dot in the column just before this one.

• If the red dot in the previous column was on the top or bottom row, we again get $$${2}$$$ expected moves (same as Case 1).
• If it was one row away from the top or bottom, then the expected moves come out to: $$${\frac{1 + 0 + 1 + 2 + 3}{5} = \frac{7}{5}}$$$
• And if it was exactly in the middle row, then we get: $$${\frac{2 + 1 + 0 + 1 + 2}{5} = \frac{6}{5}}$$$

Each row in the previous column is equally likely, so we average over all five cases: $$${\frac{2 + \tfrac{7}{5} + \tfrac{6}{5} + \tfrac{7}{5} + 2}{5} = \frac{8}{5}}$$$

So we get $$${\frac{8}{5}}$$$ as the expected moves per middle column.

Case 3: Last (right-most) column

This is basically the same as the first column, just reversed — we’re now going from a red dot in the last column to the top-right corner. So again, expected moves is: $$${2}$$$

Final calculation:

Let’s put everything together now:

• First column: $$${2}$$$
• Middle columns: $$${\frac{8}{5}}$$$
• Last column: $$${2}$$$
• Plus $$${4}$$$ moves to go from column to column

Total: $$${2 + \frac{8 \cdot 3}{5} + 2 + 4 = \frac{44}{5} + 4 = \frac{64}{5}}$$$

So the final answer is: $$${\frac{64}{5}} \Rightarrow 69$$$

Trivial
Easy
Average
Hard

We want to represent the situation as a graph with $$$6$$$ vertices and $$$6$$$ edges.

Note that we cannot have even-length cycles (e.g. a $$$4$$$-cycle), because the corresponding system of equations becomes linearly dependent. For instance, adding the equations from a $$$4$$$-cycle leads to redundancy, so one equation is wasted. Since we need $$$6$$$ independent equations for $$$6$$$ variables, all cycles must be odd.

Also, a cycle must exist (a tree on $$$6$$$ vertices has at most $$$5$$$ edges), so we consider valid configurations.

Case 1: A $$$5$$$-cycle

• Choose $$$1$$$ vertex to leave out: $$$6$$$ ways.
• Arrange the $$$5$$$-cycle: $$$12$$$ ways.
• Connect the leftover vertex to one of the $$$5$$$: $$$5$$$ ways.

Total for this case:
$$$6 \times 12 \times 5 = 360$$$

Case 2: Largest cycle is a $$$3$$$-cycle

• Two disjoint $$$3$$$-cycles: $$$\binom{6}{3}/2 = 10$$$ ways.

• A single $$$3$$$-cycle and attach the remaining $$$3$$$ vertices. There are $$$20$$$ ways to choose the $$$3$$$-cycle, then the remaining vertices can connect in:

• $$$27$$$ ways (all direct),
• $$$54$$$ ways (two-step path),
• $$$9$$$ ways ($$$2 \to 1 \to$$$ cycle),
• $$$18$$$ ways (three-step path).

So total for this subcase:
$$$20 \times (27 + 54 + 9 + 18) = 2160$$$

Adding both subcases:
$$$2160 + 10 = 2170$$$

Final total:
$$$2170 + 360 = 2530$$$

Trivial
Easy
Average
Hard

This problem can be solved with a simple DP. Let $$${E(x)}$$$ denote expected turns to get to the point where all the bulbs are burnt out. From a state where you have $$${x}$$$ bulbs, you can go to $$${x}$$$ different states with 1 turn where you have $$${0,1,2,...,x-1}$$$ bulbs left respectively. Why? Because you choose any of the remaining bulbs with equal probability and after choosing that bulb, all bulbs to its right are burnt, leaving only the bulbs to its left, which is 0 for leftmost bulb, 1 for second bulb, 2 for third bulb, and so on.

This means $$${E(x) = 1 + \frac{1}{x} \cdot (E(0) + E(1) + E(2) + ... + E(x-1)) }$$$ because all the states have equal probability and the base case is $$${E(0) = 0}$$$ since you don't need any more turns if you're not left with any more bulbs.

dp = [0]
dp_sum = 0
for i in range(1, 1000001):
    dp.append(1 + dp_sum / i)
    dp_sum += dp[i]

for _ in range(int(input())):
    n = int(input())
    print(int(dp[n])) # Since we wanted to return floor of the answer

Trivial
Easy
Average
Hard

We are tasked with counting sequences of length $$${k}$$$ made up of "S" and "T" such that there are no two consecutive "S" or three consecutive "T". To solve this, we can find the number of sequences of length $$${k}$$$ if we know how many sequences of length $$${k-1}$$$ end with "S", "T", and "TT".

How? If a sequence ended with an "S" then the next letter ought to be "T" because we can't have two consecutive "S". Now if a sequence ended with "T", it is always allowed to add an "S" after it, and if it ended with "T" but not "TT" then we can also add a "T" to it. And we end up with the difference of number of sequences ending with "T" and "TT" as the new number of sequences ending with "TT".

To put it more mathematically, let $$${S(x)}$$$ denote the number of sequences of length $$${x}$$$ ending with an "S", $$${T(x)}$$$ denote the number of sequences of length $$${x}$$$ ending with "T" and $$${TT(x)}$$$ denote the number of sequences of length $$${x}$$$ ending with a "TT", then:

$$${T(x) = S(x-1) + T(x-1) - TT(x-1)}$$$
$$${S(x) = T(x-1)}$$$
$$${TT(x) = T(x-1) - TT(x-1)}$$$

for $$${x = 1}$$$, $$${T(1) = 1}$$$, $$${S(1) = 1}$$$ and $$${TT(1) = 0}$$$. From here we can solve up for any $$${x \ge 1}$$$.

And obviously the answer is $$${S(x) + T(x)}$$$ for each $$${x}$$$.

ans = [0,2]
MOD = 10**9+7
S = 1
T = 1
TT = 0
for i in range(2, 1000001):
    S, T, TT = T, S + T - TT, T - TT
    S %= MOD
    T %= MOD
    TT %= MOD
    ans.append((S+T)%MOD)

for _ in range(int(input())):
    k = int(input())
    print(ans[k])

Trivial
Easy
Average
Hard

The first important observation is that the answer is the probability for the first day when getting population equal to exactly $$${k}$$$ is possible. This is because if we don't get population $$${k}$$$ on that day, then it will never be possible afterwards and if we do get population $$${k}$$$ on that day, then we have already achieved the target at least once, regardless of what happens later.

Now consider the binary representation of $$${k}$$$. If there is a $$${1}$$$ in some bit position, we require the event that adds $$${2^i}$$$ for that bit.

The interesting case arises when we encounter $$${0}$$$ bits. A single $$${0}$$$ does not give us much flexibility. But if we have two consecutive zeros, then we have two valid chains of events:
1) The population remains unchanged on the days corresponding to both bits.
2) We gain $$${2^i}$$$ on bit $$${i}$$$ and lose $$${2^{i+1}}$$$ on bit $$${i+1}$$$. In both cases, we end up with $$${0}$$$ in both bit positions.

If we have more than two consecutive $$${0}\text{s}$$$, then multiple valid chains of events arise. This number can be calculated using Fibonacci numbers. Let $$${F(n)}$$$ be the $$${n}\text{-th}$$$ Fibonacci number.

Proof:
Suppose we have $$${n}$$$ consecutive zero bits. Consider where we first apply the second type of event chain:
If it starts at the first bit (from the left), then we have $$${n-2}$$$ bits remaining to the right that we need to count the cases for.
If it starts at the second bit, then we have $$${n-3}$$$ bits to the right to count the cases for.
And so on.

Thus the recurrence is:
$$${E(n-1) = E(n-3) + E(n-4) + \cdots + E(0) + 1}$$$
$$${E(n) = E(n-2) + E(n-3) + \cdots + E(0) + 1} = E(n-2) + E(n-1)$$$

Thus the simplified recurrence is:
$$${E(n) = E(n-1) + E(n-2)}$$$

with base cases $$${E(0) = 1}$$$ and $$${E(1) = 1}$$$ (since for $$${0}$$$ or $$${1}$$$ consecutive zero bits, there is only one possible chain of events: do nothing).

Hence $$${E(n)}$$$ is exactly the Fibonacci sequence.

Now,
for the binary representation of $$${k}$$$, find all maximal chains of consecutive $$${0}$$$ bits. The numerator is the product of the corresponding Fibonacci numbers for each chain, and the denominator is $$${3^{(\text{number of bits in the binary representation} - 1)}}$$$. (We subtract $$${1}$$$ because the $$${2^0}$$$ bit is fixed at $$${1}$$$ in the problem statement.) After cancelling common factors of $$${3}$$$ from the numerator and denominator, we obtain the values of $$${p}$$$ and $$${q}$$$.

F = [1, 1]
for i in range(2, 33):
    F.append(F[-1] + F[-2])

for _ in range(int(input())):
    k = bin(int(input()))[2:]
    p = 1
    curr = 0
    for i in range(len(k)):
        if k[i] == "0":
            curr += 1
        else:
            p *= F[curr]
            curr = 0
    q = len(k) - 1
    while p%3 == 0:
        p//=3
        q -= 1
    print((p+q)%1000000007)

Trivial
Easy
Average
Hard

The key to solving this problem is to express the probability of reaching the time machine as a linear function of the probability of reaching it from position $$${1}$$$.

Let the probability of reaching the time machine from position $$${x}$$$ be written as
$$${P(x) = a + b \cdot i}$$$
where $$${i}$$$ is the probability of reaching the time machine starting from position $$${1}$$$.

At position $$${n}$$$, the only possible move is to go directly to position $$${1}$$$, so we have $$${P(n) = 0 + 1 \cdot i}$$$. Now we move backwards from $$${n-1}$$$ down to $$${1}$$$ and compute $$${P(x)}$$$:
If there is a time machine at position $$${x}$$$, then $$${P(x) = 1}$$$.
If there is a teleportation point at position $$${x}$$$, then $$${P(x) = 0}$$$.
Otherwise, $$${P(x)}$$$ is the average of the probabilities of all positions greater than $$${x}$$$.

When we finally reach position $$${1}$$$, its probability must be equal to the average of all probabilities from $$${2}$$$ to $$${n}$$$, i.e.

$$${i = a + b \cdot i}$$$.

This gives the linear equation whose solution is

$$${i = \dfrac{a}{1 - b}}$$$.

To avoid recomputing sums repeatedly, we maintain two running values while moving backward from $$${n}$$$ to $$${2}$$$: the total contribution to the constant coefficient $$${a}$$$, the total contribution to the coefficient of $$${i}$$$, i.e. $$${b}$$$.

At each position we determine $$${P(x) = a' + b' \cdot i}$$$, and add $$${a'}$$$ and $$${b'}$$$ to our running totals. By the time we reach position $$${1}$$$, these totals divided by $$${n-1}$$$ give us the final coefficients $$${a}$$$ and $$${b}$$$. Plugging them into

$$${i = \dfrac{a}{1 - b}}$$$

yields the desired probability.

for _ in range(int(input())):
    n = int(input())
    a, b = map(int, input().split())

    state = [0 for i in range(n)]

    for i in list(map(int, input().split())):
        state[i-1] = -1

    for i in list(map(int, input().split())):
        state[i-1] = 1

    a, b = 0,1
    for i in range(n-2, 0, -1):
        if state[i] == 1:
            a += 1
            continue
        elif state[i] == -1:
            continue
        a += a/(n-i-1)
        b += b/(n-i-1)
    a /= n-1
    b /= n-1
    print(a/(1-b))

Trivial
Easy
Average
Hard

We first observe that each $$${R_i = \tfrac{\min(X_i, X_{n+i})}{\max(X_i, X_{n+i})}}$$$ is uniformly distributed on $$${(0,1)}$$$. This can be shown by direct calculation of the CDF.

Now let $$${P = \prod_{i=1}^n R_i}$$$. Taking logs,

$$${-\ln P = \sum_{i=1}^n (-\ln R_i)}$$$.

Since $$${R_i \sim U(0,1)}$$$, we have $$${-\ln R_i \sim \text{Exponential}(1)}$$$. The sum of $$${n}$$$ i.i.d. exponentials is $$${\text{Gamma}(n,1)}$$$.

Therefore,

$$${\Pr[a \lt P \le b] = \Pr[-\ln b \le -\ln P \lt -\ln a] = F(-\ln a) - F(-\ln b)}$$$

where $$${F}$$$ is the CDF of the $$${\text{Gamma}(n,1)}$$$ distribution:

$$${F(x) = 1 - e^{-x} \sum_{k=0}^{n-1} \dfrac{x^k}{k!}}$$$.

This can be computed in $$${O(n)}$$$ using precomputed factorials.

import math

def gamma_cdf(x, n):
    s = 0
    term = 1
    for k in range(int(n)):
        if k > 0:
            term *= x / k
        s += term
    return 1 - math.exp(-x) * s

for _ in range(int(input())):
    n, a, b = map(float, input().split())
    la, lb = -math.log(a), -math.log(b)
    ans = gamma_cdf(la, n) - gamma_cdf(lb, n)
    print(ans)

Trivial
Easy
Average
Hard