October 10, 2018 Single Round Match 739 Editorials

SRM 739 was held on October 10th. Thanks to Blue.Mary for the problems and majk for testing the round and writing the editorials.

HungryCowsEasy – Div. 2 Easy

The limits are small, so we can afford iterating over all cow-barn pairs. For each such pair, we calculate the cow’s distance from the barn. For a fixed cow, we select the barn with the smallest distance. There can be at most two such barns, and if there are two, we pick the one with smaller x-coordinate.

 class HungryCowsEasy {
 public:
     vector findFood(vector cowPositions, vector barnPositions) {
         vector ans;
         for (int cow: cowPositions) {
             int best = 0;
             for (int i = 0; i < barnPositions.size(); ++i) { int curPos = barnPositions[i]; int bestPos = barnPositions[best]; if (abs(curPos-cow) > abs(bestPos-cow))
                     best = i;
                 if (abs(curPos-cow) == abs(bestPos-cow) && curPos < bestPos))
                     best = i;
             }
             ans.push_back(best);
         }
         return ans;
     }
  };

The complexity of this approach is O(n^2). It can also be solved in O(n log n) or even in O(n) if both arrays would be initially sorted.

ForumPostMedium – Div. 2 Medium

We start by converting the timestamps into a format that is easier to work with: the number of seconds from the midnight. Consider the difference between the two timestamps. We can observe that each potential label is used on a single interval. One can thus use few simple if statements.
One slight complication is that the post might be from a previous day. In that case, the number of seconds between the (yesterday’s) midnight and the posting time is larger than the number of seconds between the (today’s) midnight and the current time. In that case, we need to add 86400 (the number of seconds in a day) to the difference.

 class ForumPostMedium {
 public:
     string getShownPostTime(string currentTime, string exactPostTime) {
         stringstream ct(currentTime), ept(exactPostTime);
         int h, m, s; char c, d;
         ct >> h >> c >> m >> d >> s;
         int t1 = 3600*h + 60*m + s;
         ept >> h >> c >> m >> d >> s;
         int t2 = 3600*h + 60*m + s;
         int diff = t1 - t2;
         if (diff < 0) diff += 24 * 60 * 60;
         if (diff < 60) return "few seconds ago";
         else if (diff < 60 * 60) {
             stringstream ans;
             ans << diff / 60 << " minutes ago";
             return ans.str();
         } else {
             stringstream ans;
             ans << diff / 60 / 60 << " hours ago";
             return ans.str();
         }
     }
 };

The complexity of this approach is O(1).

CheckPolygon – Div. 2 Hard

In this task, one needs to carefully translate the requirements from words into code. To prevent any nasty surprises, we should perform all computations on integers, and avoid floats.
First, a few definitions:

typedef pair Point;
#define x first
#define y second

We use a simple orientation test, that returns positive value for left hand turn, negative value for right hand turn, and zero for collinear points.

int orientation(Point a,, Point b, Point c) {
    auto o = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
    return (o>0) - (o<0);
}
bool collinear(Point a, Point b, Point c) {
    return orientation(a, b, c) == 0;
}

Next we need a test to check whether a point lies on segment. To check that, all three points must be collinear, and both the x and y-coordinates of the point on the segment has to be within the bounding box of the segment:

bool onSegment(Point a, Point b, Point c) {
    return orientation(a, c, b) == 0
            && ((c.x <= max(a.x, b.x) && c.x >= min(a.x, b.x))
            && (c.y <= max(a.y, b.y) && c.y >= min(a.y, b.y)));
}

To determine whether two segments intersect, we first check whether any of the four points lies on the other segment. Then, we can use the fact that the segments intersect if and only if the points a and b are in different half-planes determined by the line cd, and the points c and d are in different half-planes determined by the line ab. This condition is easily checked using orientation tests:

bool segmentsIntersect(Point a, Point b, Point c, Point d) {
    return onSegment(a, b, c) || onSegment(a, b, d)
           || onSegment(c, d, a) || onSegment(c, d, b)
           || (orientation(a, b, c) != orientation(a, b, d)
              && orientation(c, d, a) != orientation(c, d, b))
}

Next we need a method to calculate the area. Since all the points are at integer coordinates, the area is an integer or a half of an integer, so we can again perform all calculations in integers.

ll doubleSignedArea(int N, vector P) const {
    ll area = 0;
    for (int i = 0; i < N; ++i) area += P[i].x * P[i+1].y - P[i+1].x * P[i].y;
    return area;
}

And now we put everything together. We verify two things:
No three consecutive points are collinear
No two non-consecutive line segments intersect.
If both conditions are satisfied we report the area.

class CheckPolygon {
public:
    string check(vector X, vector Y) {
        int N = X.size();
        vector P(N+2);
        for (int i = 0; i < N; ++i) P[i] = {X[i], Y[i]};
        P[N] = P[0]; P[N+1] = P[1];
        for (int i = 0; i < N; ++i) {
            if (collinear(P[i], P[i+1], P[i+2])) return "Not simple";
            for (int j = i+2; j < N; ++j) {
                if (i == 0 && j == N-1) continue;
                if (segmentsIntersect(P[i], P[i+1], P[j], P[j+1]))
                    return "Not simple";
             }
        }
        ll area = abs(doubleSignedArea(N, P));
        stringstream s;
        s << area/2 << '.' << "05"[area%2];
        return s.str();
    }
};

The complexity of this approach is clearly O(n^2).

ForumPostEasy – Div. 1 Easy

The obvious thing to do in this task is to try every possible starting time and see whether it matches the observations. The property of being the lexicographically smallest time equals to being the closest time to midnight. Note that we should parse the input just once to avoid having too large constant in the time complexity.

class ForumPostEasy {
public:
    string getCurrentTime(vector exactPostTime, vector showPostTime){
         vector Times, Result;
         for (int i = 0; i < exactPostTime.size(); ++i) { stringstream ept(exactPostTime[i]); int h, m, s; char c, d; ept >> h >> c >> m >> d >> s;
             int t = 3600*h + 60*m + s;
             Times.push_back(t);
             char ch = showPostTime[i][showPostTime[i].size()-6];
             if (ch == 'd') Result.push_back(0);
             else {
                 stringstream spt(showPostTime[i]);
                 int d; spt >> d;
                 if (ch == 'e') Result.push_back(d);
                 else Result.push_back(-d);
             }
         }
         for (int t = 0; t < 86400; ++t) {
             bool ok = true;
             for (int i = 0; i < exactPostTime.size() && ok; ++i) {
                 int exp = 0, diff = t - Times[i];
                 if (diff < 0) diff += 86400; if (diff >= 3600) exp = -(diff / 3600);
                 else if (diff >= 60) exp = diff / 60;
                 ok &= exp == Result[i];
             }
             if (ok) {
                 stringstream ans;
                 ans << t / 36000 << (t / 3600)%10 << ':'
                     << (t / 600)%6 << (t / 60)%10 << ':' << (t / 10) % 6 << t%10;
                 return ans.str();
             }
         }
         return "impossible";
     }
 };

The complexity of this approach is O(t n), where t is the number of seconds in a day.

HungryCowsMedium – Div. 1 Medium

We can binary search on the answer. How do we check whether the cows can make it in time? First note that if cow has appetite a_i and a barn has coordinate x_j, then the cow cannot possibly eat at this barn if a_i + x_j > t. For this reason, we sort all the barns by their increasing coordinate, and all cows by their decreasing appetite and use the following greedy algorithm.
We pick k such that sum_i=1^k a_i <= t – x_1. Then k of the cows with the most appetite will eat their full portion in the first barn. If there is time left in this barn, we take the k+1-th cow and use the remaining capacity. To have the maximum flexibility, it is clear that this is the first cow that should eat. In the next barn, this half-fed cow needs to eat last, and reduces the capacity accordingly.
To show that this strategy is indeed optimal, one needs to use the exchange argument to show that we can avoid the following configurations in an optimal solution:
a cow that eats at both i-th and j-th barn where j-i >= 2
two cows that eat at both i-th and i+1-th barn
cows a_i > a_j eating (at least partially) at barns x_k > x_l, respectively

class HungryCowsMedium {
public:
    ll getWellFedTime(vector  C, vector  B) {
        sort(C.begin(),C.end());
        sort(B.begin(),B.end());
        return binary_search_smallest(0LL, ll(4e11), [&](ll T) {
            auto cow = C.rbegin(); ll time = 0;
            for (auto barn = B.begin(); barn != B.end() && cow != C.rend(); ++barn) {
                if (*cow > T - *barn) return false;
                time += T - *barn - *cow;
                while (++cow != C.rend() && *cow <= time) time -= *cow;
            }
            return cow == C.rend();
        });
    }
};

MakePolygon – Div. 1 Hard

A bit of trial and error suggests that on an infinite grid, the optimal solution has area (N-2)/2. The question is how to put it into a grid that is relatively small, and how to avoid the neighbouring segments to be collinear. One approach would be to make an inward spiral, such as this one with 572 points, built from blocks of 8 points in a 2×5 rectangle.
If fewer than 500 points are requested, we may omit some of the points from either side. Keep in mind that this may introduce two collinear consecutive segments, i.e. when we remove the four points at the inner end of a spiral. To combat this, we may either remove some points from both ends of a spiral and check whether the conditions hold, or we may be more careful in the spiral construction. The approach used in the solution below is to not generate all the six points in a rectangle if we are approaching the correct number of points.
To do that in a manageable fashion, we grow two sides of the polygon, called left and right, in alternating fashion, and stop when the needed amount of points is reached. Afterwards, the left and right side of the polygon are merged together.

class MakePolygon {
public:
    int N;
    vector L, R;
    bool space(int n = 0) {
        return (L.size() + R.size() + n< N); } void left(int x, int y) { if (space() && (L.empty() || L.back() != 100*x+y) && x >= 1 && x <= 25 && y >= 1 && y <= 25) L.push_back(100*x+y); } void right(int x, int y) { if (space() && (R.empty() || R.back() != 100*x+y) && x >= 1 && x <= 25 && y >= 1 && y <= 25) R.push_back(100*x+y);
    }
    void yway(int x, int y, int d, int end) {
        bool beg = true;
        while (y != end) {
            left(x, y);
            right(x+d, y);
            if (!beg && space(4)) left(x-d, y);
            if (!beg && space(3)) left(x, y+d);
            if (!beg && space(5)) right(x+d+d, y);
            if (!beg && space(5) && y+d+d != end) right(x+d+d+d, y+d);
            left(x+d, y+d);
            right(x+d+d, y+d);
            y += d+d;
            beg = false;
        }
    }
    void xway(int x, int y, int d, int end) {
        bool beg = true;
        while (x != end) {
            if (!beg && space(4)) right(x, y-d-d);
            if (!beg && space(4)) left(x, y+d);
            left(x, y);
            right(x, y-d);
            right(x+d, y-d-d);
            if (!beg && space(5) && x+d+d != end) right(x+d, y-d-d-d);
            left(x+d, y-d);
            if (space(4)) left(x+d, y);
            x += d+d;
            beg = false;
        }
    }
    vector make(int N) {
        this->N = N;
        for (int j = 0; j <= 8; j += 4) {
            yway(1+j, 1+max(j-2,0), 1, 25-j); left(2+j, 25-j);
            xway(3+j, 25-j, 1, 25-j); left(25-j, 24-j);
            yway(25-j, 23-j, -1, 1+j); left(24-j, 1+j);
            xway(23-j, 1+j, -1, 5+j); left(5+j, 2+j);
        }
        reverse(L.begin(),L.end());
        L.insert(L.end(), R.begin(), R.end());
        return L;
    }
};