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);
}
};
