@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.
@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 CodeChef: Practical coding for everyone
pls check my solution
then why subtask 2 is not being accepted i would love to hear a word form u on this
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
