SRM 549... I had a bad day with a very slow 250 and a 600 that I solved but could not debug fast enough. I think the problem set itself was fine and interesting, albeit perhaps imbalanced (which happens 90% of the time). But the statements were just not clearly explained. Specially, the lack of images or better explanations in 250.
Div1 250: The one with cones
So, what is an apex? Those of us who did not learn basic geometry in English probably have no idea. I had to google apex, it turns out it is just the top vertex of the cone. So in fact, the distance from a cone's base to the apex is giberish for the word "height". It was still pretty hard to understand what the condition for a top cone to match a bottom cone.
Anyway, we have a list of top cones, each with radius and heights, there is a correct way (which is impossible to understand) which defines a condition in which a top cone can be used in combination with a bottom cone to make a wizard hat. What is the maximum number of hats you can make?
The problem is just a maximum bipartite matching problem. There is probably a way to solve the problem without max flow or the Hungarian algorithm. But that requires you to actually understand the rule that determines whether you can match a top cone with a bottom one. But I solved it with max flow. Basically, pasting max flow and preparing the bipartite matching was the easiest part that took me less than a minute. The problem was to then just find what the condition was...
At the end, I guessed it. If you are going to place a cone on top of another, then you can think of the cones as straight triangles. Then when placing a cone on top of another, you are interested in the height at which the width of the top cone intersects the lower cone. It is much, much, much easier with a image:
The trick is to find the line equation that would give us the y-position at which the bottom cone distance from axis to hypotenuse is equal to the top cone's width. Then you can find the position at which the apex (top vertex) of the top cone will end. Compare this position with the bottom cone's height, it must be higher. (Also compare the widths before doing all of this, the top cone's width must be smaller.
bool canDo(int topHeight, int topRadius, int bottomHeight, int bottomRadius)
{
if (topRadius < bottomRadius) {
// The equation is:
// y = bottomHeight - (x/bottomRadius) * bottomHeight
// then:
// bottomHeight - (x/bottomRadius) * bottomHeight + topHeight
// >
// bottomHeight
//
// or:
return ( topRadius*bottomHeight < topHeight*bottomRadius );
}
return false;
}
Once I guessed this rule, I implemented it and it passed the examples. I submitted it and it turns out to be fine. Sorry but, I would have rather not spent 95% of the time trying to guess what the problem statement wanted. It is worse because at the end few people solved 600 so the difference between a good rank and a bad one was mostly defined by speed in this problem.
Div1 600: The one with hats in grid
This one had the clarity issue, albeit not as badly as the 250.
You are given a board (at most 13x13) which contains hats (at most 13) in some of the cells. There is a list of coins (less than or equal to the number of hats), that the wizard placed in such a way that each hat has a coin. You can make at most numGuesses guesses which involve picking one hat, one at a time. After you pick a hat but before you get to see its contents, the wizard is allowed to "reshuffle" the coins in the hats. This was the first point of confusion, after asking the admins, it turns out that the "reshuffling" is not random, instead, the wizard will place each coin in whatever hat he wants. However, the reshuffling will not change the contents of hats you have already picked before.
So in fact, whenever you pick a hat, the wizard can do whatever he likes and thus it does not really matter what was inside the hat before you picked it, the wizard will just give you the coin he likes the most or no coin at all. The game would be pointless if it was not for the following condition: At any point in time, for each row, the sum between the number of coins and hats in the row is even. And for each column, the sum between the number of coins and hats is even too.
It was such a coincidence (albeit ultimately not a very happy one, because I still could not solve the problem). That I recently remembered a problem of mine called RobotKing, which was used in a netEase tournament. The problems are similar in the game theory aspect and in having to encode the state in base 3...
Base 3, so imagine we determine the current state of the game as a list of values, one for each hat in the board (there are at most 13 of them). Each value is 0 if we still have not picked the hat. 1 if we picked the hat and it turned out to have a coin and 2 if we picked the hat and it turned not to have a coin. This state is enough to represent the game. Let us say there are correctGuesses 1s in the state, it means that you have already gotten correctGuesses coins. If the wizard decides to give you a coin, there is no reason for the wizard to give you a coin with value higher than the smallest value available. So you can assume that the correctGuesses smallest coins have already been given to you. Let usedGuesses be the number of values in the state that are not 0 (the number of known hats), then you also know you have made only usedGuesses in total.
Thus we have a function f(state), where the state is such an array of values (0,1 or 3) for each of the hats. That returns the number of hats you will get if you and the wizard play optimally - make the best choices possible. The state is currently an array, but you can also represent it as a single number mask. Considering it as a base 3 number, you can extract values (0,1 or 2) from it. So, if the number of used guesses is equal to the guess limit, we got a base case, we cannot win any more coins. Else we can pick one of the hats as a guess. So, let us try each possible choice. This will allow us to implement the recurrence with dynamic programming or memoization.
Let us say we decide to uncover the i-th hat (the value of the hat must be 0, unknown). Then the wizard may have two possible choices. a) To give you no coins at all. b) To give you the smallest coin available. The wizard will pick the decision that will ultimately give you the least number of coins.
The problem is that there are times at which placing a coin in a certain hat is not possible, or not placing a coin at all in the hat is not possible (To follow the condition regarding parity of rows and columns). I basically spent 20 minutes thinking of a way to do this. At the end, I thought it was very silly I did not think of this before. The constraints are still slow - 13. So in fact, we can do this with another dynamic programming function. couldHappen(mask), the mask is in the same format as the state in the other function. It returns if a possible setting (with some hats being unknown, other hats having coins and some definitely not having coins) is possible. The base case is when there all coin positions are known, we calculate the parities and if the parities are correct, then it is possible, else it is not.
The recursion involves, when not all coin positions are known, to decide to place a coin in one of the unknown positions. If any of these possible moves leads us to a correct setting, then the original setting is also correct.
.struct MagicalHats
{
int pow3[14];
int r, c;
int numGuesses;
int mem[1594323];
char could[1594323];
vector<int> coins;
int n;
int x[13];
int y[13];
vector<int> rowpar, colpar;
int couldHappen(int mask)
{
// Is the state given by the mask possible?
char & res = could[mask];
if (res == -1) {
res = 0;
int known = 0;
{
vector<int> rp = rowpar;
vector<int> cp = colpar;
for (int i=0; i<n; i++) {
int ch = (mask / pow3[i]) % 3;
// ch == 0: unknown contents
// ch == 1: coin
// ch == 2: no coin.
if ( ch == 0) {
} else if (ch == 1) {
known++;
rp[ x[i] ] ^= 1;
cp[ y[i] ] ^= 1;
}
}
// Base case, all coin positions are known,
// verify the parities are correct.
if (known == coins.size() ) {
res = 1;
for (int i=0; i<r; i++) {
if (rp[i] == 1) {
res = 0;
}
}
for (int i=0; i<c; i++) {
if (cp[i] == 1) {
res = 0;
}
}
return res;
}
}
if ( known < coins.size() ) {
// decide to place a coin in an unknown place
res = 0;
for (int i=0; i<n; i++) {
if ( (mask / pow3[i]) % 3 == 0 ) {
// this updates the mask, the place is
// now known to have a coin:
int nmask = mask + pow3[i];
if (couldHappen(nmask)) {
res = 1;
}
}
}
}
}
return res;
}
// What is the number of coins the player wins after the
// state that is given by the mask?
int rec(int mask)
{
int & res = mem[mask];
if (res == -1) {
res = 0; // maximize this!
int usedGuesses = 0;
int correctGuesses = 0;
for (int i=0; i<n; i++) {
int ch = (mask / pow3[i])%3;
if ( ch != 0) {
usedGuesses ++;
}
if ( ch == 1) {
correctGuesses++;
}
}
if (usedGuesses == numGuesses) { //no more guesses
res = 0;
} else {
// guess something...
for (int i=0; i<n; i++) {
// what happens if I pick hat i?
if ( (mask / pow3[i])%3 == 0) {
// The wizard actually wants to minimize the result
int wiz = 130000;
// What happens if the wizard places a coin here?
int nmask = mask + pow3[i];
if ( couldHappen(nmask)) {
// coins[correctGuesses] is the smallest coin available
wiz = std::min(wiz, coins[correctGuesses] + rec(nmask));
}
// can the wizard place nothing here?
nmask = nmask + pow3[i];
if ( couldHappen(nmask)) {
wiz = std::min(wiz, rec(nmask));
}
// the maximum is what we want...
res = std::max(res, wiz);
}
}
}
}
return res;
}
int findMaximumReward(vector <string> board, vector <int> coins, int numGuesses)
{
sort(coins.begin(), coins.end());
this->coins = coins;
this->numGuesses = numGuesses;
//init powers of 3:
pow3[0] = 1;
for (int i=1; i<=13; i++) {
pow3[i] = 3*pow3[i-1];
}
//init parities and positions:
r = board.size(); c = board[0].size();
rowpar.resize(r);
colpar.resize(c);
n = 0;
for (int i=0; i<r; i++) {
for (int j=0; j<c; j++) {
rowpar[i] ^= ( board[i][j] == 'H');
colpar[j] ^= ( board[i][j] == 'H');
if (board[i][j] == 'H') {
y[n] = j;
x[n++] = i;
}
}
}
memset(could, -1, sizeof(could));
if (! couldHappen(0) ) {
return -1;
}
memset(mem, -1, sizeof(mem));
return rec(0);
}
};
I was not so lucky during the contest. Ultimately, the one bug that prevented me from submitting was : I typed int & res = mask; instead of int & res = mem[mask] ;
Outcome
Barely nothing in rating increase.
Again, I think the problems were good and interesting, but the clarity issues sort of broke the match for me. We don't want topcoder to become codeforces. Well, at least I don't...
0 comments:
Post a Comment