PROBLEM LINK:
Author: Abhra Dasgupta
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Pushkar Mishra
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Ad Hoc, Observation
PROBLEM:
Given are N+1 numbers A_0 to A_N. These numbers come in as a stream in order from A_0 to A_N. The number coming in can be placed at either ends of the sequence already present. Score of such a gameplay is calculated as per given rules. Output the sum of scores of all possible different gameplays.
EXPLANATION:
Subtask 1
Subtask 1 can be solved by directly simulating the given problem. In other words, we can directly append the number coming in at either ends and check the sum for each possible arrangement. There can at maximum be 2^N different sequences. Therefore, the time complexity is \mathcal{O}(2^N) per test case. This is sufficient for this subtask.
Subtask 2
Let us start by thinking of simpler sequences in which observing patterns could be easier. A trick is to take something like 1, 1, 1, …, 1, 5 as the sequence. And then the 5 can be shuffled around to different positions to observe how many times a position is taken into account.
Nevertheless, we are going to take a more mathematical approach in this editorial. Let’s see what happens when k^{th} number, i.e., A[k] appears in the stream. It can be appended to either of the two ends of the already existing sequence. But how many already existing sequence are there? Clearly, 2^{(k-1)}. Let us say for now that A[k] is appended to the right of already existing sequence. Now, consider some p^{th} number A[p] coming after A[k]. How many sequences exist such that the A[p] will be multiplied by A[k]? For A[p] to be multiplied by A[k], all numbers coming in between these two must not go to the side that A[k] is on, i.e., they should be put on the left in all the 2^{(k-1)} sequences where A[k] has been appended on the right. If this happens, then when A[p] comes, it will be multiplied by A[k] when placed on the right of it. The (p+1)^{th} up till N^{th} numbers can be arranged in any order after that. So how many sequences in total will have the product of A[k] and A[p]? Clearly, 2^{(k-1)}*2^{(N-p)}. Thus, total value that gets added to the answer is (A[k]*2^{(k-1)})*(A[p]*2^{(N-p)}).
We now have a way to calculate the required answer. Below is the pseudocode of the same.
let possible_future_prod[i] = A[i] * 2^(N-i)
let answer = 0; //accumulator variable
for i = 0 to N-1
{
ways_to_arrange_prefix = 2^(i-1); //if i = 0, then 1
//multipying A[i] with the number of possible prefixes
partial_prod = (ways_to_arrange_prefix * A[i]);
//iterating over elements coming after i
for j = i+1 to N
{
total_prod = partial_prod * possible_future_prod[j];
//adding total_prod to the accumulator variable
ans += total_prod;
}
}
//recall, we had only taken the case when an element is
//appended to the right.
//for taking symmetrical cases into account, multiply by 2.
return 2*ans
This algorithm runs in \mathcal{O}(N^2).
Subtask 3
The algorithm stated in subtask 2 can be made \mathcal{O}(N) by precalculating the suffix sum of the possible\_future\_sequences array. Once we have the suffix\_sum array, the inner loop given above in the pseudocode can be reduced to:
//calculating the suffix_sum array
suffix_sum[n] = possible_future_prod[n]
for i = N-1 downto 0
suffix_sum[i] = possible_future_prod[i] + suffix_sum[i-1];
let answer = 0; //accumulator variable
for i = 0 to N-1
{
ways_to_arrange_prefix = 2^(i-1); //if i = 0, then 1
//multipying A[i] with the number of possible prefixes
partial_prod = (ways_to_arrange_prefix * A[i]);
//calculating the sum that can be achieved by
//multiplying A[i] with numbers coming after it
total_prod = (partial_prod * suffix_sum[i+1]);
//adding total_prod to the accumulator variable
ans += total_prod;
}
//for taking symmetrical cases into account, multiply by 2
return 2*ans
The editorialist’s program follows the editorial. Please see for implementation details.
OPTIMAL COMPLEXITY:
\mathcal{O}(N) per test case.
