Cent Savings

Introduction

This problem asks you to divide a list of n (2000) integers into d (20) groups, where the sum of the items in each group, mod 10, is minimized cumulatively across all d groups.

Solutions

Dynamic Programming - Slow

Idea

DP Dimensions:

• start index
• end index
• number of dividers remaining

DP Stored Value:

• max amount of money saved

Relation:

1. For every state, iterate over all possible divider locations
2. For each divider location, iterate over all possible splits of dividers into the two halves
3. choose maximum

Runtime

• size of the array * work done for each step
• n*n*d * n*d
• n^3 * d^2 = 3.2 trillion

Dynamic Programming - Faster

Idea

Realize in the above relation, instead of iterating over all divider positions and splits of remaining dividers, assume when you place a divider it is the FIRST divider location, therefore all dividers come after that divider. This eliminates a factor of d from the runtime.

Realize in the above relation, when computing the value for a given state, that if we assume we are at the first divider location, then we are only need to consider values from our current position until the end of the input. This eliminates a factor of n from our runtime.

Here we eliminated TWO dimensions.

DP Dimensions:

• Start of current grouping
• number of dividers remaining to place between our position and the end of the input

DP Value:

• max amount of money saved

Relation:

1. iterate over all possible divider positions from start value of the group until the end of the input
2. value is the sum of the amount saved for start->divider_position with NO dividers plus amount saved for divider_position->end of input with one fewer dividers
3. Choose Maximum

Runtime

n*d*d = 800000

Code

Solution - Java

import java.util.*;
public class c {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new c().go();
	}
	private void go() {
		int n=in.nextInt(),d=in.nextInt();
		int[] p=new int[n+1];
		for(int i=0;i<n;i++)p[i]=in.nextInt();
		int[][] dp=new int[n+1][d+1];
		int total=0;
		for(int i=n-1;i>=0;i--){//price with no dividers is just price of remaining items
			total+=p[i];
			dp[i][0]=round(total);
		}
		for(int i=1;i<=d;i++)for(int j=0;j<=n;j++){//for this number of items remaining
			int sum=0;
			dp[j][i]=Integer.MAX_VALUE;
			for(int k=j;k<=n;k++){
				dp[j][i]=Math.min(dp[j][i], round(sum)+dp[k][i-1]);//simulate placing the divider at every location
				sum+=p[k];
			}
		}
		System.out.println(dp[0][d]);
	}
	private int round(int total) {
		int mod=total%10;
		if(mod<5)return total-mod;
		return total-mod+10;
	}
}

Dynamic Programming - Fastest

Idea

Realize that when choosing a divider position, the amount saved before the divider can only take 10 values. Since we assumed the divider location is the FIRST divider, there will be no dividers in this first segment. As we are mod 10, there are only 10 possible values. For the Second segment, the result can only take on 10 values, BUT we can greedily select the first location a given mod occurs.

Simply: when you are at a given start position, choose the first location following with a given modulus. This is guaranteed to be at least as good as any following location of the same modulus.

NOTE: since the sum from our start position to the end of the array is fixed, the mod between our start position and a candidate divider position is directly dependent on the mod between the candidate divider position and the end.

Implementation

Before running DP, have 10 entries for each position (a) in the list, representing the FIRST location (b) following (a) such that the sum between (b) and the end of the input mod 10 is some value. Iterate backwards through the positions, calculating the modulus from the current position to the end of the list as you go. Maintain the current bests (lowest index where sum until the end of the input mod 10 is some value), and each time you reach a new item, populate that position's 10 entries with the current "bests." update the "best" list with the modulus of the current position. This takes b * n time, where b = base = 10.

During the DP, instead of analyzing all possible divider locations, only need to analyze the 10 entries in the "best" list for that location.

Runtime

n*d*b = 400000