RGAME - Editorial

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];

Can someone tell what is wrong with this solution.
solution

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

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];

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;
}

}

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

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

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

In Subtask 3 pseudocode, shouldn’t it be

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

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

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.

4 Likes

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: CodeChef: Practical coding for everyone

I have used recursion in my code. Can this be the source of the problem?

Gramercy…

lol i am new :stuck_out_tongue:

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

2 Likes

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 : CodeChef: Practical coding for everyone

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

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

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;
}

}

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

@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]);

}

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

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