PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
For a binary string S, let X denote the number of its subsequences that equal 01, and Y denote the number of its subsequences that equal 10.
Given N, count the number of distinct pairs of (X, Y) across all binary strings of length N.
EXPLANATION:
Given that we want to count the number of distinct pairs (X, Y), it’s natural to try something along the lines of “fix the value of X, and try to count the number of valid Y corresponding to it”.
However, this is not so simple: there are too many values of X to even iterate over each of them individually (the largest possible value of X is \frac{N^2}{4}, the smallest is 0).
Instead, observe that both 01 and 10 subsequences correspond to pairs of unequal elements in the string — and in fact, together they cover all pairs of unequal elements in S.
This means X+Y equals the number of pairs of unequal elements in S.
On the other hand, if S contains K zeros and (N-K) ones, the number of pairs of unequal elements is K\cdot (N-K).
There are only N+1 possible values of K, so let’s fix one of them.
Note that fixing K fixes X+Y, so if X is known then Y is uniquely determined.
Our aim is now to count the number of distinct values X can take.
Clearly, the lowest possible value of X is 0 (with the string \underbrace{11\ldots 11}_{N-K}\ \underbrace{00\ldots 00}_{K}), and the highest possible value is K\cdot (N-K) with the reverse of that string.
What about values between them?
As it turns out, all of them are possible - that is, for every X\in [0, K\cdot (N-K)], there exists a binary string containing K zeros and N-K ones, such that it has exactly X subsequences equal to 01.
Proof
There’s a fairly simple algorithm to show this.
Start off with the string S = \underbrace{11\ldots 11}_{N-K}\ \underbrace{00\ldots 00}_{K} which has X = 0.
Now, repeatedly do the following:
- Choose an index i such that S_i = 1 and S_{i+1} = 0. Swap S_i and S_{i+1}.
Observe that each such operation increases the value of X by exactly 1.
The only time we can fail to perform it, is when every 1 occurs after every 0 - but such a string has X = K\cdot (N-K) anyway, so we’ve achieved our goal of constructing all values before it.
So, with K fixed, there are exactly K\cdot (N-K) + 1 distinct pairs of (X, Y) we can obtain.
However, we haven’t considered equality across K - as in, is it possible to have some pair (X, Y) occur in two different choices of K (in which case we’d be counting it multiple times, but it should be counted only once)?
As it turns out, no, this is not possible (for the most part).
Note that if a pair (X, Y) is fixed, that means K\cdot (N-K) is fixed (to be equal to X+Y).
There are at most two values of K that can satisfy the equality K\cdot (N-K) = X+Y (because this is a quadratic equation in K) - let them be K_1 and K_2.
Note that if K_1 satisfies the equation then so will N - K_1, meaning we have K_2 = N - K_1.
Now, for both K and N - K, the range of values X can take is the same: [0, K\cdot (N-K)].
This means we’ve simply counted all such pairs twice instead of once - to account for this, we can simply process just one of K and N-K instead of both.
This means the final answer is simply
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
ans = 0
for k in range(n+1):
if k > n-k: break
ans += k*(n-k) + 1
print(ans)
