CODEWITHSUNDEEP
c++algorithm
Rohit Roy
Rohit Roy

Reputation: 21

sum of all possible game scores

I am working on a problem whose solution am unable to understand. I came up with my own solution but that isn't accepted:

N+1 numbers occur sequentially (one at a time) from A0 to AN. Each number can be placed either side of the last sequence. The score at this point would be the product of this number and its neighbor, e.g.: A0.A1.A2 or A2.A0.A1 (A2 could be placed either side of A0.A1 so scores could be A1.A2 or A2.A0; there could also be a possibility of A1.A0 before A2 came up). We need to sum up the all the possible scores in across all the possible combinations; i.e. sum of score of first sequence over N+1 numbers, then sum over some other sequence and so on and finally sum of all these sums.

Here is the logic which was found to be acceptable: 

int pwr[0] = 1;

for (int i = 1; i < 100000; i++)
  pwr[i] = (pwr[i - 1] << 1) % MOD;

extra = A0 * 2;
sum = 0;
for (int i = 1; i <= N; i++){
    Ai = scan();
    sum = (sum * 2 + Ai * extra) % MOD; //Mod is a scaling factor
    extra = (extra + pwr[i] * Ai) % MOD;
}

could somebody explain how this works?

Here is my logic (solution) to the same problem, but didn't accept:

#include <iostream>
#include <cmath>

int main()
{
    int T;
    std::cin>>T;
    long long int output[T];
    for (int i = 0; i < T; ++i)
    {
        int N;
        std::cin>>N;
        long long int inp[N+1];
        for (int j = 0; j <= N; ++j)
        {
            std::cin>>inp[j];
        }
        long long int tot = 0;
        for (int j = 0; j < N; ++j)
        {
            for (int k = j+1; k <= N; ++k)
            {
                tot += (inp[j] * inp[k] * pow(2,N-k+1));
            }
        }
        long long int num = pow(10,9) + 7;
        output[i] = tot % num;
    }
    for (int i = 0; i < T; ++i)
    {
        std::cout<<output[i]<<std::endl;
    }
    return 0;
}

Upvotes: 1

Views: 188

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Explanation

At the start of each iteration of the loop I believe:

  1. sum represents the total score from all permutations of elements 0..i-1
  2. extra represents the sum of the two edge elements for all permutations of elements 0..i-1

Also note that there are pow[i]=2^i permutations of elements 0..i.

At the start, the only permutation is [A0] which has a sum of 0, and a total edge of 2.A0 as A0 is on both the left and the right edge.

On iteration i, we are doubling the number of permutations by considering all those where Ai goes on the left, and all those where Ai goes on the right. Therefore the internal score of these permutations is 2*sum and the additional score from considering the edge samples is Ai*extra.

Also extra needs to increase by Ai for all 2^i permutations because it is either on the left or on the right in each new permutation.

Example

Consider [A0,A1,A2].

There are 4 possible ways of building up the sequence:

  1. Right/Right A0,A1,A2 score = A0.A1+A1.A2
  2. Right/Left A2,A0,A1 score = A0.A1+A2.A0
  3. Left/Right A1,A0,A2 score = A0.A1+A2.A0
  4. Left/Left A2,A1,A0 score = A0.A1+A2.A1

The total score is 4A0.A1+2A1.A2+2A2.A0

Upvotes: 1

Related Questions