# Thread: ACM Programming Contest.... Seeking Answers!

1. ## 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?

2. Did you ever try NOT using "using namespace std;" I am thinking a name collision issue on swap or qsort.
No idea if it is likely or not; I am a C programmer who from time to time tries to learn C++.

Tim S.

3. The problem is that the exercise required you to compare rankings that each judge gives each contestant. Your approach doesn't do that.

Even with that, your code is a hybrid of C and C++. Even if the judges are unfussed by what language you use, using a hybrid of two is not good form.

4. @grumpy

If you could be more specific as to how I'm failing to do what the program asked.

From the last paragraph of the description:
"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."

I read in the scores, while giving each person an id. Then once they are sorted based on score, I start with the highest ranked contestant (far end of the arrays). If the have the same id, the same contestant received the same ranking. I progress on until the end of array or a mismatch is found, then printed.

What am I missing?

Also, when you say I'm using a mix of C and C++, what are you exactly referring to? As in, what is C in the source that would not be considered C++?

EDIT:
Also, you do realize that my programs output matches that of the sample output for the given sample input? Is this just a coincidence?

5. Originally Posted by jwroblewski44
From the last paragraph of the description:
"[COLOR=#333333]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."
The approach you described is sorting contestants by scores. That is different from checking if judges ordered contestants in the same way.

Originally Posted by jwroblewski44
Also, when you say I'm using a mix of C and C++, what are you exactly referring to? As in, what is C in the source that would not be considered C++?
Depends on your definition of C++. From a "C++ as a sort-of superset of C" perspective, your code might be said to quality. From a "using idiomatic C++" perspective it does not.

Expert judges will look for idiomatic code in whatever programming language is used - it shows technical discipline by the author of that code.

The point of idioms in any programming language is using facilities of that language and its library effectively, without having to roll your own. Idiomatic code tends to be smaller (since it uses facilities that are provided by the language AND its standard library), easier to get right (reusing something that is specified in a standard is less error prone than writing new code to do the same thing).

Idiomatic C++ very rarely makes use of pointers, at least not directly. It also makes more use of - or extends if needed - facilities in the standard library. Your usage of pointers, the usage of new/delete to create an array (instead of a standard container), writing a function to do sorting (instead of an appropriate algorithm that works with iterators from a standard container), and writing a swap function are all hallmarks of hybrid C/C++.

Originally Posted by jwroblewski44
Also, you do realize that my programs output matches that of the sample output for the given sample input? Is this just a coincidence?
Maybe it is. I don't know. I certainly can't exclude that possibility.

When I saw that your description of approach was not consistent with what was asked for, I didn't bother to examine the code to see if it did something different. I only looked at the code enough to recognise it was not idiomatic C++.

Producing a given set of outputs from a given set of inputs does not demonstrate you have used the right approach to get there. I've seen lots of software that passes test cases, despite actually using a completely wrong approach.

All I'm saying is that, given the information you provided, I can understand why the judges did not accept any iteration of your code. If I was a judge (and, no, I wasn't) I would have done the same, for the reasons I explained.

6. Originally Posted by jwroblewski44
Also, when you say I'm using a mix of C and C++, what are you exactly referring to? As in, what is C in the source that would not be considered C++?
To see why it might not be considered "idiomatic C++" it might be instructive to try and change this program to make it a valid C program and see which lines needed to be changed. In your example, only a few trivial changes must be made, such as changing cin/out to scanf/printf, changing new/delete to malloc/free, etc. Also, unless you need to make your own sorting algorithm, why not use the standard library rather than defining your own? C standard library defines qsort and C++ standard library defines std::sort.

7. Yes. I agree that writing my own sort was not the best approach. Simply, I don't have much experience using the standard system sorts, but I did have access to a book with a sort method I was familiar with. So rather than flail about trying to show my command of the language, I simply used what I knew to accomplish the main objective. Also, I'm a C guy at heart, so it's hard not to stray.

I can't think of any other way of seeing if judges ranked each contestant relatively the same.... Could you point me in the right direction?

8. I'm learning C++11 here's my attempt at this contest (using your same logic...not sure if they want you to instead normalize scores between each judge...the result is the same though.
Code:
```#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <boost/regex.hpp>

struct contestant {
unsigned long score, cont_num;
bool operator<(const contestant& b) const { return score < b.score; }
};

inline bool matches_re(const std::string& s, const std::string& exp)
{
boost::regex re;
try {
re.assign(exp);
} catch (const boost::regex_error& e) {
std::cout << "regex error: " << e.what() << " code: " << e.code() << "\n";
return false;
}
return boost::regex_match(s, re);
}

inline std::string perform_judgement(unsigned long& contestants, std::vector<std::multiset<contestant>>& judge)
{
unsigned long count;

for (count = 0; count < contestants; ++count) {
for ( const auto& j : judge ) { // Sorted by scores
// Ugly but iterator doesn't support addition apparently grumble..
auto iter = j.begin();
for (unsigned long i = 0; iter != j.end() && i < count; ++i) ++iter;

if (iter->cont_num != count)
return std::to_string(count);
}
}
return count == contestants ? "agree" : "0";
}

int main(void)
{
unsigned long contestants = 0;
unsigned long caseno = 0;
std::vector<std::multiset<contestant>> judges;

do {
std::string line;
const auto& ok = std::getline(std::cin, line);
std::stringstream ss{line};

if (!ok || matches_re(line, "^\\s*\\d+\\s*"))  {
/* Report our case results */
if (contestants) {
std::cout << "Case #"
<< ++caseno
<< ": "
<< perform_judgement(contestants, judges)
<< "\n";
judges.clear(); // clear judge list for next case
}

// Received contestant count, install it
ss >> contestants;
} else if (matches_re(line, "^\\s*(?:(?:\\d+)\\s?)+")) {
unsigned long count = 0;
contestant ct;
std::multiset<contestant> scores;

// Read contestant scores into sorted order
// and remember their original number
while ( count < contestants && ss >> ct.score ) {
ct.cont_num = count++;
scores.insert((contestant){ct.score, ct.cont_num});
}

// Add these scores to the judge list
judges.emplace_back(scores);
} else {
std::cerr << "[invalid input]: " << line << "\n";
}

} while(std::cin);

return 0;
}```

9. @nonpuz

I spoke with my department chair(he was a judge during the comp) and he gave me the test cases for the problem. When I have some free time ( thanksgiving break? ), I'm going to check test my program with their test cases and see what I missed. After this, I will test your code and let you know whether or not they would have given your program 'the nod'.

10. Well once I went through and changed all the int's to long's, the program gave all the correct outputs. The issue was that I neglected to replace the int's used for the counters in the for loops.

@nonpuz

when I try to compile your code, my system can't find the "boost/regex.hpp" file.

11. Originally Posted by jwroblewski44
when I try to compile your code, my system can't find the "boost/regex.hpp" file.
That's part of the boost library. You would have to download and install it. Which would not a bad idea certainly, as it's shock full of useful stuff.
But then again, it might probably be better off just using std::regex instead, allowing you to skip the dependency on boost.

Popular pages Recent additions