Monday, November 3, 2014

UVa Problem 111 - History Grading

Problem:

Solution:

First, notice the number given are ranks. To find out the actual sequence we need to do some mapping work. In particular, we want the student answer is this form

0 1 2 3 4 5 6 8 7 9

such that the sequence represent the student's order, the number represent the actual order. Then we reduced the problem to longest increasing sub-sequence, again.

This time it is even easier because we only need the length.

The rank thing tricked me once, again, be careful reading the problem.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=47

#include "UVa111.h"

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int UVa111()
{
int num_events;
cin >> num_events;
map<int, int> actual_event_rank;
for (int event_id = 0; event_id < num_events; event_id++)
{
int event_rank;
cin >> event_rank;
actual_event_rank.insert(pair<int, int>(event_id, event_rank));
}

while (true)
{
map<int, int> student_event_id;
for (int event_id = 0; event_id < num_events; event_id++)
{
int student_event_rank;
cin >> student_event_rank;
if (cin.eof())
{
return 0;
}
student_event_id.insert(pair<int, int>(student_event_rank, event_id));
}
for (int event_rank = 1; event_rank <= num_events; event_rank++)
{
}

vector<int> score;
score.resize(num_events);
score[0] = 1;
int max_score = 1;
for (int i = 1; i < num_events; i++)
{
int best_score = 1;
for (int j = 0; j < i; j++)
{
{
int current_score = score[j] + 1;
if (current_score > best_score)
{
best_score = current_score;
}
}
}
score[i] = best_score;
if (best_score > max_score)
{
max_score = best_score;
}
}
cout << max_score << endl;
}
}