# UVA #10258 - Contest Scoreboard

The problem statement is here.

## Problem Description

The task is to rank the contestants in the contest based on following criteria

1. Contestants are ranked first by the number of problems solved (the more the better)
2. then by decreasing amounts of penalty time
3. If two or more contestants are tied in both problems solved and penalty time, they are displayed in order of increasing team numbers.

## How Penalty time is calculated

Penalty time is computed as the number of minutes it took for the first correct submission for a problem to be received plus 20 minutes for each incorrect submission received prior to the correct solution.

The penalty time will be considered only if the problem is solved. There will not be any penalty if the problem is not solved even if the several Incorrect submissions were made. A problem is solved if any of the submissions for that problem is judged correct.

## Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

Input consists of a snapshot of the judging queue, containing entries from some or all of contestants 1 through 100 solving problems 1 through 9. Each line of input will consist of three numbers and a letter in the format contestant problem time L

where L can be ‘C’, ‘I’, ‘R’, ‘U’ or ‘E’. These stand for Correct, Incorrect, clarification Request, Unjudged and Erroneous submission. The last three cases do not affect scoring. Lines of input are in the order in which submissions were received.

## Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

Output will consist of a scoreboard sorted as previously described. Each line of output will contain a contestant number, the number of problems solved by the contestant and the time penalty accumulated by the contestant. Since not all of contestants 1-100 are actually participating, display only the contestants that have made a submission.

## Algorithm

for every test_case
for every submission
If a new contestant submitted a solution to a problem
consider the user for the rest of the contest
judge the solution to the problem
else
if the problem has not already been solved
judge the solution to the problem

calculate the penalty time for solved problems for every contestant
print it


## Data Structure

struct board

• contestant: id of the contestant
• nproblem: no of problem solved by the contestant
• problem[1..9]: 1 if ith problem is solved by the contestant else 0
• penalty[1..9]: total penalty time for the problem to be solved by contestant
• time: total penalty time for whole contest awarded to the contestant

Any suggestions for improving efficiency or readability?

#include <iostream>
#include <algorithm>
#include <sstream>
#include <vector>

using namespace std;

struct board
{
int contestant;
int nproblem;
int problem;
int penalty;
int time;
board(int c): contestant(c), nproblem(0)
{
time = 0;
for ( int i = 0; i < 10; ++i )
{
problem[i] = 0;
penalty[i] = 0;
}
}
};

inline void init(int index[])
{
for ( int i = 0; i < 101; ++i )
index[i] = -1;
}

void judge(board &b, const int &problem, const int &time, const char &L)
{
if ( L == 'C' )
{
++b.nproblem;
b.problem[problem] = 1;
b.penalty[problem] += time;
}
else if ( L == 'I' )
{
b.penalty[problem] += 20;
}
}

bool operator<(const board &b1, const board &b2)
{
if ( b1.nproblem > b2.nproblem )
return true;
if ( b1.nproblem == b2.nproblem && b1.time < b2.time )
return true;
if ( b1.nproblem == b2.nproblem && b1.time == b2.time
&& b1.contestant < b2.contestant )
return true;
return false;
}

void calc_time(vector<board> &v)
{
for ( vector<board>::iterator it = v.begin(); it != v.end(); ++it )
{
for ( int i = 1; i < 10; ++i )
{
if ( it->problem[i] == 1 )
it->time += it->penalty[i];
}
}
}

int main()
{
int T;
string s;
int contestant, problem, time;
char L;

cin >> T;
getline(cin, s);
getline(cin, s);
for ( int t = 1; t <= T; ++t )
{
int index;
init(index);
vector<board> v;

while( getline(cin, s) )
{
if ( s == "" ) break;

istringstream iss(s);
iss >> contestant >> problem >> time >> L;

if ( index[contestant] == -1 )
{
v.push_back(*new board(contestant));
index[contestant] = (int)v.size() - 1;
judge(v[index[contestant]], problem, time, L);
}
else
{
if ( v[index[contestant]].problem[problem] == 0 )
{
judge(v[index[contestant]], problem, time, L);
}
}
}
calc_time(v);
sort(v.begin(), v.end());
for ( vector<board>::iterator it = v.begin(); it != v.end(); ++it )
cout << it->contestant << ' ' << it->nproblem << ' ' << it->time << endl;
if ( t < T )
cout << endl;
}
return 0;
}


Refactored Code

The changes in the code is suggested by vnp

#include <iostream>
#include <algorithm>
#include <sstream>
#include <vector>

struct board
{
int contestant;
int nproblem;
int problem;
int penalty;
int time;
board(int c): contestant(c), nproblem(0)
{
time = 0;
for ( int i = 0; i < 10; ++i )
{
problem[i] = 0;
penalty[i] = 0;
}
}
void calc_time()
{
for ( int i = 1; i < 10; ++i )
{
if ( problem[i] == 1 )
time += penalty[i];
}
}
};

inline void init(int index[])
{
for ( int i = 0; i < 101; ++i )
index[i] = -1;
}

void judge(board &b, const int &problem, const int &time, const char &L)
{
if (b.problem[problem] == 1)
{
return;
}
if ( L == 'C' )
{
++b.nproblem;
b.problem[problem] = 1;
b.penalty[problem] += time;
}
else if ( L == 'I' )
{
b.penalty[problem] += 20;
}
}

bool operator<(const board &b1, const board &b2)
{
if ( b1.nproblem > b2.nproblem )
return true;
if ( b1.nproblem == b2.nproblem && b1.time < b2.time )
return true;
if ( b1.nproblem == b2.nproblem && b1.time == b2.time
&& b1.contestant < b2.contestant )
return true;
return false;
}

int main()
{
int T;
std::string s;
int contestant, problem, time;
char L;

std::cin >> T;
getline(std::cin, s);
getline(std::cin, s);
for ( int t = 1; t <= T; ++t )
{
int index;
std::fill(index, index + 101, -1);
std::vector<board> v;

while( getline(std::cin, s) )
{
if ( s == "" ) break;

std::istringstream iss(s);
iss >> contestant >> problem >> time >> L;

if ( index[contestant] == -1 )
{
v.push_back(*new board(contestant));
index[contestant] = (int)v.size() - 1;
}
judge(v[index[contestant]], problem, time, L);
}

for ( std::vector<board>::iterator it = v.begin(); it != v.end(); ++it )
it->calc_time();

sort(v.begin(), v.end());
for ( std::vector<board>::iterator it = v.begin(); it != v.end(); ++it )
std::cout << it->contestant << ' ' << it->nproblem << ' ' << it->time << std::endl;
if ( t < T )
std::cout << std::endl;
}
return 0;
}

• Now your code may be working, but your question should include more details about what your code does, and what problem it solves. The link is not enough. Consider reading: meta.codereview.stackexchange.com/a/2438/31503 – rolfl Mar 27 '16 at 14:26

• The judgement is split into two unrelated fragments: the judge function and the v[index[contestant]].problem[problem] == 0 test. Looking at judge() it is very hard to say that submissions are handled correctly.

I recommend to consolidate judgement in a single place:

void judge(board &b, const int &problem, const int &time, const char &L)
{
if (b.problem[problem] == 1) {
return;
}
if ( L == 'C' ) {
++b.nproblem;
b.problem[problem] = 1;
b.penalty[problem] += time;
} else if ( L == 'I' ) {
b.penalty[problem] += 20;
}
}


and relieve the main loop from any judgement:

    if (index[contestant] == -1) {
v.push_back(*new board(contestant));
index[contestant] = (int)v.size() - 1;
}
judge(v[index[contestant]], problem, time, L);

• Computation of a contestant's total penalty definitely should be a board member function.

• init is not a very meaningful name. Also consider replacing it with

std::fill(index, index + 101, -1);

• If features are available, change for loops to range-based:

for (auto it: v)

• Avoid using namespace std;