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

×

RGAME - Editorial

2
2

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

This question is marked "community wiki".

asked 01 Jan '16, 12:44

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581
accept rate: 4%

edited 10 Mar '16, 13:21

admin's gravatar image

0★admin ♦♦
19.8k350498541


short editorial on four relatively easy problems: https://shadekcse.wordpress.com/2016/01/11/codechef-jan16-challenge/

link

answered 11 Jan '16, 15:26

shadek's gravatar image

3★shadek
10913
accept rate: 0%

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

link

answered 14 Jan '16, 18:52

aman935's gravatar image

3★aman935
1201
accept rate: 0%

Nice problem :)

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

Here's my solution : https://www.codechef.com/viewsolution/9060724

link

answered 17 Jan '16, 13:35

code_hard123's gravatar image

6★code_hard123
7818
accept rate: 7%

somebody please upvote me , i have questions to ask thank you

link

answered 25 Sep '16, 16:41

vijayiota77's gravatar image

4★vijayiota77
14425
accept rate: 3%

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.

link

answered 11 Jan '16, 15:36

saurabhsuniljain's gravatar image

2★saurabhsuniljain
8115
accept rate: 0%

edited 11 Jan '16, 15:51

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★

This was soo hard :p

link

answered 11 Jan '16, 15:15

theweblover007's gravatar image

2★theweblover007
10116
accept rate: 0%

Good problem

link

answered 11 Jan '16, 16:44

ashishsb95's gravatar image

3★ashishsb95
1
accept rate: 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).

link

answered 11 Jan '16, 17:13

aman935's gravatar image

3★aman935
1201
accept rate: 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

link

answered 11 Jan '16, 17:22

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 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.

link

answered 11 Jan '16, 17:34

killjee's gravatar image

5★killjee
4769
accept rate: 5%

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

link

answered 13 Jan '16, 18:38

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 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[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 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 :)

link

answered 15 Jan '16, 02:05

c0dew0rm's gravatar image

3★c0dew0rm
1
accept rate: 0%

edited 15 Jan '16, 02:08

please fix the solution links

link

answered 15 Jan '16, 08:50

codedog29's gravatar image

3★codedog29
556
accept rate: 0%

tough question .

link

answered 16 Jan '16, 11:03

shuboy2014's gravatar image

2★shuboy2014
112
accept rate: 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 ?

link

answered 16 Jan '16, 11:14

shuboy2014's gravatar image

2★shuboy2014
112
accept rate: 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

link

answered 18 Jan '16, 16:11

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

@jawa2code You are not supposed to remove duplicates

link

answered 19 Jan '16, 14:54

killjee's gravatar image

5★killjee
4769
accept rate: 5%

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

link

answered 20 Jan '16, 15:11

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 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

link

answered 21 Jan '16, 17:13

devil2's gravatar image

0★devil2
1
accept rate: 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 ??

link

answered 23 Jan '16, 01:35

c0dew0rm's gravatar image

3★c0dew0rm
1
accept rate: 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

c0dew0rm's gravatar image

3★c0dew0rm
1
accept rate: 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];

link

answered 25 Jan '16, 10:22

alkos's gravatar image

2★alkos
1
accept rate: 0%

Can someone tell what is wrong with this solution. solution

link

answered 15 Feb '16, 20:03

rishabh_bitg's gravatar image

3★rishabh_bitg
11
accept rate: 0%

edited 15 Feb '16, 20:07

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

link

answered 29 Apr '16, 08:48

ankitkataria's gravatar image

2★ankitkataria
1
accept rate: 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];

link

answered 09 May '16, 22:48

imeavinash's gravatar image

0★imeavinash
1
accept rate: 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;i<T;i++){
        N=a.nextInt();
        Ai=new long[N+1];
        for(int j=0;j<=N;j++)
            Ai[j]=a.nextInt();
        System.out.println(calculate(Ai));      
    }

}

public static long calculate(long[] Ai){

    long[] suffix_sum = new long[N+1];
    suffix_sum[N] = (1L* (Ai[N]) * powerOf2(0)) % MOD;
    for(int i=N-1;i>0;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;
}

}

link

answered 10 May '16, 19:14

imeavinash's gravatar image

0★imeavinash
1
accept rate: 0%

can someone point out the mistake in this code ? https://www.codechef.com/viewsolution/10055742

link

answered 11 May '16, 16:34

vinayak_1's gravatar image

3★vinayak_1
191
accept rate: 0%

edited 11 May '16, 16:37

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.

code link https://www.codechef.com/viewsolution/10322873

link

answered 05 Jun '16, 03:24

mahend_gaur's gravatar image

0★mahend_gaur
1
accept rate: 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

cc: / @killjee, @pushkarmishra, @aman935

link

answered 12 Jun '16, 17:03

darkwin007's gravatar image

0★darkwin007
1
accept rate: 0%

edited 12 Jun '16, 17:05

In Subtask 3 pseudocode, shouldn't it be

suffix_sum[i] = possible_future_prod[i] + suffix_sum[i+1];

link

answered 28 Jul '16, 01:39

meetrockstar's gravatar image

4★meetrockstar
14316
accept rate: 10%

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

link

answered 08 Aug '16, 14:57

dr_aps's gravatar image

3★dr_aps
1
accept rate: 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.

link

answered 30 Aug '16, 12:53

sou333's gravatar image

0★sou333
1
accept rate: 0%

edited 30 Aug '16, 12:54

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

link

answered 24 Sep '16, 10:32

americast's gravatar image

2★americast
11
accept rate: 0%

edited 24 Sep '16, 20:49

lol i am new :P

link

answered 24 Sep '16, 11:06

gokuo's gravatar image

0★gokuo
1
accept rate: 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

link

answered 02 Nov '16, 21:01

atarekaze's gravatar image

0★atarekaze
1
accept rate: 0%

can any one tell why i m getting wrong ans for this method

https://www.codechef.com/viewsolution/12137512

link

answered 25 Nov '16, 13:00

sandeeplalala's gravatar image

3★sandeeplalala
1
accept rate: 0%

edited 25 Nov '16, 13:06

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[100][2];
    int b[100];
    int k;
}grp[100];
int arr[100],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][0]=j;
                grp[j].a[z][1]=grp[j-1].a[c][1];
                grp[j].b[z]=grp[j-1].b[c]+arr[grp[j-1].a[c][0]]*arr[j];

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

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

}

link

answered 15 Jan '17, 20:25

riteshp887's gravatar image

0★riteshp887
1
accept rate: 0%

include<stdio.h>

struct code
{
    int y;
    int a[100][2];
    int b[100];
    int k;
}grp[100];
int arr[100],t,n,kk,j,p,c,a,i,z,m,sum[100];
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][0]=j;
                grp[j].a[z][1]=grp[j-1].a[c][1];
                grp[j].b[z]=grp[j-1].b[c]+arr[grp[j-1].a[c][0]]*arr[j];

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

                z++;
            }
            z=z-1;
            grp[j].k=z;
        }
        else
        {
            grp[j].k=0;
            grp[j].b[0]=0;
            grp[j].a[0][0]=0;
            grp[j].a[0][1]=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.

link

answered 15 Jan '17, 20:31

riteshp887's gravatar image

0★riteshp887
1
accept rate: 0%

@jawa2code @killjee please help make this solution perfect.

include<stdio.h>

struct code
{
    int y;
    int a[100][2];
    int b[100];
    int k;
}grp[100];
int arr[100],t,n,kk,j,p,c,a,i,z,m,sum[100];
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][0]=j;
                grp[j].a[z][1]=grp[j-1].a[c][1];
                grp[j].b[z]=grp[j-1].b[c]+arr[grp[j-1].a[c][0]]*arr[j];

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

                z++;
            }
            z=z-1;
            grp[j].k=z;
        }
        else
        {
            grp[j].k=0;
            grp[j].b[0]=0;
            grp[j].a[0][0]=0;
            grp[j].a[0][1]=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]);

}

link

answered 15 Jan '17, 20:49

riteshp887's gravatar image

0★riteshp887
1
accept rate: 0%

Please tell me what is wrong with this solution in the below given link :

https://www.codechef.com/viewsolution/12927725

link

answered 25 Feb '17, 17:08

singh_8's gravatar image

4★singh_8
1
accept rate: 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?

link

answered 13 Apr '17, 02:50

rockstar283's gravatar image

0★rockstar283
11
accept rate: 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?

link

answered 21 Jun '17, 16:01

sphd's gravatar image

2★sphd
1
accept rate: 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 <iostream>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#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<n;i++)
        {
            ull k=exp;
            if(i!=0)
                k=exp/2;
            for(int j=i+1;j<=n;j++)
            {
                mul=multiply(multiply(arr[i],arr[j]),k);
                sum=(sum%MOD+mul%MOD)%MOD;
                k=k/2;
            }
        }
        cout<<sum<<endl;
        test--;
    }
}
link

answered 21 Jun '17, 19:49

vivek091195's gravatar image

0★vivek091195
1
accept rate: 0%

edited 21 Jun '17, 19:53

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<iostream>
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<n;i++)
    sum=(sum*2)%M;
    return sum;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
    unsigned    long long int n,a[100010],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<<tot<<endl;
    for(j=i+1;j<=n;j++)
    {

    if(j==i+1)
    tot2=mult(n-j)%M;
    else tot2=tot2/2;
    pdt2=(a[j]*tot2)%M;

    //  cout<<tot<<endl;
        sum=(sum+(pdt1*pdt2)%M)%M;
        //cout<<sum<<endl;

    }
}
    cout<<sum<<endl;    
    }
    return 0;
}
link

answered 22 Sep '17, 00:59

rp789's gravatar image

5★rp789
22
accept rate: 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.

link

answered 26 Oct '17, 11:31

tijus's gravatar image

0★tijus
1
accept rate: 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.

link

answered 31 Aug '18, 21:21

joffan's gravatar image

5★joffan
9488
accept rate: 13%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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