|
Match Editorials |
Thursday, September 4, 2008
Match summary
TCHS SRM 56 was more difficult than a typical SRM, with a low success rate in both the medium and hard problem. Only 2 coders were able to solve all three problems, the winner wcao and the runner-up gnocuil. Both of them have competed at TC for less than a year, and they are already yellow in the regular Algorithm bracket as well. Good luck to the both of you at becoming red!
Finishing out the top 5 were AndyFang, Hornax and Zuza.
The Problems
StrangeComparator
Used as: Division One - Level One:
Value 250 Submission Rate 64 / 69 (92.75%) Success Rate 63 / 64 (98.44%) High Score Zuza for 249.14 points (1 mins 40 secs) Average Score 225.73 (for 63 correct submissions)
This was the only easy problem of the SRM, and it was very easy. To pass system test, you had to implement a function which did what the problem statement told you to do.
vector<string> compareString(vector<string> a, vector<string> b)
{
vector<string> ret;
for(int i = 0; i < a.size(); i++)
{
if(a[i].size() != b[i].size()) ret.push_back("No");
else
{
int wrong = 0;
for(int j = 0; j < a[i].size(); j++)
{
if(a[i][j] != b[i][j]) wrong++;
}
if(wrong > 1) ret.push_back("No");
else ret.push_back("Yes");
}
}
return ret;
}
Playlist
Used as: Division One - Level Two:
Value 500 Submission Rate 16 / 69 (23.19%) Success Rate 6 / 16 (37.50%) High Score Zuza for 411.52 points (13 mins 48 secs) Average Score 275.40 (for 6 correct submissions)
When I was solving this SRM in the practice room, this question tricked me a couple of times and bamboozled me for a good hour. For me, it was harder than the 1000-point problem. I submitted 2 or 3 wrong solutions before coming to the right answer.
The issues and faulty logic I encountered came from trying to tackle this problem head on. I attempted to write code which calculated the "possible spots" to put good songs based on each spot's frequency in the playlist, which is easy, and then used that to optimally assign good songs to some subset of those spots. This failed because, as I found out, my logic couldn't deal with cases where there were many more "possible spots" than good songs. Try as I might, I couldn't make progress thinking about the problem this way.
So, I decided to take a different approach. Instead of trying to directly calculate the optimal solution, I just calculated what the best_score of the optimal solution would be. To do this, you just choose the M most frequently played positions in the playlist, where M is the size of best , and take the total number of points earned by putting good songs in those positions.
With this information, my code then iteratively builds the optimal solution. Starting at position 0 in the playlist, and working forward, at each position i I iterate over all the song numbers I have yet to add to the playlist, in order. With each song j reached, I try to add it to my optimal solution at position i, and then calculate to see the best score I could get. If this is equal to the best_score, I keep song j at position i and then continue to position i+1 .
Exercises
- What is the complexity of the following code in Big-O Notation?
- Write a solution to this problem that does not use this iterate-and-test method.
- What is the complexity of that solution?
const int MAXN = 55;
int times[MAXN];
class Playlist {
public:
int pos_score(vector<int> left, vector<int> best, int pos, int N)
{
if(pos == N) return 0;
vector<int> points;
for(int i = pos; i < N; i++)
points.push_back(times[i]);
sort(points.begin(), points.end());
int ret = 0;
for(int i = 0; i < best.size(); i++)
{
if(left[best[i]] == 0) continue;
ret += points.back();
points.pop_back();
}
return ret;
}
vector<int> trackSort(int N, vector<int> best, vector<int> order)
{
memset(times,0,sizeof(times));
for(int i = 0; i < best.size(); i++)
best[i]--;
for(int i = 0; i < order.size(); i++)
times[order[i]-1]++;
vector<int> left(N,1);
int best_score = pos_score(left,best,0,N);
vector<int> ret(N,0);
int cur_score = 0;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
if(left[j] == 0) continue;
left[j] = 0;
bool is_good = false;
for(int k = 0; k < best.size(); k++)
if(best[k] == j) is_good = true;
if(is_good) cur_score += times[i];
int total = pos_score(left,best,i+1,N);
if((total + cur_score) == best_score)
{
ret[i] = j+1;
break;
}
else
{
left[j] = 1;
if(is_good) cur_score -= times[i];
}
}
}
return ret;
}
};
BestJob
Used as: Division One - Level Three:
Value 1000 Submission Rate 12 / 69 (17.39%) Success Rate 4 / 12 (33.33%) High Score AndyFang for 676.47 points (21 mins 59 secs) Average Score 641.36 (for 4 correct submissions)
A quick definition: to make the inverse of a string a , replace each 'Y' with an 'N', and each 'N' with a 'Y'. For example, 'YNNNNY' becomes 'NYYYYN' and 'NYNY' becomes 'YNYN'.
This problem looks complicated at the beginning, but becomes very simple with one key observation. That is, if k1 != 0 or k2 != 0, then the solution, if it exists, has to equal either one of the answer strings given in the input vector, or the inverse of one of those answer strings. This is obvious, because if the solution is not, then every person answered at least one question right and one question wrong and they all belong to group 3, which is a contradiction. With this knowledge we can break down the solution into two cases:
Case A : k1 != 0 || k2 != 0
So, we know that for Case A, the solution is either one of the answer strings, or one of their inverses. To find the optimal one, we iterate over all of the answer strings, and each of their inverses, and calculate what the sizes of the three groups - g1, g2 and g3 - would be if that string was the actual list of answers for the test. If g1 == k1 && g2 == k2 && g3 == n-k1-k2 , then that string is a possible solution. Out of all the possible solutions, we return the lexographically shortest one.
Case B: k1 == 0 && k2 == 0
We can use our key observation to tell us what the solution to Case B should look like - it cannot be equal to one of the answer strings or their inverses. In fact, all those strings which do not appear in the input vector and are not inverses of the strings in the input vector are possible solutions. Therefore, we should return the lexographically smallest of them.
How do we do that? Well, lets start at the smallest string (all 'N's), and iterate through the strings in lexographic order. We return the first string we encounter which is not an answer string or the inverse of an answer string. Iterating through the strings in order is actually a tricky problem, so lets diagram out the order of strings we would check if N = 3, to see if we can find a pattern to code:
N N N N N Y N Y N N Y Y Y N N Y N Y Y Y N Y Y Y
Mentally replace the N's with 0's and the Y's with 1, and you will come to a possibly startling insight - this is a ordered list of the number 0-7... in binary! Therefore, to iterate through the strings, we only have to start at 0, and continue forward, translating each number to its respective string, and then check that string to see if it is a valid solution.
Exercises
- In Case B, how come we do not check 2^(N) strings in the worst case? How many strings do we check in the worse case?
- What is the complexity in Big-O notation of the algorithm for each Case, assuming that testing for string equality takes N operations.
- Is this the smallest complexity possible?
class BestJob {
public:
int N, NQ;
vector< vector<int> > responses, inverses;
vector<int> makeinv(vector<int> answers)
{
vector<int> ret;
for(int i = 0; i < NQ; i++)
{
ret.push_back(1-answers[i]);
}
return ret;
}
int correct(vector<int> person, vector<int> data)
{
int ret = 0;
for(int i = 0; i < NQ; i++)
if(person[i] == data[i]) ret++;
return ret;
}
string convert(vector<int> data)
{
string ret = "";
for(int i = 0; i < data.size(); i++)
{
if(data[i] == 1) ret += 'Y';
else ret += 'N';
}
return ret;
}
vector<int> nextSmallest(vector<int> current)
{
for(int i = current.size()-1; i >= 0; i--)
{
if(current[i] == 1) current[i] = 0;
else
{
current[i]++;
return current;
}
}
current[0] = -1;
return current;
}
string didIMadeMistake(int right, int wrong, vector<string> answers)
{
N = answers.size();
NQ = answers[0].size();
for(int i = 0; i < N; i++)
{
vector<int> next;
for(int j = 0; j < NQ; j++)
{
if(answers[i][j] == 'Y') next.push_back(1);
else next.push_back(0);
}
responses.push_back(next);
}
for(int i = 0; i < N; i++)
inverses.push_back(makeinv(responses[i]));
if(right == 0 && wrong == 0)
{
vector<int> test(NQ,0);
while(true)
{
int ok = 1;
for(int i = 0; i < N; i++)
{
int score = correct(responses[i],test);
if(score == 0 || score == NQ)
{
ok = 0;
}
}
if(ok == 1) return convert(test);
test = nextSmallest(test);
if(test[0] == -1) break;
}
return "";
}
string best = "";
for(int i = 0; i < 2*N; i++)
{
vector<int> possible;
if(i < N) possible = responses[i];
else possible = inverses[i-N];
int numberW = 0, numberR = 0;
for(int j = 0; j < N; j++)
{
int score = correct(responses[j],possible);
if(score == 0) numberW++;
else if(score == NQ) numberR++;
}
if(numberW == wrong && numberR == right)
{
if(best.size() == 0 || convert(possible) < best)
best = convert(possible);
}
}
return best;
}
};
