TopCoder SRM 507

My performance was bad. Though I correctly solved Medium, it was too slow and I made a careless mistake in Easy. Moreover, I made no challenges while there are many chances to challenge. As a result, I got 192nd place in div1 and my rating fell 27. Now my rating is 2270.

Link to TopCoder (login required)

250 CubeStickers

As I mentioned above, I made a careless mistake and my solution was successfully challenged. I had to review my solution before or after submission.

500 CubePacking

Though I finally solved this problem, I wasted much time to consider wrong ways to solve this. My approach for this problem is as follows.

First, it is obvious that the lower bound of the volume is Ns+Nb*L^3. Then let's consider the upper bound. We can pack all cubes by following way: we lines up large cubes in a straight line, then we appends small cubes to it. So the result must be greater than or equal to Ns+Nb*L^3 and lower than or equal to Ns+Nb*L^3+L^2. This problem can be solved by searching all boxes whose volume is between lower and upper bounds.

Solution in C# (which I submitted in the contest)

public class CubePacking { 
    public bool ok2(int X, int Y, int Z, int S, int B, int L) 
    { 
        int x = X / L, y = Y / L, z = Z / L; 
        if (x * y * z < B) return false; 
        return true; 
    } 

    public bool ok(int V, int S, int B, int L) 
    { 
        for (int x = 1; x * x <= V; ++x) 
        { 
            if (V % x != 0) 
                continue; 
            for (int y = 1; y * y <= V / x; ++y) 
            { 
                if (V / x % y != 0) 
                    continue; 
                if (ok2(x, y, V / x / y, S, B, L)) 
                    return true; 
            } 
            for (int y = 1; y * y <= x; ++y) 
            { 
                if (x % y != 0) 
                    continue; 
                if (ok2(V / x, y, x / y, S, B, L)) 
                    return true; 
            } 
        } 
        return false; 
    } 

    public int getMinimumVolume(int Ns, int Nb, int L) 
    { 
        int V = Ns + Nb * L * L * L; 
        while (true) 
        { 
            if (ok(V, Ns, Nb, L)) 
                return V; 
            V++; 
        } 
    } 
}