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.