Thursday, January 12, 2012

Codeforces round #102 div2

This was a good problem set imho. I began the match 4 minutes late. I think I did ok. Probably I will return to division 1 unless I made a stupid mistake (which could happen).

Problem A - Help Vasilisa the Wise 2
The numbers to write in the 4 boxes are limited to 1-9 . There definitely less than 9*9*9*9 combinations to try. In fact, lower than that if we cut cases with repeated numbers. Then for each combination, just verify that the line pairs give the sums c1, c2, r2, r2, d1 and d2, respectively.

int r1 , r2; 
int c1, c2;
int d1, d2;

void solve()
{
for (int a=1; a<=9; a++) {
for (int b=1; b<=9; b++) if (a!=b) {
for (int c=1; c<=9; c++) if (c!=b && c!=a) {
for (int d=1; d<=9; d++) if (c!=d && b!=d && a!=d) {
if ( (a + d == d1)
&&(b + c == d2)
&&(b + d == c2)
&&(a + c == c1)
&&(a + b == r1)
&&(c + d == r2)
) {
cout << a << " " << b<<endl;
cout << c << " " << d<<endl;
return;
}

}

}

}

}
cout << "-1" << endl;
}



Update: Of course, with a little further thought you can find that if you just brute force for one of the boxes, the rest of the boxes can be found through simple equations like: (b = c1 - a). This faster solution wasn't needed though.

Problem C - Help Farmer
After submitting A, I noticed some fast submissions for problem C. So I gave it a try before B.

We have n = (A - 1)*(B- 2)*(C-2). We want to minimize/maximize A*B*C - n. We can try all possibilities for (A-1), note that it must be a divisor of n, hence there are O(sqrt(n)) possibilities for A. (Need to know how to iterate a number's divisors in O(sqrt(n)) time.). Second, (B-2) should be a divisor of n/(A-1), so we can also iterate through these divisors. The total complexity is sublinear (less than O(n)). It may be hard to find the actual formula. But it will work in time for n=1000000000.

In theory, A*B*C may overflow 64 bits integers. I am not sure if that is possible. But you can get rid of the triple product by just expanding A*B*C - (A-2)*(B-1)*(C-1) . If you expand that formula you will find something without A*B*C.
typedef long long int64; 
#define long int64
void solve(long n)
{
long A, B, C;

// Look for A-1
// A-1 is a divisor of n
long A1, B2, C2;
long minres = numeric_limits<long>::max();
long maxres = numeric_limits<long>::min();
for (A1 = 1; A1 <= n/A1; A1++) { //O(sqrt(n)
if (n % A1 == 0) {
long a1[2] = {A1, n / A1} ;
for (int i=0; i<2; i++) {
long n1 = n / (a1[i]);
A = a1[i] + 1;
//Given (A-1), can we find (B-2)*(C-2) ?
for (B2 = 1; B2 <= n1/B2; B2++) {
//B and C are symmetric, no need to try all ways
if (n1 % B2 == 0) {
B = B2 + 2;
C = (n1 / B2) + 2;
long dif = 2*A*B + 2*A*C - 4*A + B*C - 2*B - 2*C + 4;
minres = std::min(minres, dif);
maxres = std::max(maxres, dif);

}
}

}
}
}

cout << minres << " "<<maxres<<endl;

}
#undef long


Problem B - Help Kingdom of Far Far Away 2
This is really just a implementation problem. Due to the factors stated in the problem statement, we should really try not to parse the original number as a float. We can just use it as a string, this should avoid any incidental rounding if it can actually happen. Then it is all about parsing the original string following the problem's instructions.

My code looks awful:
string solve(string s) 
{
bool neg = (s[0] == '-');
if (neg) {
s = s.substr(1);
}
int point = 0;
while ( (s[point] != '.') ) {
point ++;
if (point == s.length()) {
s = s + ".";
break;
}
}
string dec = s.substr(point+1, 2);
int j = point;
stack<string> parts;
while (j >= 3) {
string p =s.substr(j-3, 3);
parts.push(p);
j -= 3;
}
string result = "$";
bool first = true;
if (j > 0) {
first = false;
result += s.substr(0, j);
}
while (! parts.empty() ) {
if (first) {
first = false;
} else {
result += ",";
}
result += parts.top();
parts.pop();
}
result += string(".") + dec;
if (dec.length() < 2) {
result += string(2 - dec.length(), '0');
}

if (neg) {
result = string("(") + result + string(")");
}
return result;
}


Problem D - Help General
The first step is to notice that saying the squared distance to be 5 in a grid , is the same as saying that there is a Knight (Chess piece) move between the cells. Or rather for two cells, the difference in one coordinate must be 1 and the difference in the other coordinate 2.

Thus we can read the problem as maximizing the number of knights we can place in a n x m without them attacking each other.

My tip: Try some cases in paper. You will note that for large boards, we can place Knights in cells that are adjacent diagonally.

For example, for 5x5:

xyxyx
yxyxy
xyxyx
yxyxy
xyxyx

We can place knights in either all x cells or all y cells.

However, that is only true for large boards. When minimum(n,m) is 1, then we can place knights in all cells. When minimum(n,m) is 2, then we can follow this pattern:

xx..xx..xx..x
xx..xx..xx..x ...

Update: Another easy way to solve when the minimum is 2 is to fill one of the sides with soldiers/knights, the result is the same.

You will see that once the minimum(n,m) is 3 the above property is true.

int solve(int n , int m) 
{
if (n > m) {
return solve(m, n);
}
// {n <= m}

if (n == 1) {
//Every one!
return n*m;
}
if (n == 2) {
int d = (m / 4) * 2;
if (m % 4 != 0) {
d += min(m % 4, 2);
}
return d*2;
}
// {m >= 3 && n >= 3 }
if (n*m % 2 == 1) {
return (n*m)/2 + 1;
} else {
return (n*m)/2;
}

}


Problem E - Help Caretaker

I am not very sure about this problem. Maybe optimized bruteforce works. Maybe you need something clever. I had doubts about trying dp as it would lead to some issues when building the final board and 2^18 * 9 * 9 does not seem small enough. I actually thought brute force would work. But at least my brute force solution's speed increases spectacularly between 7x7 and 7x8.

When I finished coding the bruteforce solution, there wasn't a lot of time left. So I tried an optimization such as verifying if the remaining rows are empty, we can reuse the solution for smaller n. Update: Forgot to mention that this solution turned out to still be too slow.

Also, I think that given enough time after reading the statement, it was possible to precalculate the 9*8/2 different boards off line and then just submit a solution that uses the precalculated ones.

Update: Yes, the precalculation idea was indeed a usable one.

I eventually solved the problem without need of precalculation by combining the pseudo dp idea with a way to crop the backtracking space. We intend to maximize the number of shapes we place, and thus we should avoid leaving too many empty spaces in the board as we recurse. Thus we can calculate the density of used squares / visited squares and stop the recursion if the density is too small. This combined with the pseudo-dp solves the problem.

Word on the street is that there is an overcomplicated dynamic programming solution to this. I think it might be the 9*9*2^18 solution I mentioned. But now I think it might be possible to turn it into 9*9*3^9.

7 comments :

Shuaib said...

Vexorian, I love you man (in a totally admiration sense;) ). Thanks for the excellent explanations.

Bruno said...

I second that :)

Dr. Bitboy said...

Nice quick summary, thanks!

My 8x8 bruteforce for D is still running, top says 1598 minutes so far (i think there is something wrong;-). One solution I saw simply watched the clock and returned an answer after so many ticks. Another had a precalculated solution for every possible input, yes all 81 of them.

Btw, gotta love this:

if (n == 1) {
//Every one!
return n*m;
}

wait for it ... yeah!! that moment of dawn comprehension we all live for!

Anubhaw Raj said...

vexorian,your solutions and explainations are quite gud,except for the last one("help caretaker"),can u give some more comprehensive approach to solve it......

vexorian said...

Thing is that my current solution is quite long and messy.

It is really just a couple of optimizations that started with the normal (and awfully slow) brute force solution.

There are two parts which I tried to explain in the blog:
- "Pseudo dynamic programming". Whenever my recursion reaches a new row, and it turns out that the row and all the (X-1) rows on top are all empty, then it is just as if we were solving the case when the height is X. Thus we can solve for height = 0, then height = 1 then height = 2 and just include something in the recursion to reuse the best solution for smaller heights if it is possible.

For example, imagine you are in the middle of the recursion for 5 rows and you just filled rows 1, 2 and 3. Rows 3, 4 and 5 are empty. We can just get the result for 3 rows (which will probably have some shapes) and replace the characters in those shapes with new characters A-Z that do not coincide the ones you have already added. This makes it possible to precalculate the cases in 40 minutes. But is still very slow.

- The second part is the density idea. The idea is that when you are doing backtracking for bruteforce, you should stop recursion if you find that the total number of shapes you have added so far in all your visited cells is not large enough. So you keep two variables in your recursion u, n - U is the number of used cells and n the number of cells you have already visited. Now, for optimal plaments, we want n/u to be as large as possible, and if n/u is currently too small, then it is unlikely the case we are trying is the optimal one. You need to know what is a good constant for the necessary "density" (Picking the largest one that allows the solution to run in time is good enough).

--------------
Speaking of that. If you made a solution that recursively tries to add shapes to squares but you included something that forced it stop before 3 minutes and just outpuits the current best result you found it should work (And Dr. Bitboy apparently found solutions that do this).
This approach should work for the same density idea. You will normally first try to add shapes in your recurion before trying not adding anything at all, this should mean that the optimal case is easy to find fast.

Dr. Bitboy said...

I think the search space gets smaller if you require any new piece to "touch" an existing piece. I thought there was a problem with this because sometimes you want a new piece X to leave a space between it and the existing spaces for piece Y, but I think it unlikely that any piece will touch no other pieces, so piece X will be placed further down the search path after piece Y.

Dr. Bitboy said...

Is another way to look at this as a 7x7x? ([9-2]x[9-2]x?) problem? i.e. pick any box in a 3x3 set as the anchor for a shape, there are only 49 places that anchor can go, and there are only 4 arrangements of the piece that can use each anchor. and each time you place a piece, you reduce the number of arrangements at 18 or 20 nearby anchors by 2, 3 or 4.