RGAME - Editorial

c0dew0rm · January 23, 2016, 1:35am

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

c0dew0rm · January 24, 2016, 3:58am

@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

alkos · January 25, 2016, 10:22am

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

rishabh_bitg · February 15, 2016, 8:03pm

Can someone tell what is wrong with this solution.
solution

ankitkataria · April 29, 2016, 8:48am

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

imeavinash · May 9, 2016, 10:48pm

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

imeavinash · May 10, 2016, 7:14pm

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

}

vinayak_1 · May 11, 2016, 4:34pm

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

mahend_gaur · June 5, 2016, 3:24am

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

darkwin007 · June 12, 2016, 5:03pm

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

meetrockstar · July 28, 2016, 1:39am

In Subtask 3 pseudocode, shouldn’t it be

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

dr_aps_1 · August 8, 2016, 2:57pm

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

sou333 · August 30, 2016, 12:53pm

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.

americast · September 24, 2016, 10:32am

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…

gokuo · September 24, 2016, 11:06am

lol i am new

vijayiota77 · September 25, 2016, 4:41pm

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

atarekaze · November 2, 2016, 9:01pm

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

sandeeplalala · November 25, 2016, 1:00pm

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

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

riteshp887 · January 15, 2017, 8:25pm

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

}

riteshp887 · January 15, 2017, 8:31pm

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