Pyramids

Once we enumerate all the heights of all the pyramids we could have, we could do a knapsack DP. For each pyramid, for each height, either build or don't build that pyramid, storing the number/sizes of the pyramids built for a given height to ensure we follow all the rules.

This ends up being 10^6 * # of pyramids, which ends up being 320. This is plenty fast.

We can also exchange dimensions. For a given count of pyramids, and a given height, try adding all pyramids that are smaller than the smallest one already used to reach that height (so if we used the 5th tallest pyramid to reach some height with 3 pyramids, start by using the 6th tallest. This means our DP state is the shortest pyramid used to reach that height...which means it's also the only one we need to check when trying to build

Runtime is 7*10^6 * # of pyramids, which is like 2 billion....but we can make some optimizations...since we're building tallest to smallest, as soon as we have a stack reach a given height, we don't have to stop to evaluate pyramids that reach that height anymore for greater numbers of pyramids. We can also only evaluate the pyramid heights shorter than our current shortest for a given node. These constant time improvements combined with the fact that we're precomputing still probably leave you on the edge, but it's probably fast enough.

This is the approach the solution here takes, though I think there is a bug: dp[i-1][j-height.get(k)]!=k should say ...>=k As there is nothing stopping us from building a pyramid of height A, then one of height B, and then A again. It passes all the test cases though, so it seems nothing exposes that bug

import java.util.*;
public class j {

	/**
	 * @param args
	 */
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new j().go();
	}
	private void go() {
		ArrayList<Integer> height=new ArrayList<Integer>();
		ArrayList<String> print=new ArrayList<String>();
		int l=10;
		int ls=3;
		int h=5;
		int hs=2;
		while(l<1000000||h<1000000){
			if(l<=h){
				height.add(l);
				print.add(ls+"L");
				ls++;
				l=0;
				for(int i=ls;i>0;i-=2)l+=i*i;
			}else{
				height.add(h);
				print.add(hs+"H");
				hs++;
				h+=Math.pow(hs, 2);
			}
		}
		int[][] dp=new int[7][1000001];
		for(int[] i:dp)	Arrays.fill(i, -1);
		for(int i=0;i<height.size();i++)dp[1][height.get(i)]=i;
		for(int i=2;i<dp.length;i++)for(int j=1;j<dp[0].length;j++)for(int k=0;k<height.size();k++)if(j-height.get(k)>=0&&dp[i-1][j-height.get(k)]!=-1&&dp[i-1][j-height.get(k)]!=k)dp[i][j]=k;
		int cnum=0;
		while(true){
			cnum++;
			int n=in.nextInt();
			if(n==0)break;
			int num=Integer.MAX_VALUE;
			for(int i=6;i>=0;i--)if(dp[i][n]!=-1)num=i;
			if(num==Integer.MAX_VALUE){
				System.out.printf("Case %d: impossible\n", cnum);
				continue;
			}
			System.out.printf("Case %d:", cnum);
			while(num!=0){
				System.out.print(" "+print.get(dp[num][n]));
				n-=height.get(dp[num][n]);
				num--;
			}
			System.out.println();
		}
	}
}
//Pyramids
//dp
//output