Thursday, September 4, 2008 Match summaryTCHS 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 ProblemsStrangeComparatorUsed as: Division One - Level One:
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:
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
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:
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 != 0So, 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 == 0We 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
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; } }; |
|