SRM 492, comments and explanation for div1 250

Before this match, I noticed how it was actually plausible I would reach 2100+ rating this time, and get to see a red sector in my rating graph. But it did not happen.

Div1 250 - TimeTravellingGardener

Once I noticed this problem, I knew it was going to take me a long time.

The idea is actually simple, imagine that at least two of the trees will stay in their position, then we can find two of such trees, and generate a straight line from them. Then we can iterate through all the other trees and see if their tops are already in the line, else verify that their tops can be reduced so that they touch the line. And pick the pair of points that would require the least amount of cuts (time traveling).

But for that, we need to ask "Is a case that leaves less than one tree intact possible?" As a matter of fact, it is, and I only found out about it after coding the two trees solution, example 1) actually has a case in which only one tree is left intact.

There are good news though, if we assume that exactly one tree will stay intact, then we can change all of the other trees' heights. The simplest thing to do in this case is to set these trees' heights to be equal to the tree that will stay intact. In fact, we can just cut all the trees so that their heights become equal to the minimum, and then we will have a straight line that will go through their tops. Since all sequences of heights will have a minimum, we can assume that the result will be n-1 in case it is not possible to pick two trees that form a valid straight line (previous step).

Back to that previous step, the checks needed for this iteration are tricky. Imagine trees i and j were picked to be part of the straight line, and we want to check if tree k belongs to that line. Assume that i < j (without loss of generality). Also assume we have arrays x[] and y[] that hold the top points' (x,y) coordinates for each tree (x would be the position of the tree and y its height). Then we can say that (dx = x[j]-x[i]) and (dy = y[j]-y[j]). We can say that the slope is dy/dx . Then what about (tx = x[k]-x[i]) ? Well, then for the point to belong to the straight line, (ty = x[k]-x[i]) must be equal to tx*(dy/dx)...

Then we have a equation;:
ty = tx*(dy/dx)

It is always recommendable not to use floating point numbers if it is not necessary, many people actually failed system tests because of precision errors, we can change last equation to:

ty * dx = tx * dy

Then we do not need integers for that. If (ty * dx = tx * dy) is true then it is not necessary to cut the tree. Otherwise it is necessary to cut the tree. There are still two things to consider, and this is the part in which I had the most trouble: a) It is not possible to "cut" a tree so that its height becomes larger than its original value. And b) It is not possible to "cut" a tree so that its height becomes negative.


For the first condition, note that it translates into: y[k] >= y[i] + tx*(dy/dx) . Because tx is the difference x[k]-x[i], so tx*(dy/dx) is going to be the wanted difference between the tree's height and y[i].

For the second condition, note that it similarly translates into: 0 <= y[i] + tx*(dy/dx).

We can get rid of floating point calculations by multiplying dx to both inequalities, but note that we have ensured dx is positive, so the directions of the inequalities will not change.

y[k]*dx >= y[i]*dx + tx*dy
(y[k]-y[i])*dx >= tx*dy
ty*dx >= tx*dy

0 <= y[i]*dx + tx*dy

If those two previous conditions are true, then it is possible to cut the tree to match the straight line, else it is not possible, so there is no solution in which both trees i and j stay intact.

Adding things up, we can code a solution...

int determineUsage(vector <int> distance, vector <int> y)
{
    int n=y.size();
    if(n<=2) {
        return 0;
    }
    ///prepare x[], note that we just renamed the height array to y[]
    int x[n];
    x[0] = 0;
    for (int i=1; i<n; i++) {
        x[i] = x[i-1] + distance[i-1];
    }
    
    
    int res = n-1;
    // It is always possible to leave at least one tree intact, just
    // pick the minimum height tree, and make the other trees' heights
    // match it.
    
    for (int i=n; i--;) {
        for(int j=i+1; j<n; j++) {
            //pick two trees i and j, j>i:
            
            int r=n-2; //r is the number of trees we sent back in time...
            bool can = true;
            for (int k=0; k<n; k++) {
                if(k!=i && k!=j) {
                    int dx = x[j]-x[i];
                    int dy = y[j]-y[i];
                    int ty = y[k]-y[i];
                    int tx = x[k]-x[i];
                    //The conditions we found...
                    if(ty*dx == dy*tx ) {
                       r--; 
                    } else if ( ( ty*dx < tx * dy ) || ( y[i]*dx+tx*dy < 0 )  ) {
                        can = false;
                    }
                }
            }
            if(can) {
                res = std::min(res,r);
            }
        }
    }
    return res;
}

During the match, I noticed most of the aspects needed for the solution early, except the second condition (that trees must not become negative after the time travel) which caused me to lose a long time debugging it.

Once I submitted 250, I barely had time to see the 550 problem, it seemed very interesting, but it is too bad 250 was such a time sink, I just didn't have enough time to think it through.

I ended up losing plenty of rating, but at least it wasn't higher than the amount of rating I won in the previous match.