RGAME - Editorial

PROBLEM LINK:

Practice
Contest

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.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

5 Likes

This was soo hard :stuck_out_tongue:

4 Likes

short editorial on four relatively easy problems: Codechef Jan’16 challenge – Discussion Forum

3 Likes

But how many already existing sequence are there? Clearly, 2^(k−1) but when two pairs equal numbers are there then there will not 2^(k-1) sequences because of repetion of sequences, like suppose we have 1, 2, 2, 3, 3
We can obtain : 1 -> 1 2 -> 1 2 3 -> 2 1 2 3 -> 3 2 1 2 3
Also, : 1 -> 2 1 -> 3 2 1 -> 3 2 1 2 -> 3 2 1 2 3.
So I think the approach is wrong and all have blind folded solved this problem.
@admin.

2 Likes

Good problem

@saurabhsuniljain In one of the comments on the contest page and I the second sample test case clearly have shown that the sequences which are actually same(:p) will still be considered different if the numbers were inserted in different orders(nobody can tell the sequence they were inserted in ,just by seeing, the mess created by the problem). Although I agree that the question statement was indeed difficult to understand (may have been clearer).

1 Like

Hello how 1 2 1 leads to 14
1 2=>2
2 1=>2
1 2 1=>2
1 1 2=>1
2 1 1=>1
1 2 1=>1
total=2+2+2+1+1+1=9
can some help me to get 14
Regards
Samuel

2 Likes

@jawa2code
Explanation Of 121:-
we pick 1 then put 2 in backside of 1 then the sequence becomes 12 then we put last 1 at the end so the sequence becomes 121 and total score for this will be 12+21=4. Also we may put last 1 in beginning of 12 which will form 112 and score for this will be 12+11=3. Also we wemay put 2 in front of first 1 which will transform the sequence to 21 now we can put the last one either in front or back of “21” which will lead to 121 and 211 and score will be 12+21=4 and 21+11=3 respectivly adding up all the scores we get 4+4+3+3=14.

7 Likes

Hello sir Killjee,thanks for your response
from the Problem statement
For a move in which you write a number Ai (i>0), your points increase by the product of Ai and its neighbour. (Note that for any move it will have only one neighbour as you write the number at an end).

are you following this instruction?
Regards
Samuel

@jawa2code . Yes, maybe you are assuming the sum in 2 1 to be fixed and then subsequent products will be calculated adding to this. But this approach is wrong. As, the question statement says that you have to to calculate the sum of scores for all game plays. Consider 1 2 1 as a gameplay. To get to this gameplay, we start with 1 2 . The sum for this is 12=2. Now, moving ahead adding 1 to the sequence, we have the new sum to be 21 + 2 =4, for 1 2 1. Now, for 1 1 2. This is a different gameplay. So, to calculate the score for this case, we’ll start from the beginning. The sequence will have to be built again. And the sum 1*1 will again be calculated. So, if you start to make different game plays like this you will see that the sum thus calculated is calculated many times.

Please upvote if this clarifies your doubt. I had the same problem in the beginning.

10 Likes

@pushkarmishra i have a different algo to solve the prob its complexity is O(n^2) but it fails subtask 2
i will try to explain u my algo
Let us take n=4;
so our array will contain n+1 elements
and we define our array to be say {1,2,3,4,5};
now what i observed was
the only scores which can be achieved will be as follows :
2 3 6 4 8 12 5 10 15 20
the reason to this being,when we are at i-th number let us say 5 it could be placed at right or left of all above formed numbers which will give only products 5 mul 1=5 5 mul 2=10 5 mul 3=15 5 mul 4=20
similarly for 4 4mul 1=4 4mul 2=8 4mul3=12
and now what i observed was that the arr[1] will repeat itself 2^n times so our score by now would be arr[1]mul2^n
now let us assume we are at arr[4]=5;
the scores which it can achieve will be
5
10
15
20 respectively 20 will repeat itself 2^n-1 times
15 2^n-2 times now we are left with only two combinations of score the will repeat themselves 2^n-3 times
what i m trying to do is iterate all numbers in the array
compute there respective scores and how many times will they repeat themselves multiply with arr[i] and aad to sum this will take a outer loop and an inner loop as i have used here CodeChef: Practical coding for everyone
pls check my solution
then why subtask 2 is not being accepted i would love to hear a word form u on this :slight_smile:

please fix the solution links

tough question .

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, can anybody explain me ?

Nice problem :slight_smile:

After a lot of WA’s ultimately got green ticked AC.

Here’s my solution : CodeChef: Practical coding for everyone

3 Likes

Thanks Aman,
May i know how are you interpreting
this condition
For a move in which you write a number Ai (i>0), your points increase by the product of Ai and its neighbour. (Note that for any move it will have only one neighbour as you write the number at an end).

My understanding is this
if the in put is 1 2 1
Time: Result
1 sec 1 appeared =1
2 sec 2 appeared =1 2/2 1 total=2+2=4
3 sec 1 appeared= 1 1 2/1 2 1/1 2 1/2 1 1=eliminate duplicates={1 1 2/1 2 1/2 1 1}=2+1+1=4
Regards
Samuel

@jawa2code You are not supposed to remove duplicates

1 Like

Hello Killjee sir,

time(sec) number appeared seq result

1 1 1 1

2 2 1 2(2)/(2)2 1 2+2=4

3 1 (1)1 1 2/1 2 1(2)/2 1 1(1)/(2)1 2 1 1+2+1+2=6

Total 1+4+6=11

@killjee my code has time complexity O(n^2) yet it only executes first sub task acc to algo it should pass 2 subtasks why is it so ??

@abhra73 , @antoniuk1 , @pushkarmishra , @admin can anyone pls explain because its not clear in the edtiorial
suffix_sum[n] = possible_future_prod[n]
the possible future productions of n should be zero
for i = N-1 downto 0
suffix_sum[i] = possible_future_prod[i] + suffix_sum[i-1];
and how can this loop calculate because suffix_sum[i-1] will store a garbage value as its not been computed at any time