ACM Programming Contest.... Seeking Answers!
Hello, all!
First off, this is program from the ACM programming contest, of which today I and two teammates competed. We managed to solve two of nine correctly, but sadly the two programs I was responsible for were never accepted.
I am hoping that someone here can help me understand what I overlooked. Don't worry, the contest is over, so you are not helping me cheat. We had no access to the internet during the contest.
The program I will focus on in this thread is as follows:
Rank Order
Your team has been retained by the director of a competition who supervises a panel of judges. The competition asks the judges to assign integer scores to competitors -- the higher the score, the better. Although the event has standards for what score values mean, each judge is likely to interpret those standards differently. A score of 100, say, may mean different things to different judges.
The director's main objective is to determine which competitors should receive prizes for the top positions. Although absolute scores may differ from judge to judge, the director realizes that relative rankings provide the needed information -- if two judges rank the some competitors first, second, third, ... then they agree on who should receive the prizes.
Your team is to write a program to assist the director by comparing the scores of pairs of judges. The program is to read two lists of integer scores in competitor order and determine the highest ranking place (first place being highest) at which the judges disagree.
Input
Input to your program will be a series of score list pairs. Each pair begins with a single integer giving the number of competitors N, 1 < N < 1,000,000. The next N integers are the scores from the first judge in competitor order. The are followed by the second judge's scores -- N more integers, also in competitor order. Scores are in the range 0 to 100,000,000 inclusive. Judges are not allowed to give ties, so each judge's scores will be unique. Values are separated from each other by one or more spaces and/or newlines. The last score list pair is followed by the end-of-file indicator.
Output
For each score pair, print a line with the integer representing the highest-ranking place at which the judges do not agree. If the judges agree on ever place, print a line containing only the word 'agree'. Use the format below: "Case", one space, the case number, a colon and one space, and the answer for that case with no trailing spaces.
Sample Input
4
3 8 6 2
15 37 17 3
8
80 60 40 20 10 30 50 70
160 100 120 80 20 60 90 135
Sample Output
Case 1: agree
Case 2: 3
The following is (roughly, I'm retyping now my memory):
Code:
#include <iostream>
using namespace std;
struct contestant
{
int score,
cont_num;
};
void swap( contestant a[], int i, int j );
void qsort( contestant a[], int left, int right );
int num_of_conts;
int case_num = 1;
int main(){
cin >> num_of_conts;
while( cin )
{
contestant * judge1 = new contestant[num_of_conts]; // list for each judges scores
contestant * judge2 = new contestant[num_of_conts]; // same index means same contestant, just score from diff judge
for( int i = 0; i < num_of_conts; i++ )
{
cin >> judge1[i].score;
judge1[i].cont_num = i;
}
for( int i = 0; i < num_of_conts; i++ )
{
cin >> judge2[i].score;
judge2[i].cont_num = i;
}
// sort both arrays of contestants by score, from lowest score to highest
qsort( judge1, 0, num_of_conts - 1 );
qsort( judge2, 0, num_of_conts - 1 );
int i;
for( i = num_of_conts - 1; i >= 0; i-- )
if( judge1[i].cont_num != judge2[i].cont_num )
break;
cout << "Case " << case_num++ << ": ";
if( i == -1 )
cout << "agree" << endl;
else
cout << num_of_conts - i << endl;
delete [] judge1;
delete [] judge2;
cin >> num_of_conts;
}
return 0;
}
void swap( contestant a[], int i, int j )
{
contestant temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void qsort( contestant a[], int left, int right )
{
int i, last;
if( left >= right )
return;
swap( a, left, ( left + right ) / 2 );
last = left;
for( i = left + 1; i <= right; i++ )
if( a[i].score < a[left].score )
swap( a, ++last, i );
swap( a, left, last );
qsort( a, left, last - 1 );
qsort( a, last + 1, right );
}
The logic is fairly simple:
*chug in the scores
*sort contestants based on scores
*iterate along the list of contestants, from best to worst, breaking on
mismatch
The judges never accepted any iteration of this code. All I could think of doing was switching most/all the ints to long and then long longs in case of any overflows.
Any thoughts on why it was never accepted?
