TWGR - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic Programming, Binary search/two pointers

PROBLEM:

For an array B, define f(B) to be the length of the longest subsequence S such that 2\cdot S_i \lt S_{i+1} for all 1 \le i \lt |S|.

Given a sorted array A, compute the sum of f(C) across all non-empty subsequences C of A.

EXPLANATION:

Let us understand how to compute f(B) for a fixed sorted array B.
There is a fairly simple greedy algorithm:

  • First, choose B_1.
  • Then, choose the smallest element that’s larger than 2\cdot B_1.
    Let the chosen index be i_1.
  • Next, choose the smallest element that’s larger than 2\cdot B_{i_1}
    Let this next chosen index be i_2.
    \vdots

That is, after first choosing B_1, repeatedly choose the smallest element that’s just larger than the previously chosen element.

This greedy is indeed optimal, which can be proved using an exchange argument:

  • If the smallest chosen element is not B_1, then replacing it with B_1 will keep the length the same without breaking the required condition.
  • Once the first step is done, the same applies to the second step.
    Note that the second chosen element is already \gt 2\cdot B_1 (because the first element was initially some x \ge B_1, and the second element must hence be \gt 2\cdot x \ge 2\cdot B_1)
    So, if it’s not the smallest element that’s \gt 2\cdot B_1, we can instead replace it by this value, and the length of the subsequence doesn’t change while it remains valid.

Performing this replacement over and over again will eventually land us at the greedy choice, proving its optimality.

Let us now attempt to solve the given problem with this observation.

Define dp_i to be the sum of scores of all subsequences starting at index i.
Note that since A is sorted, in all such subsequences we’ll certainly choose A_i itself as the first element.
Also note that there are 2^{N-i} such subsequences, since there are N-i elements after i and each one can freely be present or not present.

For transitions, note that after picking A_i, the next chosen element must be \gt 2\cdot A_i.

Let r be the smallest index such that A_r \gt 2\cdot A_i.
Finding r is fairly simple since A is sorted, you can use binary search or two pointers.

Then,

  • The indices i+1, i+2, \ldots, r-1 don’t really matter at all: whether they belong to the subsequence or not, they will surely not contribute to the score.
    There are r-i-1 such indices, giving us a multiplier of 2^{r-i-1}.
  • Among indices \ge r, only the first one matters; since this is the one our greedy algorithm chooses.
    So, let j \ge r be the smallest index present among these ones.
    Then,
    • For each subsequence starting at j with score x, we obtain 2^{r-i-1} subsequences starting at i with score x+1
      This follows from freely choosing indices in [i+1, r-1], and also A_i itself contributing 1 to the score.
    • We already know that the sum of scores of all subsequences starting at j is dp_j.
    • So, the overall contribution of index j is
      \displaystyle 2^{r-i-1} \cdot (dp_j + 2^{N-j})

The last expression comes from the fact that we want to sum up (f(s)+1) across all subsequences s starting at index j.
The sum of all f(s) is dp_j, and the sum of 1 simply equals the number of subsequences starting at j, which is 2^{N-j}.

We need to add this up across all j \ge r, and so we obtain

dp_i = 2^{i-r-1} + \sum_{j \ge r} 2^{i-r-1} \cdot (dp_j + 2^{N-j})

Here, the first 2^{i-r-1} term comes from the case where we choose no index \ge r, i.e. the subsequence lies entirely in [i, r-1] and hence has a score of 1.

Directly implementing the above transition gives a solution in \mathcal{O}(N^2 \log N), assuming that powers of 2 are computed with binary exponentiation.

However, the slow part is the sum of dp_j + 2^{N-j} across all j \ge r
Note that this is a suffix sum of values that depend purely on j, so by simply storing the suffix sums of these values, we can look them up in \mathcal{O}(1).

This brings the complexity down to \mathcal{O}(N\log N).
It’s possible to further improve this to \mathcal{O}(N) by precomputing powers of 2, because we only need the first N of them.

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
mod = 998244353
pow2 = [1]
for i in range(1, 200005): pow2.append(pow2[-1] * 2 % mod)

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    dp = [0]*n
    rt, sm = n, 0
    for i in reversed(range(n)):
        while a[rt-1] > 2*a[i]:
            rt -= 1
            sm = (sm + dp[rt] + pow2[n-1-rt]) % mod
        
        between = pow2[rt-i-1]
        dp[i] = between * (sm + 1) % mod
    print(sum(dp) % mod)