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.

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

Solution - *Language X*

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

Tags

• BFS
• Dynamic Programming