We have to make a program that tells what is the smallest set of prices needed to change in order to have a growing price list. This time we need to think a little bit more, why? because if we don't think before coding our program can be dealing with 2 at the power of 64 iterations a total of 18446744073709551616 iteration which is hard even if your PC have the best processor in the market.

Click here to download the problem statement.

This solution was posted by Igor Naverniouk, in the Google Code Jam Group at Google Groups the author of the python code is Jeff Tamer. I'm not python fluent so I could have misunderstood the logic.

Step 1: Analyzing the problem

Here we have two lists, the first with a product's name and the second with our first guess of the product's prices, both lists are ordered based on the actual prices, and we need to change the smallest set of prices.

This is represented as follows:

x1, x2, x3, ..., xi, ..., xn // Product names
y1, y2, y3, ..., yi, ..., yn // Product prices

And don't forget that one condition is the statement is that y_i have to be minor than y_i+1 because the list is ordered.

What we need is to know which of the prices have to be changed, in general if y_i have to be changed or not, this is a yes or not question, as the problem statement says, for the large data set we can get a maximum of 64 items; another thing we need to know is what is the price of the last price that wasn't changed as a reference to evaluate if the price is actually growing.

For y_i we will try both cases, the case when it changes, and the another where it doesn't change, with this we don't have to worry about y_i because we have covered it in all cases, good news is that we just reduced the number of items by one, bad news is that this way we are still trying with all cases (2ⁿ) =(.

In the image we can analyze graphically what is happening with the items when we decide to use both cases for y_i, in this small graphic we have FOUR! times the same subtree for y_i+2 and EIGHT! times the same subtree for y_i+3, imaging this, your program is processing the item y_i+3 8 times, and the only information to vary the result is the last price that wasn't changed, then instead of calculating everything 8 times, we can process it the first time, save the result in a cache (we can use a variable for this) and if in the other 7 times we have same the scenario (same last price that wasn't changed) we read the cache instead of calculating everything again =), of course if is not the same scenario we need to calculate the new result and save it in the cache variable.

Step 2: Start Coding

We were talking about evaluating the behavior for item y_i, y_i+1, y_i+2 and so on, doesn't it sound like a recursive function?

// We will use a recursive function to solve this problem
private function Solve(itemsNames:Array, itemPrices:Array, currentPosition:int, lastPriceNotChanged:int, cache:Array):Array{
	var answer:Array  = [];
	if(currentPosition == itemsNames.length) return []; // We reached the end of the list
															// and return an empty answer.
	// First we look in the cache (we may have answer already)
	var savedAnswer:Array = SearchAnswer(currentPosition, lastPriceNotChanged, cache);
	// If a saved answer is found, return it.
	if(savedAnswer) return savedAnswer; 
	
	// If we got here we haven't return any answer yet, so it's time to calculate.
	
	// We need to calculate the answer for both cases
	
	// Current price changes
	answer = Solve(itemsNames, itemPrices, currentPosition + 1, lastPriceNotChanged, cache);
	
	// if the price changes, this item is part of the solution, so we add it to the answer.
	answer.push(itemsNames[currentPosition]);
	// The answer needs to be sorted.
	answer = answer.sort();
	
	// Current price doesn't change
	// This happend only if the lastPriceNotChanged is minor than the current item price
	if(lastPriceNotChanged < itemPrices[currentPosition] ){
		// Solve again but this time the current item is not part of the solution.
		var tmpAnswer:Array = Solve(itemsNames, itemPrices, currentPosition + 1, itemPrices[currentPosition], cache);
		
		// First priority is to find the smallest set
		// Second it have to be lexicographically first
		if(answer.length > tmpAnswer.length ){
			answer = tmpAnswer;
		}
		if(answer.length == tmpAnswer.length && answer.join(" ") > tmpAnswer.join(" ")){
			answer = tmpAnswer;
		}
	}
	//trace(StringUtil.substitute("{0}-{1}-{2}", currentPosition, answer.length, answer.join(":")));
	// We save the answer in the cache before return it.
	if(answer && answer.length > 0){
		// Please, read carefully
		// I'm storing the answer as a string because all objects in ActionScript3
		// are passed by reference, that doesn't happen with primitive types like String
		cache.push([currentPosition, lastPriceNotChanged, answer.join(" ")]);
	}
	
	return answer;
}

// This function return the saved answer if it exists.
private function SearchAnswer(position:int, price:int, cache:Array):Array {
	for(var i:int = 0; i < cache.length; i++){
		if(cache[i][0] == position && cache[i][1] == price){
			return cache[i][2].split(" "); // Return the stored answer
		}
	}
	return null;
}

Now we call the recursive function for each case in the input file and we are done!.

// This functions implements the logic of your solution
private function TransformInput(inputData:Array):Array{
	var outputData:Array = []; // Output lines
	// Read number of cases.
	var N:int = inputData[0][0];
	// We start with i = 1 because first row have the number of cases
	for(var i:int=1; i <= 2*N; i++){
		var cache:Array = [];
		var itemPrices:Array = [];
		for(var j:int = 0; j < (inputData[i+1] as Array).length; j++){
			itemPrices.push(parseInt(inputData[i+1][j]));
		}
		var answer:Array = Solve(inputData[i], itemPrices, 0, 0, cache);
		i++; // we add 1 to i, because each case is completed 
			 // by two imput lines
			 
		// Add a line to the output
		outputData.push(StringUtil.substitute("Case #{0}: {1}", i/2 as int, answer.join(" ")));
	}
	return outputData;
}

Final notes

First, translating this from Python to ActionScript3 took me a while because I wasn't aware that in ActionScript3 all objects are passed by reference to functions and procedures. The good news for me is that I'll participate in the contest with C# =P which is good because I'm just starting to learn ActionScript3.

Working Solution