You are not logged in. Please login at www.codechef.com to post your questions!

×

# RGAME - Editorial

Author: Abhra Dasgupta
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Pushkar Mishra

Easy-Medium

# 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 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.

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)$.

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:

This question is marked "community wiki".

asked 01 Jan '16, 12:44 1.3k156581
accept rate: 4% 19.8k350498541

 2 short editorial on four relatively easy problems: https://shadekcse.wordpress.com/2016/01/11/codechef-jan16-challenge/ answered 11 Jan '16, 15:26 3★shadek 109●1●3 accept rate: 0%
 2 @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 3★aman935 120●1 accept rate: 0%
 2 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 781●8 accept rate: 7%
 2 somebody please upvote me , i have questions to ask thank you answered 25 Sep '16, 16:41 144●2●5 accept rate: 3%
 1 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. answered 11 Jan '16, 15:36 81●1●5 accept rate: 0% 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) vsp46★
 0 This was soo hard :p answered 11 Jan '16, 15:15 101●1●6 accept rate: 0%
 0 Good problem answered 11 Jan '16, 16:44 1 accept rate: 0%
 0 @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 3★aman935 120●1 accept rate: 0%
 0 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 24●1●2●7 accept rate: 0%
 0 @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 5★killjee 476●9 accept rate: 5%
 0 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 24●1●2●7 accept rate: 0%
 0 @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 will repeat itself 2^n times so our score by now would be arrmul2^n now let us assume we are at arr=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 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 3★c0dew0rm 1 accept rate: 0%
 0 please fix the solution links answered 15 Jan '16, 08:50 55●6 accept rate: 0%
 0 tough question . answered 16 Jan '16, 11:03 11●2 accept rate: 0%
 0 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 11●2 accept rate: 0%
 0 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 24●1●2●7 accept rate: 0%
 0 @jawa2code You are not supposed to remove duplicates answered 19 Jan '16, 14:54 5★killjee 476●9 accept rate: 5%

## 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

answered 20 Jan '16, 15:11 24127
accept rate: 0%

 0 For Free Query Regarding To Packers and Movers Visit Packers and Movers Chennai http://www.shiftingsolutions.in/packers-and-movers-chennai.html Packers and Movers Jaipur http://www.shiftingsolutions.in/packers-and-movers-jaipur.html answered 21 Jan '16, 17:13 0★devil2 1 accept rate: 0%
 0 @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 ?? answered 23 Jan '16, 01:35 3★c0dew0rm 1 accept rate: 0%
 0 @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 link This answer is marked "community wiki". answered 24 Jan '16, 03:58 3★c0dew0rm 1 accept rate: 0%
 0 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[i-1]; answered 25 Jan '16, 10:22 2★alkos 1 accept rate: 0%
 0 Can someone tell what is wrong with this solution. solution answered 15 Feb '16, 20:03 1●1 accept rate: 0%
 0 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 1 accept rate: 0%
 0 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[i-1]; be i+1 instead of i-1 I mean it should be - suffix_sum[i] = possible_future_prod[i] + suffix_sum[i+1]; answered 09 May '16, 22:48 1 accept rate: 0%
 0 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{ public static int N; public static long[] Ai; public static final long MOD = 1000000007; public static void main(String[] args){ int T; Scanner a = new Scanner(System.in); T=a.nextInt(); for(int i=0;i0;i--) suffix_sum[i]=(((1L*(Ai[i])*(powerOf2(N-i)))%MOD) + (suffix_sum[i+1]))%MOD; long ans = 0; for(int i=0;i<=N-1;i++){ long ways_to_arrange_prefix = powerOf2(i-1)%MOD; long partial_prod = (1L*(ways_to_arrange_prefix) * (Ai[i]%MOD) )%MOD; long total_prod = (1L*partial_prod * suffix_sum[i+1])%MOD; ans = (ans + total_prod)%MOD ; } ans=2*ans; ans=ans%MOD; return ans; } public static long powerOf2(int m){ long result = 1L; for(int i=1;i<=m;i++) result=result*2L; return result; }  } answered 10 May '16, 19:14 1 accept rate: 0%
 0 can someone point out the mistake in this code ? https://www.codechef.com/viewsolution/10055742 answered 11 May '16, 16:34 19●1 accept rate: 0%
 0 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 1 accept rate: 0%
 0 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 answered 12 Jun '16, 17:03 1 accept rate: 0%
 0 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 143●1●6 accept rate: 10%
 0 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 3★dr_aps 1 accept rate: 0%
 0 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 0★sou333 1 accept rate: 0%
 0 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 1●1 accept rate: 0%
 0 lol i am new :P answered 24 Sep '16, 11:06 0★gokuo 1 accept rate: 0%
 0 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 1 accept rate: 0%
 0 can any one tell why i m getting wrong ans for this method https://www.codechef.com/viewsolution/12137512 answered 25 Nov '16, 13:00 1 accept rate: 0%

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>

struct code
{
int y;
int a;
int b;
int k;
}grp;
int arr,t,n,kk,j,p,c,a,i,z,m,sum=0;
void main()
{
for(i=0;i<100;i++)
{
grp[i].k=0;
}
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d",&n);
for(j=0;j<=n;j++)
{
scanf("%d",&kk);
arr[j]=kk;
z=0;
if(j!=0)
{
p=grp[j-1].k;
for(c=0;c<=p;c++)
{
grp[j].a[z]=j;
grp[j].a[z]=grp[j-1].a[c];
grp[j].b[z]=grp[j-1].b[c]+arr[grp[j-1].a[c]]*arr[j];

z++;
grp[j].a[z]=grp[j-1].a[c];
grp[j].a[z]=j;
grp[j].b[z]=grp[j-1].b[c]+arr[grp[j-1].a[c]]*arr[j];

z++;
}
z=z-1;
grp[j].k=z;
}
else
{
grp[j].k=0;
grp[j].b=0;
grp[j].a=0;
grp[j].a=0;
}
}
j--;
for(m=0;m<=grp[j].k;m++)
{
sum+=grp[j].b[m];
}
printf("%d\n",sum);
sum=0;
}


}

answered 15 Jan '17, 20:25 1
accept rate: 0%

# include<stdio.h>

struct code
{
int y;
int a;
int b;
int k;
}grp;
int arr,t,n,kk,j,p,c,a,i,z,m,sum;
void main()
{
for(i=0;i<100;i++)
{
grp[i].k=0;
}
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d",&n);
for(j=0;j<=n;j++)
{
scanf("%d",&kk);
arr[j]=kk;
z=0;
if(j!=0)
{
p=grp[j-1].k;
for(c=0;c<=p;c++)
{
grp[j].a[z]=j;
grp[j].a[z]=grp[j-1].a[c];
grp[j].b[z]=grp[j-1].b[c]+arr[grp[j-1].a[c]]*arr[j];

z++;
grp[j].a[z]=grp[j-1].a[c];
grp[j].a[z]=j;
grp[j].b[z]=grp[j-1].b[c]+arr[grp[j-1].a[c]]*arr[j];

z++;
}
z=z-1;
grp[j].k=z;
}
else
{
grp[j].k=0;
grp[j].b=0;
grp[j].a=0;
grp[j].a=0;
}
}
j--;
for(m=0;m<=grp[j].k;m++)
{
sum[i]+=grp[j].b[m];
}
}
for(i=0;i<t;i++)
printf("%d\n",sum[i]);


} Please tell me what's the problem in this code. It's running fine in my compiler.

answered 15 Jan '17, 20:31 1
accept rate: 0%

# include<stdio.h>

struct code
{
int y;
int a;
int b;
int k;
}grp;
int arr,t,n,kk,j,p,c,a,i,z,m,sum;
void main()
{
for(i=0;i<100;i++)
{
grp[i].k=0;
}
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d",&n);
for(j=0;j<=n;j++)
{
scanf("%d",&kk);
arr[j]=kk;
z=0;
if(j!=0)
{
p=grp[j-1].k;
for(c=0;c<=p;c++)
{
grp[j].a[z]=j;
grp[j].a[z]=grp[j-1].a[c];
grp[j].b[z]=grp[j-1].b[c]+arr[grp[j-1].a[c]]*arr[j];

z++;
grp[j].a[z]=grp[j-1].a[c];
grp[j].a[z]=j;
grp[j].b[z]=grp[j-1].b[c]+arr[grp[j-1].a[c]]*arr[j];

z++;
}
z=z-1;
grp[j].k=z;
}
else
{
grp[j].k=0;
grp[j].b=0;
grp[j].a=0;
grp[j].a=0;
}
}
j--;
for(m=0;m<=grp[j].k;m++)
{
sum[i]+=grp[j].b[m];
}
}
for(i=0;i<t;i++)
printf("%d\n",sum[i]);


}

answered 15 Jan '17, 20:49 1
accept rate: 0%

 0 Please tell me what is wrong with this solution in the below given link : https://www.codechef.com/viewsolution/12927725 answered 25 Feb '17, 17:08 4★singh_8 1 accept rate: 0%
 0 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 11 accept rate: 0%
 0 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 2★sphd 1 accept rate: 0%
 0 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? #include #include #include #include #include #define MOD 1000000007 #define ull unsigned long long int using namespace std; ull multiply(ull a,ull b) { ull mul=(a%MOD*b%MOD)%MOD; return(mul); } int main() { ull test; cin>>test; while(test) { int n; cin>>n; ull arr[n+1]; ull sum=0,mul=1,exp=1; for(int i=0;i<=n;i++) { cin>>arr[i]; } for(int i=1;i<=n;i++) { exp=multiply(exp,2); } for(int i=0;i
 0 Hey can any one check my code also? I am getting correct answer for subtask one but wrong for other two. check my code: #include using namespace std; long long int M=1000000007; unsigned long long int power(long long int n) { unsigned long long sum=1; for(long long int i=0;i>t; while(t--) { unsigned long long int n,a,i,j,sum=0,tot,tot2,pdt1,pdt2; cin>>n; n=n+1; for(int i=1;i<=n;i++) cin>>a[i]; for(i=1;i<=n-1;i++) { if(i==1||i==2) tot=2; else tot=(tot*2)%M; pdt1=(a[i]*tot)%M; //cout<
 0 I have slightly easier approach. We can visualize the problem with reference to a binary tree. Starting from the top-most 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 sub-tree and it goes to the right of the previous numbers in the right sub-tree. 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 0★tijus 1 accept rate: 0%
 0 First I'll say that the percentage success model can be really helpful on this program. You can write a direct-simulation 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_{k-1}$, with the accumulated game score also including twice the sum of previous game scores, $g_k = 2g_{k-1} + s_k$ since there are two possibilities for this move. answered 31 Aug '18, 21:21 5★joffan 948●8 accept rate: 13%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,722
×968
×106

question asked: 01 Jan '16, 12:44

question was seen: 20,670 times

last updated: 31 Aug '18, 21:21