PROBLEM LINK:Author: Abhra Dasgupta DIFFICULTY:EasyMedium 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 2 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^{(k1)}$. 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^{(k1)}$ 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^{(k1)}*2^{(Np)}$. Thus, total value that gets added to the answer is $(A[k]*2^{(k1)})*(A[p]*2^{(Np)})$. We now have a way to calculate the required answer. Below is the pseudocode of the same.
This algorithm runs in $\mathcal{O}(N^2)$. Subtask 3
The editorialist's program follows the editorial. Please see for implementation details. OPTIMAL COMPLEXITY:$\mathcal{O}(N)$ per test case. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 01 Jan '16, 12:44

short editorial on four relatively easy problems: https://shadekcse.wordpress.com/2016/01/11/codechefjan16challenge/ answered 11 Jan '16, 15:26

@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. answered 14 Jan '16, 18:52

Nice problem :) After a lot of WA's ultimately got green ticked AC. Here's my solution : https://www.codechef.com/viewsolution/9060724 answered 17 Jan '16, 13:35

somebody please upvote me , i have questions to ask thank you answered 25 Sep '16, 16:41

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^(k1) 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. answered 11 Jan '16, 15:36
The initial problem statement had this confusion. It was updated on 2nd or 3rd day as far as i remember > "when we read from left to right, there exists some position i, at which the gameplays have aj and ak written at the ith position such that j ≠ k."
(13 Jan '16, 19:24)

@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). answered 11 Jan '16, 17:13

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 answered 11 Jan '16, 17:22

@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. answered 11 Jan '16, 17:34

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 answered 13 Jan '16, 18:38

@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 ith 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^n1 times 15 2^n2 times now we are left with only two combinations of score the will repeat themselves 2^n3 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 https://www.codechef.com/viewsolution/9177526 pls check my solution then why subtask 2 is not being accepted i would love to hear a word form u on this :) answered 15 Jan '16, 02:05

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 ? answered 16 Jan '16, 11:14

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 answered 18 Jan '16, 16:11

@jawa2code You are not supposed to remove duplicates answered 19 Jan '16, 14:54

Hello Killjee sir,time(sec) number appeared seq result1 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 answered 20 Jan '16, 15:11

For Free Query Regarding To Packers and Movers Visit Packers and Movers Chennai http://www.shiftingsolutions.in/packersandmoverschennai.html Packers and Movers Jaipur http://www.shiftingsolutions.in/packersandmoversjaipur.html answered 21 Jan '16, 17:13

@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 = N1 downto 0 suffix_sum[i] = possible_future_prod[i] + suffix_sum[i1]; and how can this loop calculate because suffix_sum[i1] will store a garbage value as its not been computed at any time
link
This answer is marked "community wiki".
answered 24 Jan '16, 03:58

i think in the 4 line there should be suffix_sum[i] = possible_future_prod[i] + suffix_sum[i+1] instead of suffix_sum[i] = possible_future_prod[i] + suffix_sum[i1]; answered 25 Jan '16, 10:22

Can someone tell what is wrong with this solution. solution answered 15 Feb '16, 20:03

here is my solutions it works on the test cases but it shows wrong ans when i submitted https://www.codechef.com/viewsolution/9977223 thanks in advance answered 29 Apr '16, 08:48

In the O(N) solution for subtask3, shouldn't the index of suffix_sum in the RHS of the expression  suffix_sum[i] = possible_future_prod[i] + suffix_sum[i1]; be i+1 instead of i1 I mean it should be  suffix_sum[i] = possible_future_prod[i] + suffix_sum[i+1]; answered 09 May '16, 22:48

Why is the below code not working for subtask 2 and 3. I have used the logic of the editorial only. import java.util.Scanner; class RupsaGame2{
} answered 10 May '16, 19:14

can someone point out the mistake in this code ? https://www.codechef.com/viewsolution/10055742 answered 11 May '16, 16:34

what must be the time complexity of the program. I have written the code and when trying to submit it is showing "Time Limit Exceeded" error. I have used backtracking. answered 05 Jun '16, 03:24

I'm not able to understand how come for a sequence 1 2 1 the output is 14. According to my calculations, it always yields 11 as @jawa2code has mentioned. Clearly some have to explain this with proper example.(because I could not follow with @aman935 answer) for sequence 1 2 1 These are the possible AiAi+1 pairs . 1 > Output 1 1 *2* > Output 2 1 2 *1* > Output 2 *1* 1 2 > Output 1 *2* 1 > Output 2 1 2 *1* > Output 2 *1* 2 1 > Output 1 Where the number in star indicate the position of the number (in sequence) placed at left or right. So the Output of the result of the above operation is 1 + 2 + 2 + 1 + 2 + 2 + 1 = 11 cc: / @killjee, @pushkarmishra, @aman935 answered 12 Jun '16, 17:03

In Subtask 3 pseudocode, shouldn't it be suffix_sum[i] = possible_future_prod[i] + suffix_sum[i+1]; answered 28 Jul '16, 01:39

can someone check and find the error in my code...I have compared my output with those of the other successful submissions for random values and the outputs are same https://www.codechef.com/viewsolution/11074855 answered 08 Aug '16, 14:57

It took quite some time to understand the problem. For the numbers 1 2 1 Case 1. Lets start with writing numbers only at the right end 1     1 2     product is 2     1 2 1     product is 2 (2 multiplied with 1) (product is new number multiplied with its neighbor) Sum of the products is 4 Case 2. Write numbers only at the left end 1     2 1     product is 2     1 2 1     product is 2 Sum of the products is 4 Case 3. Write numbers at alternate ends starting with right end 1     1 2     product is 2     1 1 2     product is 1 (1 multiplied with 1) Sum of the products is 3 Case 4. Write numbers at alternate ends starting with left end 1     2 1     product is 2     2 1 1     product is 1 Sum of the products is 3 Sum of all the products is 14. Though case 1 and 2 resulted in the same sequence, both should be considered since the order in which numbers were written is different. answered 30 Aug '16, 12:53

Can anyone tell me what's the problem with this code? I have tried with random inputs from one of the successful submissions and they all seem to give the correct result. Here's the code: https://www.codechef.com/viewsolution/11610571 I have used recursion in my code. Can this be the source of the problem? Gramercy... answered 24 Sep '16, 10:32

Hmm, I need some amount of help. I have written the code, which seems to work right for a small number of elements. When we increase the size of the elements, then it makes a small mistake somehow. The test case I ran, had an error of 19. I want to know where is this error generated. Here is the code : https://www.codechef.com/viewsolution/11993701 answered 02 Nov '16, 21:01

can any one tell why i m getting wrong ans for this method answered 25 Nov '16, 13:00

I have written this code for the given problem but for some reason, while submitting, it's giving me some error. Can anyone please help me with this? By the way, it was a good problem. include<stdio.h>
} answered 15 Jan '17, 20:25

include<stdio.h>
} Please tell me what's the problem in this code. It's running fine in my compiler. answered 15 Jan '17, 20:31

@jawa2code @killjee please help make this solution perfect. include<stdio.h>
} answered 15 Jan '17, 20:49

Please tell me what is wrong with this solution in the below given link : answered 25 Feb '17, 17:08

While submitting my solution for this problem, I am getting compile error and if I click on the link to find out what the compilation error is, then I am getting to a page where it says 'There was an error while serving this page. Please try again after some time'. Is there anyone who faced a similar issue? Any ideas? answered 13 Apr '17, 02:50

hello, i don't understand the solution of 121 even after reading the editorial. in the explanation of the of the answer for 121 i've read the solution to be adding the sum of scores of gameplays taking 121 twice. According to the problem, two gameplays are different if after writing down all the numbers, the sequences of the gameplays aren't identical. for this to be true, 121 has only three gameplays  121, 112 and 211. these gameplays gave the answer as 12+21 = 4, 11+12 = 3 and 21+11 = 3. This gives an answer of 10. Now, in other explanations the 121 gameplay has been taken twice  once by doing this sequence  12 > 1 > 121  and the other by doing 21 > 1 (on the front end) > 121. In the end, this gameplay can not be taken as two different gameplays as both of them result in the same sequence after writing down (n+1) numbers. So, what's the explanation for the answer? answered 21 Jun '17, 16:01

Hello, can someone please tell me what's wrong with my code It is giving right answers for Subtask 1 But giving wrong answer(WA) for Subtask 2 And for Subtask 3, it is giving TLE(As the complexity of my code is O(n^2)), Please tell me why it is giving WA for Subtask 2?
answered 21 Jun '17, 19:49

Hey can any one check my code also? I am getting correct answer for subtask one but wrong for other two. check my code:
answered 22 Sep '17, 00:59

I have slightly easier approach. We can visualize the problem with reference to a binary tree. Starting from the topmost part of the node we can draw a binary tree in such a way that the new number goes to the left of the previous numbers in the left subtree and it goes to the right of the previous numbers in the right subtree. In the way we just have to eliminate the numbers having same sequence. This is depicted in the below link: https://drive.google.com/file/d/0B9d_mf_aoiYAUUttdDZmOXc1Z2M/view?usp=sharing In this image we can calculate the sum at each levels of the tree i.e. 12=2,21=2,121=4,211=3,112=3. Total is 14. We can ignore the last element of the subtree since it is a repeated sequence. Please upvote my answer if you find this to be helpful. I will put on the code in a short while. answered 26 Oct '17, 11:31

First I'll say that the percentage success model can be really helpful on this program. You can write a directsimulation program to solve subtask 1 and with that you can generate test data to support other approaches. My solution runs forward through the cases by maintaining a term that represents the mix of exposed ends of the game string. This is initially $t_0 = 2 a_0$  two sides of the first placement  then $t_1 = 2(a_0+a_1)$, the two exposed ends of the two possible games of $n=1$  then $t_2 = 2(a_0+a_1) + 4a_2$, $t_3=2(a_0+a_1) + 4a_2 +8a_3$, etc. Each time the next move set sums across all possibilities to $s_k = a_k t_{k1}$, with the accumulated game score also including twice the sum of previous game scores, $g_k = 2g_{k1} + s_k$ since there are two possibilities for this move. answered 31 Aug '18, 21:21
