Sunday, September 02, 2012

SRM 554

I posted something about SRM 554 TCO blog. Extra comments:

I had quite a silly luck this time. I do not why, but I took very long in the 250 points one. Probably because I went from the general case to the specific case instead of the opposite. So I was just about to solve the problem finding the union of three arithmetic sequences, until I started doing an extra analysis to notice that many of the intersections are not possible.

Pretty code for that problem:

int find(int redCount, int redHeight, int blueCount, int blueHeight) 
{
return
+ min(redCount, blueCount)
+ 1 + min(redCount-1, blueCount)
+ 1 + min(redCount, blueCount-1)
- (redHeight == blueHeight) * (min(redCount, blueCount) );
}

For div1 500, I messed up even more spectacularly. I reached the conclusion of the condition that was necessary to reach the optimal result (but I did not think to prove that it is also sufficient, knowing that it was also sufficient would have saved me a lot of problems). The problem is that after that, I used a dynamic programming approach. I took some time to code it, until I found that I was failing the last example (Which does not make sense, because the condition IS necessary). I did a quick fix by adding a dimension to the dp. The quick fix was not necessary, but it passed the examples so I submitted the problem.

Then I noticed that I had too many dimensions and my approach could be too slow (It was n6 in theory, but maybe it runs faster). I tried some random test cases, until I found one that was not timing out, but instead breaking an assertion I added while debugging the first bug. It turns out that I was sorting an array after I make the copy that was in use by the dynamic programing algorithm. So, I fixed that bug, which fixed the assertion, but now, as I suspected, was timing out. I figured that maybe that lame bug was the one that caused my initial solution to fail. There was only 1 minute left. Somehow, I managed to get rid of the extra dimension in the dp, pass examples and re-submit before the end of the coding phase.

Challenge phase was more about feeling very nervous. I felt the approach was right, but overcomplicated , so there was plenty of room for failure. At the end I passed. (yay)

Here is pretty code for it:

vector<int> find(vector<int> heights) 
{
int n = heights.size();
vector<int> res(n, 0), used(n, false);
used[0] = true;
//res[0] = 0 is always possible.
// Yes, it is always possible to choose any arbitrary first element and still
// follow the condition (non-increasing and then non-decreasing)
//
for (int i=1; i<n; i++) {
for (int j=n-1; j>=0; j--) {
if (! used[j]) {
if (heights[j] <= heights[ res[i-1] ] ) {
//this is always fine.
// If an element j exists such that:
// heights[j] < heights[res[i-1])
//
// It means that the next case was never reached. Thus it is
// still possible to do it.
//
// if heights[j] = heights[res[i-1]], then it can count as
// either of the cases and also fine.
res[i] = j;
} else {
// If the new element is greater, then it must forcefully be
// equal to the minimum of the remaining elements so that the
// rest of the elements are placed in non-decreasing order.
bool can = true;
for (int k=0; k<n; k++) {
can &= (used[k] || (heights[k] >= heights[j]) );
}
if (can) {
res[i] = j;
}
}
}
}
used[res[i]] = true;
}
return res;
}

As you can see, Figuring out (and proving) that the condition is not only necessary but also sufficient allows a VERY simple approach.

Div2 1000 was cute. Here is code for it too:

const int MOD = 1234567891; 
#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
struct TheBrickTowerHardDivTwo
{
int pow5[5];
int mem[8][48][5*5*5*5];

// I encode each state as a single number in base 5.
// (I added a fifth color that is a wildcard. So that the top-most row
// in a dp can add any colors without decreasing K).
//
// The transition array saves all the possible transitions from a state
// of colors to another AND the value we have to decrease from K.
// It is sorted non-decreasingly by the value to decrease from K, so that
// we can stop when K would get less than 0.
vector<pair<int,int> > transition[5*5*5*5];


int rec(int K, int H, int state)
{
int &res = mem[K][H][state];
if (res == -1) {
if (H==0) {
res = 1; //empty
} else {
long long tem = 0;
// Iterate through the list of transitions, try the transition
for_each(q, transition[state]) {
int nk = K - q->first;
if (nk >= 0) {
tem += rec(nk, H-1, q->second);
} else {
break;
}
}
res = (int)( tem % MOD);
}
}
return res;
}

int find(int C, int K, int H)
{
pow5[0] = 1;
for (int i=1; i<=4; i++) {
pow5[i] = 5*pow5[i-1];
}
memset(mem, -1, sizeof(mem));

// make the transitions
for (int state=0; state<pow5[4]; state++) {
for (int newstate=0; newstate < pow5[4]; newstate++) {
bool valid = true;
int krem = 0;
for (int i=0; i<4; i++) {
int x = (newstate / pow5[i])%5;
// use only C colors...
valid &= ( x < C);
// sharing face with the above brick
if ( (state/pow5[i]) % 5 == x) {
krem++;
}
// We represent the colors in this way.
// [0][1]
// [3][2]
// This means that a cube is adjacent to the next and previouis
// index. Which translates to us needing to check index (i+1)%4
int y = (newstate / pow5[ (i+1) % 4 ]) % 5;
if (y == x) {
krem ++;
}
}
if (valid && (krem <= K) ) {
transition[state].push_back( make_pair(krem, newstate) );
}
}
sort(transition[state].begin(), transition[state].end());
}
long long res = 0;
for (int i=1; i<=H; i++) {
res += rec(K, i, pow5[4] - 1 );
}
return (int)(res % MOD);
}
};

10 comments :

F'Ola Yinka said...

I still don't understand the 500-point, does the first tower always have index 0 after rearrangement?

vexorian said...

You can choose any tower for the left-most one and still be able to have optimal distance.

Demostration.

Let us say the tower has height X.

- Place tower of height X to the left most position.
- There are some towers of heights less than or equal to X, place them all next to tower X in non-increasing order.
- The remaining towers of heights greater than X are placed next, in non-decreasing order.

(The condition for optimality is for the ordering to be the opposite of a convex ordering:

x
x x
xx x
xxxx
)

Since we can place any tower we want in the first position, and the problem asks us for the lex-first ordering, then it is always better (and possible) to place tower 0 in the left-most position.

am said...

Hello vexorian, I am pretty new at algorithms in topcoder, I still learning, my question is how do you solve the 250 div2?, any special algorithm??

F'Ola Yinka said...

i misinterpreted the question. The elements of the return vector represent the indices in "heights" of the element of "heights" at a nth position, n being any index of the return vector. But I interpreted it to be them to be the positions of the elements of "heights" with corresponding indices in the return vector. Thank you for your explanation, it helped me solve the algorithm.

F'Ola Yinka said...

I dunno if Vexorian approves of this: if you don't understand what he has written, check http://folayinkacodes.blogspot.com/2012/09/topcoder-srm-554.html

vexorian said...

you can use the same solution I posted for the div1 version.

But the low constraints allow the following solution:

- Find the height of a tower that has X bricks and begins with a red brick:

(X/2) * (bh + rh) , (if X is even)
(X/2) * (bh + rh) + rh ( if X is odd).

(You alternate bricks of each color X/2 times. You might have an extra red brick if the number of bricks is odd)

Likewise, if you begin with a blue brick:

(X/2) * (bh + rh) , (if X is even)
(X/2) * (bh + rh) + bh ( if X is odd).

Since the maximum number of bricks is small, you can manually try all the valid values of X. Find the height of each of the two kinds of towers of X bricks, and MARK THE HEIGHT YOU FIND IN A BOOLEAN ARRAY. After that, just count the number of heights you marked in that array. You will need a boolean array of at most [47*47] length.

You can also use recursion, like this:


struct TheBrickTowerEasyDivTwo
{
set towers;

int rec(int h, int rc, int rh, int bc, int bh)
{
towers.insert(h);
if (rc > 0) {
rec(h + rh, bc, bh, rc-1, rh);
}
}

int find(int rc, int rh, int bc, int bh)
{
rec(rh, bc, bh, rc-1, rh);
rec(bh, rc, rh, bc-1, bh);
return towers.size();
}
};

am said...

thanks for answering vexorian It was very useful

am said...

thanks for answering F'Ola Yinka I already check all

Ravi Kiran said...

I think your 250 fails for:
1 3 3 3.
Your answer: 2
Correct answer: 3 (r, b, brb)

I think the correction to your idea must be to subtract the min(B, C) when rh = bh, and not C everytime.

vexorian said...

That's lame. Thanks.

I had min(bc, rc) during the match and before. Somehow I "figured" I could simplify the code by saying C=B, but never actually tested it. That was dumb.