COUNT0110 - Editorial

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

\sum_{2K \leq N+1} \left(1 + K\cdot (N-K)\right)

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)
1 Like

This problem is solvable by ChatGPT Reason (FREE) model in one try.

7 Likes

Yeah no way 700+ people in div3 would have solved this problem

3 Likes

I thought i am getting dumb

3 Likes

can some one please explain the proof of this line " 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",i couldnt understand the proof properly,:frowning:

As mentioned in the editorial, considering the (x, y) pair is fixed, we want to know the values of k such that x + y = k(n - k), i.e. k(n - k) = S, where S is a constant. This is a quadratic equation k^2 - nk + S = 0 with two roots k1, and k2 such that the sum of roots k1 + k2 = n, so if k1 is a root n- k1 is the other root, so there will always be two values of k for a fixed (x, y). So we can consider only values up till the floor of (n + 1)/2, and there will be no duplicates

2 Likes

Okay,now I understood thanks.

1 Like

Typo:
The answer is from for all k >= 0 && 2 * k <= n, we have to apply summation.
In the end it is mentioned 2 * k <= n + 1

Even I couldn’t believe so many people solved it in div 2.

This was a good problem required a good breaking