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
@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
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];
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;
}
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.
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
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
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.
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.
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
