Can't find error - Google Code Jam problem

[georgep]

In the recent Code Jam qualification round on problem B: http://code.google.com/codejam/contest/1460488/dashboard , I got the small test case correct but the large test case wrong.

I went back to try and find the problem after the round ended and spotted 2 serious errors in my code, that had not affected the output for the small test case.

Here is the code, I will describe the errors below:

#include<iostream>
using namespace std;

int main()
{
	unsigned int tests;
	short int googlers, surprising, best;
	short int total[100];
	
	cin >> tests;
	
		for(int i = 1; i <= tests; i++)	//loops for each test case
		{
			
			cin >> googlers >> surprising >> best;	//number of dancers, number of surprising scores, best score
			
			for(int a=0; a < googlers; a++)
				cin >> total[a];
				
			int number = 0;	//number that can be equal or greater than best
			
			for(int a=0; a < googlers; a++)	//loops for each score
			{
				bool found = false;
				bool possible = false;
				
				//---first try without surprising---//
				
				for(int first = best; first <= 10 && !found; first++){ //**THIS LINE**
				for(int second=first-1; second <= first && !found; second++){
				for(int third=first-1; third <= first && !found; third++){
				
					if(first + second + third == total[a]){	//if you can make the score...
						if(first >= 0 && second >= 0 && third >= 0){ //... and none of them are illegal
						possible = true;	
						found = true;	
						}			
					}
				}				
				}
				}
					
				//---if failed without surprising try with---//	
					
				if((!found) && (surprising != 0))	//if an answer hasn't been found and there are any surprising left
				{
					for(int first = best; first <= 10; first++){ //**THIS LINE**
					for(int second=first-2; second <= first; second++){
					for(int third=first-2; third <= first; third++){
					
						if(first + second + third == total[a]){
							if(first >= 0 && second >= 0 && third >= 0){
							surprising--;	//surprising has been used so decrease accordingly
							possible = true;
							}
						}
					
					}
					}
					}
					
				}
				
				if(possible)	//if it could be greater / equal to best...
						number++;		//increase total
			}	
			
	
			
			cout << "Case #" << i << ": ";
			cout << number;
			
				if(i < tests)	//to ensure that no endline is printed at the end
					cout << endl;
		}
	
	return 0;	
}

The first error was in each FOR loop that I have marked with **THIS LINE**. Initially, I continued the loop while the first number was lower than the total. However, I now realize that this is wrong, as no number can exceed 10.

This did not affect the result for the small test case, as I don't think any of the best values were above 10 anyway.

Once I fixed it however, my program output was not the same as before, so I looked for more errors:

The second error is in the line marked //...and none of them are illegal and the matching line in the second try including surprising scores. After fixing the original problem I was faced with the issue that my program allowed values to be under 0, also illegal.

Once I fixed these 2 errors, the output went back to the original but as with the old code, it gets the practice version of the problem incorrect.

I've tried for ages looking for the error, but I can't find it. Can someone please show me where I am going wrong?

[georgep]

Really hoping someone can help with - sorry for bumping.

[cire]

A working link might help.

[georgep]

Sorry, not sure why that link is broken. I've replaced it with this one:
http://code.google.com/codejam/contest/1460488/dashboard

You'll have to navigate to the second problem "Dancing With the Googlers" though, as it seems I can't actually link to that problem.

[cire]

Try this as input:

1
5
5
2
2 3 3 4 2

5 is the correct output.

Consider that multiple values for x,y, and z can satisfy the condition that x+y+z = t, then take a fresh look at lines 47 through 61. If best == 2, and total[a] == 3 then (2,0,1) and (2, 1, 0) both satisfy the condition (on line 51.)

Because you aren't checking to see if surprising is >0, only !=0 in:

if((!found) && (surprising != 0)) //if an answer hasn't been found and there are any surprising left

Your code fails in fewer places than one might expect, as for instance in the input set:

1
3
3
2
3 3 3

surprising never equals 0. It goes from 3 to 1 to -1.

[georgep]

Thanks for the help but I know what the error was now:

I didn't end the "checking with a surprising result" set of for loops after I found an answer, unlike the "checking without surprising result" set of loops.

That meant the number of surprising left was reduced more times than it should have.

Your point is also valid though, and I will be sure to fix that problem too.

[cire]

It is the same issue. =)

You should consider an alternate approach.

#include<iostream>
using namespace std;

int main()
{
	unsigned int tests;
	short int googlers, surprising, best;
	short int total[100];

	cin >> tests;

	for(int i = 1; i <= tests; i++)	//loops for each test case
	{
		cin >> googlers >> surprising >> best;	//number of dancers, number of surprising scores, best score

		for(int a=0; a < googlers; a++)
			cin >> total[a];

		unsigned minTotal_NoSurprising = best > 0 ? best*3 - 2 : best ;
		unsigned minTotal_Surprising   = best > 1 ? best*3 - 4 : best ;

		int number = 0;	//number that can be equal or greater than best

		for(int a=0; a < googlers; a++)	//loops for each score
		{
			if ( total[a] >= minTotal_NoSurprising )
				++number ;
			else if ( surprising && total[a] >= minTotal_Surprising )
			{
				++number ;
				--surprising ;
			}

		}	

		cout << "Case #" << i << ": ";
		cout << number;

		if(i < tests)	//to ensure that no endline is printed at the end
			cout << endl;
	}

	return 0;	
}

You can capitalize on the fact that for a triplet to contain a specific 'best' value, a minimum value for total can be set based on the the triplet containing the lowest scores possible while still containing the 'best' value.

[georgep]

Sorry, still very much a beginner and I don't understand lines 19 and 20.

Otherwise that looks like a much better approach than mine. The trouble I have, is that I tend to stick with the brute force approach. I'm not sure how to learn to analyse a problem more carefully but I'm very bad at spotting things like this.

The Problem Analysis at the end of the first round made me feel very stupid :(

[cire]

If you consider a triplet that contains the 'best' value 8.

The non-surprising scores are:
(7, 7, 8)
(7, 8, 8)
(8, 8, 8)

With totals 7+7+8=22, 7+8+8=23, 8+8+8=24.

We can assume if we have a total that is 22 or larger, that the triplet satisfies the conditions set forth in the problem.

You'll note the triplet we're concerned with in this case (7, 7, 8) takes the form of (p-1, p-1, p) and to get the total we simply do p-1 +p-1 +p, which you can combine to get 3p -2. That is where the best*3-2 comes from in line 19.

The possible surprising scores are:

(6, 6, 8)
(6, 7, 8)
(6, 8, 8)

The total for the triplet we're concerned with (6, 6, 8) is 20. The triplets we're concerned with for the surprising scores take the form (p-2, p-2, p) and to get the total: p-2+p-2+p which can be combined into 3p-4. That is where the best*3-4 comes from in line 20.

That doesn't completely explain the lines, and I assume you may not be familiar with the ternary operator so I'll give you the equivalent of those lines below:

unsigned minTotal_NoSurprising ;
if ( best > 0 )
     minTotal_NoSurprising = best*3-2 ;  // or best + best-1 + best-1
else
     minTotal_NoSurprising = best ;

unsigned minTotal_Surprising ;
if ( best > 1 )
     minTotal_Surprising = best*3 - 4 ; // or best + best-2 + best-2
else
     minTotal_Surprising = best ;

You already know that for the edge case where best is 0 or 1, special handling was required to ensure your answers weren't negative. It is for the same reason the special handling exists here. (For situations where the max number is 1 or lower, surprising scores can't occur in triplets -- minTotal_Surprising being equal to minTotal_NoSurprising means that the code in the loop handles this situation correctly.)

I'm not sure how to learn to analyse a problem more carefully but I'm very bad at spotting things like this.

I find sitting down with a pen or pencil and a piece of paper is helpful. =)