SRM 586 : Meh

Another bad day.

Div1 500 : Something with dynasties

Not sure what to do. I reduced it to finding out if there is a solution to a system of inequalities, where the variables are the (real) starting year of each nation's calendar. I had issues even implementing a stub code. I couldn't debug them because my valgrind was suddenly not providing line numbers. The other day, before releasing my test setup I actually tweaked my c++ build file a bit, I may have done something that gives valgrind line number amnesia. I actually spent most of the last 10 minutes (before the 10 minute mark) trying to fix this. Not like I had an actual idea of how to solve this problem.

Div1 250: The one with a function.

You are given an array `Y = { Y_0, Y_1, ... Y_(n-1) }`, the array talks about a real function `f()` with domain `[Y_0, Y(n-1)]`. For each `(i < n - 1)`, the function contains line segment between points `(i,Y_i)` and `(i+1, Y_(i+1))`.

Find an equation `y = "something"` that intersects the largest number of times with this function. And return that number of times. Of course, if a horizontal segment exists in `f()` there exists a `y` that will have infinitely many intersections, in that case return -1.

This was a good problem and I felt confident to solve it under 10 minutes. However, I had a bug (didn't notice an issue with code) which delayed me a bit past the end of the coding phase. According to KawigiEdit, I would have scored ~209 points in this problem if I opened it first. Too slow. Then it turns out that my idea was wrong anyway. So I don't think things changed much by my strategy. If I was having a good day, I *may* have found the challenge case , and maybe attempted to challenge. Who knows? I am still preferring to use my new strategy, whilst 250 is tricky, I learned a bit more by trying to solve div1 500 than by solving yet another tricky 250.

Anyway, the solution was to notice that most of the times we only need to try values from `Y[]` as the position of the horizontal line that crosses f(). This is because any intermediary point in a segment will intersect an equal or lesser number of times than the segment's extremes. So just count, for each `Y[i]`, the number of times it intersects with segments in the function

So does `y` intersect with a segment that goes from `Y[i-1]` to `Y[i]`?, if `y` lies in interval `[Y[i-1], Y[i] ]`, the answer is yes. However, the mistake I made was that I was counting some intersections twice. The same point `(x,y)` may be shared by two segments, and you only need to count once. What I did to fix this small issue was to make sure that `y` is not equal to `Y[i-1]` before counting that intersection.

However, there is a catch and it is that there are exceptions to the rule. Imagine `Y = {0, 5, 0, 5}`, in this case, neither 0 or 5 are optimal locations. 2.5 is better (3 intersections). What is up with that?

It turns out that, besides of the segment's extremes, you need to take a point (any point) between any two extremes of a segment. You only need to check once per pair of segment extremes. In fact, you can just check for every segment extreme +- 0.5 and it will suffice. +- 0.5 can be implemented easily by scaling all values by 2 so you just have to try +- 1. I hope to have a formal proof by the time the editorial is released.

int maximumSolutions(vector <int> Y)
{
    // If there is a horizontal segment, return -1:
    for (int i=1; i<Y.size(); i++) {
        if (Y[i] == Y[i-1]) {
            return -1;
        }
    }
    // Scale up all values by 2:
    for (int i=0; i<Y.size(); i++) {
        Y[i] *= 2;
    }
    int mx = 0;
    // for each y such that abs(y - Y[i]) <= 1:
    for (int i=0; i<Y.size(); i++) {
        for (int y = Y[i] - 1; y <= Y[i] + 1; y++) {
            //count the number of intersections:
            int c = (Y[0] == y);
            for (int j=1; j<Y.size(); j++) {
                if (Y[j] > Y[j-1]) {
                    c += ( (Y[j-1] < y) && (y <= Y[j]) );
                } else {
                    c += ( Y[j] <= y && y < Y[j-1] );
                }
            }
            mx = std::max(mx, c);
        }
    }
    return mx;
}

Comments, etc

Ok match, div1 500 had a too complex statement. Div1 250 was good. I am very disappointed by the low amount of python submissions. Hopefully it is because the python coders are still not aware of the news that it can be used.