Round G 2020 Google Kick Start Merge Cards Problem - Java Solution

Problem

Panko is playing a game with N cards laid out in a row. The i-th card has the integer Ai written on it.

The game is played in N - 1 rounds. During each round Panko will pick an adjacent pair of cards and merge them. Suppose that the cards have the integers X and Y written on them. To merge two cards, Panko creates a new card with X + Y written on it. He then removes the two original cards from the row and places the new card in their old position. Finally Panko receives X + Y points for the merge. During each round Panko will pick a pair of adjacent cards uniformly at random amongst the set of all available adjacent pairs.

After all N - 1 rounds, Panko's total score is the sum of points he received for each merge. What is the expected value of Panko's total score at the end of the game?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. A second line follows containing N integers, describing the initial row of cards. The i-th integer is Ai.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the expected total score at the end of the game.

y will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

In sample case #1, N = 3. The initial row of cards is [2, 1, 10]. In the first round, Panko has two choices, of which he will choose one at random.

If Panko merges the first pair (2, 1), then the row of cards becomes [3, 10], adding 2 + 1 = 3 points to his total score. In the second round, there is only one pair remaining (3, 10). If he merges them, the row of cards becomes [13], adding 3 + 10 = 13 points to his total score. Panko ends the game with 3 + 13 = 16 points.
If Panko merges the second pair (1, 10), then the row of cards becomes [2, 11], adding 1 + 10 = 11 points to his total score. In the second round, there is only one pair remaining (2, 11). If he merges them, the row of cards becomes [13], adding 2 + 11 = 13 points to his total score. Panko ends the game with 11 + 13 = 24 points. Thus, the expected number of points Panko ends the game with is (16 + 24)/2 = 20.

In sample case #2, N = 5. The initial row of cards is [19, 3, 78, 2, 31]. There are too many possibilities to list here, so we will only go through one possible game:

In the first round, if Panko merges the pair (78, 2), then the row of cards becomes [19, 3, 80, 31], adding 78 + 2 = 80 to his score.
In the second round, if Panko merges the pair (80, 31), then the row of cards becomes [19, 3, 111], adding 80 + 31 = 111 to his score.
In the third round, if Panko merges the pair (19, 3), then the row of cards becomes [22, 111], adding 19 + 3 = 22 to his score.
In the fourth round, if Panko merges the pair (22, 111), then the row of cards becomes [133], adding 22 + 111 = 133 to his score.
At the end of the game explained above, Panko's total score is 80 + 111 + 22 + 133 = 346.

Java Code

import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for(int test=0; test<t; test++) { double dp[][]= new double[5000][5000]; double sum[] = new double[5000]; double s[] = new double[5000]; double e[] = new double[5000]; int n = sc.nextInt(); double a[] = new double[n]; for(int i=0; i<n; i++) { a[i] = sc.nextDouble(); s[i]=0; e[i]=0; } sum[0] = a[0]; for(int i=1; i<n; i++) { sum[i] = sum[i-1]+a[i]; } for(int i=0; i<n; i++) { dp[0][i] =0; } for(int i=1; i<n; i++) { for(int j=0; i+j<n; j++) { dp[i][j] = i*sum[i+j]; if(j>0) { dp[i][j]-=i*sum[j-1]; } dp[i][j]+=s[j]; dp[i][j]+=e[i+j]; dp[i][j]/=i; } for(int j=0; i+j<n; j++) { s[j]+=dp[i][j]; e[i+j]+=dp[i][j]; } } System.out.printf("Case #%d: %.6f\n",test+1,dp[n-1][0]); } } }

Here is the link for Google KickStart Round F 2021 Trash Bins Problem.