sum of all possible game scores

Question

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

Also note that Variable Length Arrays are not allowed many times. You are making an array of size N at runtime, use 'new' keyword instead. — Pushan Gupta, Jun 09 '17 at 18:18
The first code snippet does not use `pow`, while your code does. There is no guarantee that `pow` when using integer exponents will return the correct value. [See this thread](https://stackoverflow.com/questions/25678481/why-does-pown-2-return-24-when-n-5-with-my-compiler-and-os) — PaulMcKenzie, Jun 09 '17 at 18:41
ok. but am more concerned about the logic in the first snippet. Doesn't seem correct to me. Any insights? — Rohit Roy, Jun 09 '17 at 18:43
@RohitRoy *but didn't accept:* -- Please be more specific. That quote from your post could mean anything, including getting the "right" answers algorithm-wise, but due to floating point inaccuracies, you get the wrong answer. — PaulMcKenzie, Jun 09 '17 at 18:47

Peter de Rivaz · Answer 1 · 2017-06-09T19:03:03.557

Explanation

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

sum represents the total score from all permutations of elements 0..i-1
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:

Right/Right A0,A1,A2 score = A0.A1+A1.A2
Right/Left A2,A0,A1 score = A0.A1+A2.A0
Left/Right A1,A0,A2 score = A0.A1+A2.A0
Left/Left A2,A1,A0 score = A0.A1+A2.A1

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

consider the sequence, A0, A1, A2. Correct answer would be 2 *(A0.A1 + A2.A1 + A0.A2); however this logic would give answer as 4*A0.A1 + 2*A1.A2 + 2*A0.A2 I agree there would be a doubling in the permutations when we add an Ai, but how does this double the sum? (we are only supposed to add neighbour's product when Ai is considered) — Rohit Roy, Jun 09 '17 at 18:18
@RohitRoy Regardless of this, just the usage of the `pow` function in your code can cause trouble. — PaulMcKenzie, Jun 09 '17 at 18:44
I believe that 4*A0.A1 + 2*A1.A2 + 2*A0.A2 is the correct output, I've added an explanation to the answer. — Peter de Rivaz, Jun 09 '17 at 19:01

sum of all possible game scores

1 Answers1

Explanation

Example