SRM 547: Scary

As I write this, there are 7 minutes left before the end of the coding phase and I have supposedly finished coding 250 and 500. Supposedly, because I have so many doubts... It is scary.

Div1 250: Expect hypotenuse!

This problem is cool. I hope it is original though it would be surprising to see nobody thought of this before. Even though it is so cool.

You are given w,x and y. At position 0, a line of integer height picked uniformly at random between 1 and x. At position w, another line this time picked between 1 and y. Return the expected length of a straight line connecting the top of each line. PS x,y < 1000000.

We cannot do a O(x*y) search trying each case. The second best choice would be a O(x) search - fix a height px for the first line and then somehow calculate the rest.

The somehow can be done by using an array acumy[i] that returns the sum of the hypotenuses of a 90 degrees triangle with base w and heights < i. This array can be accumulated in O(y) time.

With that array, you can calculate the sum between all the straight lines that could start from the first line and end in the second line. You just need to be clever about how to use it. You can later divide the sum by y and add it to a result. Then divide the total result by x.

Tons of doubts about this problem. The approach is correct, but I wonder if I have made an error somewhere. To calm myself, I coded a bruteforce solution and began running random test cases comparing the results. So far, so good.

When I submitted this I was shocked to find that almost everyone else in the room already submitted it. And a red coder already solved 500...

double brute(int w, int x, int y) { 
    double res = 0; 
    for (int px = 1; px <= x; px++) { 
       for (int py=1; py<=y; py++) { 
           double dx=w; 
           double dy = px - py; 
           res += sqrt(dx*dx + dy*dy); 
       } 
    } 
    res /= x; 
    res /= y; 
    return res; 
     
} 
double getExpectedLength(int w, int x, int y) 
{ 
    if (x <= 1000000/y) { 
        cout << brute(w,x,y) << endl; 
    } 
    acumy[0] = 0; 
    for (int i=0; i<300000; i++) { 
        double dx = w; 
        double dy = i; 
        double hyp = sqrt(dx*dx + dy*dy); 
        acumy[i+1] = hyp + acumy[i]; 
    } 
     
    double res = 0; 
    for (int px = 1; px <= x; px++) { 
        double s = 0; 
        if (y >= px) { 
            // all good 
            s = acumy[y - px + 1]; 
            if (px > 1) { 
                s += acumy[ px ] - acumy[1];  
            } 
        } else { 
            int lo = px - y; 
            int hi = px - 1; 
            s = acumy[hi+1] - acumy[lo]; 
        } 
        res +=  s / y; 
    } 
    res /= x; 
     
    return res; 
 
 
} 

Div1 500: The one with the big table

You are given a table with some height and some width. The numbers on the table are such that the cell at (i,j) has value (i*width + j). Find a subrectangle of that table such that the total sum of the rectangle is equal to S and minimize the area of the rectangle. If no rectangles exist, return -1

The trick to this problem is to notice that, given a width w for the subrectangle, you already know something about it.

It is hard to explain, but given a rectangle of width w and height h, then it will be something like this:

0 1 2 ... w
0 1 2 ... w
...
0 1 2 ... w

Added to this:

0 0 0 ... 0
W W W ... W
...
2*W 2*W 2*W ... 2*W

(Where W is the total width) And this:

K K K ... K
K K K ... K
...
K K K ... K

Where K is the value of the cell at the top-left corner of the subrectangle.

Long story short, with that knowledge, you can, given w and h, calculate K. And given K you can verify that such a rectangle exists. The constraints seem too long for this approach, except that the formula for K actually allows you to break very early. So the approach seems to be something like O(width * sqrt(height)) if not better.

I am nervous because this solution is VERY straightforward, plus the contest writers decided to include the supposed worst case in the examples. (That is never good, it might mean there is another case that is slower). I am also concerned about overflow. My solution overflows in theory, but I cannot catch a case in which that matters.

long minimalArea(int height, int width, long S) 
{ 
    pair<long, long> res = make_pair(1LL << 60, -1); 
    for (long w=1; w<=width; w++) { 
        long x = w; 
        x = (x * (x-1)) / 2;  //1e12 
         
        for (long h=1; h<=height; h++) { 
            long y = h; 
            y = (y * (y-1)) / 2; //1e12 
            y = (y * width) * w;  
            assert(x*h >= 0); 
            assert(y >= 0); 
            long ss = S - x*h - y; 
            if (ss < 0) break; 
            if (ss % (w * h) == 0) { 
                long k = ss / (w * h); 
                int i = k % width; 
                int j = k / width; 
                if (i + w <= width && j + h <= height) { 
                    res  = std::min(res, make_pair(w*h, w*h) ); 
                } 
            } 
        } 
    } 
    return res.second; 
} 

Div1 1000, something evil with polygons

Opened it. No idea what to do. Somehow I hope I am not writing the editorial because explaining this might be too hard.

Challenge phase

Challenge phase begins. Let us see what happens.

22:33 The approaches in 500 look drastically different. This is not good.

22:35 The approaches in 250 are also different to mine. errr.

22:38 Tons of challenges in 250.

And the challenge phase ends, let's see what happens...