The first of three nice problems in the "Qualification Round" for Google Code Jam 2008, our mission is to save the universe from a possible implosion caused by a search engine, how can we fix this to keep the universe in order? the answer is a click away from here.

You may start thinking how can a search engine make all the universe implode, well ... impossible happens ... all the time.

Click here to download the problem statement.

Step 1: Analyzing the problem

From the statements we know this:

• We have given a list of search engines
• We have given a list of queries
• If query is the same as the search engine name we need to send the query to another search engine
• Queries have to be processed in order
• We need to switch the minimal necessary to accomplish the statements

I made my self this question, "how long can we advance in the queries list until we necessarily switch engines?", after a ton of bad guesses a good answer came to me .. "we can count the number of different engines until our counter match the number of given engines" why? its simple, while we are processing the queries without using all the search engine queries we always have a change ... the chance of choose the search engine that wasn't count, but if the counter reaches the number of search engines there is no chance to choose any search engine the universe would implode wherever search engine you chose.

Step 2: Start coding

This part is not so hard, we can make it in few lines, let see:

First we need to make a modification on our Solution Template, because it assumes that a space means two different values, this time we are given one value on each row of input.

Before:

private function handleProcess(event:MouseEvent):void{
	// Split input data into an string array
	var inputLines:Array = inputText.text.split("\r");
	var inputData:Array = [];
	for(var index:int; index < inputLines.length; index++){
		 inputData.push((inputLines[index] as String).split(" "));
	}
	outputText.text = TransformInput(inputData).join("\r"); 
}

After:

private function handleProcess(event:MouseEvent):void{
	// Split input data into an string array
	var inputLines:Array = inputText.text.split("\r");
	var inputData:Array = [];
	for(var index:int; index < inputLines.length; index++){
		 inputData.push(inputLines[index] as String);
	}
	outputText.text = TransformInput(inputData).join("\r"); 
}

As you see, in the line 6 we are not splitting the value into an array anymore.

Now, lets continue with the logic.

// This functions implements the logic of your solution
private function TransformInput(inputData:Array):Array{
	var outputData:Array = []; // Output lines
	
	var N:int = parseInt(inputData[0]);
	var index:int = 1;
	
	for(var caseNumber:int = 1; caseNumber <= N; caseNumber++){
		var switchCount:int = 0;
		var S:int = parseInt(inputData[index]);
		index++;
		// Get the subarray with the engines
		var engines:Array = inputData.slice(index, index + S); 
		var queries:Array = [];
		index += S;
		var Q:int = parseInt(inputData[index]);
		index++;
		// Here we will look for every complete group of engines
		// in the list of queries 
		for( var i:int = index; i < index + Q; i++){
			if( queries.indexOf(inputData[i]) < 0 &&
				engines.indexOf(inputData[i]) >= 0){
				queries.push(inputData[i] as String);
				if(queries.length == engines.length){
					// We completed the entire list of engines
					// we are forced to switch
					switchCount++;
					// Start the list with the last item
					queries = [inputData[i] as String];
				}
			}
		}
		index += Q;
		outputData.push(StringUtil.substitute("Case #{0}: {1}", caseNumber, switchCount));
	} 
	return outputData;
}

Nice, isn't it? =)

Working Solution