Match Editorial

Match summary

The problem set in division 1 was well balanced. The easy problem was really easy and had a high success rate. The medium turned out to be more tricky than many expected, and system tests took their toll. In my opinion the hard problem from this set was pretty easy both to solve and to implement. Still, geometry problems are always tricky, and the fact that there were only 13 successful solutions proves this.

Victory went to tomek by a comfortable margin, with UdH-WiNGeR second (someone to watch out for, this is only his 7th match!) and ploh third.

In the easier division the hard problem was geometrical as well, and it proved to be tough. Only seven coders managed to get it right in time, and three of them claimed the top spots: carlos.guia won, npostolov was second and Effect third.

The Problems

Value	250
Submission Rate	437 / 499 (87.58%)
Success Rate	360 / 437 (82.38%)
High Score	NB-zhanglehua for 249.95 points (0 mins 23 secs)
Average Score	211.62 (for 360 correct submissions)

Already in the problem statement it is explained why the answer is never greater than 2P.

From this, we can make a simple observation: in the optimal solution we have a≤2P and b≤2P.

As P can be at most 1000, this leaves us with at most 4 000 000 pairs (a,b) to try out. We can simply examine all of them, and for each of them compute (aX+bY) mod P.

class TheEquation {
public:
  int leastSum(int X, int Y, int P) {
    int res=2*P;
    for (int a=1; a<=2*P; a++) 
      for (int b=1; b<=2*P; b++)
        if ((a*X+b*Y)%P == 0) 
          res=min(res,a+b);
    return res;
  }
};

The running time of this solution is quadratic in P. There are more effective solutions. Try to find one that is linear in P.

Value	500
Submission Rate	241 / 499 (48.30%)
Success Rate	134 / 241 (55.60%)
High Score	RAD. for 432.10 points (11 mins 38 secs)
Average Score	265.60 (for 134 correct submissions)

Value	250
Submission Rate	365 / 378 (96.56%)
Success Rate	306 / 365 (83.84%)
High Score	Krzysan for 243.40 points (4 mins 42 secs)
Average Score	178.94 (for 306 correct submissions)

First of all, let's start by preprocessing the input: split the input string into words. Clearly, the exact words are not important, the only thing that matters are their lengths. (We could precompute these, but the constraints were so small that this was not necessary.)

With height limited to 10 000, and with letter height equal to twice the font size, the maximum font size is never greater than 5 000. This means that the number of possible font sizes is small. All we need is an efficient way how to find out whether our text fits the panel when using a given font size.

To check whether a given font size is good, we can use a simple greedy approach: Each line of text should contain as many words as possible. We will process the given words in order, and for each word we either place it on the current line (if it fits), start a new line (if it doesn't, but fits on a line by itself), or give up (if the word does not even fit on a single line).

The following function checks whether text fits on a panel with width times height pixels when using font size fontSize. Note that thanks to our implementation we don't have to handle the third case (a word that's too long) separately.

bool fits(const vector<string> &text, int width, int height, int fontSize) {
  int charWidth = fontSize + 2,   charHeight = 2*fontSize;
  int cols = width / charWidth,   rows = height / charHeight;

  if (cols==0 || rows==0) return false;
  int currentWord = 0, words = text.size();

  for (int r=0; r<rows; r++) {
    int c=0;
    while (currentWord < words) {
      int currentLength = text[currentWord].size();
      if (c > 0) currentLength++;
      if (c + currentLength > cols) break;
      c += currentLength;
      currentWord++;
    }
  }
  return currentWord == words;
}

Now all we have to do is a linear search for the largest good font size.

int largestFontSize(string text, int width, int height) {
  vector<string> T;
  stringstream SS(text);
  string S;
  while (SS >> S) T.push_back(S);
  if (!fits(T,width,height,8)) return -1;
  int res = 8;
  while (fits(T,width,height,res)) res++;
  return res-1;
}

Value	1000
Submission Rate	35 / 499 (7.01%)
Success Rate	7 / 35 (20.00%)
High Score	zyx3d for 706.01 points (20 mins 11 secs)
Average Score	530.09 (for 7 correct submissions)

Finding the intersection of a axes-parallel rectangle and a line segment is one of the most important geometry algorithms. Without actually realizing it, you encounter it often -- whenever a line or a surface is clipped to fit a window.

In this task we had to implement a significant part of the line clipping algorithm. (Still, our task was much easier, for example we didn't have to find the actual intersections. We will use this observation later.)

Geometry algorithms tend to be nasty and involve special cases. When encountering tasks like this one, it is best to slow down and double check that you thought of each and every case that might occur.

This solution will be much more verbose than what I would actually write in the contest. However, only the presentation would change (e.g., I would use static arrays of integers instead of classes), the idea would remain the same.

We will start by making classes for points, segments and rectangles:

class Point {
  public:
  int x,y;
  Point(int xx=0, int yy=0) { x=xx; y=yy; }
};

class Segment {
  public:
  Point P,Q;
  Segment(Point PP, Point QQ) { P=PP; Q=QQ; }
  bool isHorizontal() const { return P.y == Q.y; }
  bool isVertical() const { return P.x == Q.x; }
  bool intersectsSegment (const Segment &S) const;
};

class Rectangle {
  public:
  Point P,Q;
  Rectangle(const Point &PP, const Point &QQ) { P=PP; Q=QQ; }
  bool containsPoint(const Point &Z);
  bool intersectsSegment(const Segment &S);
  int area() { return (Q.x-P.x)*(Q.y-P.y); }
};

Note that our objects will contain methods for some operations we will use later. We already implemented the area of a rectangle, and checks whether a segment is horizontal or vertical.

Now we need to take the input data, and convert it from its initial representation into our points, segments and rectangles. We will write a function that will convert the input data into points. Note that we can use this function twice -- once for rectangles, once for segments.

// merge a vector<string> into a string
string merge(const vector<string> &input) {
  string result;
  for (unsigned i=0; i<input.size(); i++) result += " " + input[i];
  return result;
}

// parse a vector<string> into a vector of points
vector<Point> parse(const vector<string> &input) {
  vector<Point> result;
  stringstream SS( merge(input) );
  int x,y;
  while (SS >> x >> y) resultpush_back( Point(x,y) );
  return result;
}

For the first subproblem, we may forget about line segments. We are simply given a set of points, and for each rectangle we have to check whether the rectangle contains some of the points. This check is really simple:

bool Rectangle::containsPoint(const Point &Z) {
  if (Z.x <= P.x || Z.x >= Q.x) return false;
  if (Z.y <= P.y || Z.y >= Q.y) return false;
  return true;
}

For the second subproblem, we can already assume that no endpoint of the segment lies inside the rectangle. This leaves us with two possible cases. The first case are horizontal and vertical line segments. These are nasty, as they can have a common part with the boundary of the rectangle in several different ways. The second case are line segments that are neither horizontal nor vertical. We will handle these two cases separately.

To make the code simpler, we will define two helper functions:

// check whether x lies in [start,end]
bool contains(int start, int end, int x) { return start<=x && x<=end; }

// is the intersection of [start1,end1] and [start2,end2] non-empty?
bool intersect(int start1, int end1, int start2, int end2) {
  if (contains(start1,end1,start2)) return true;
  if (contains(start1,end1,end2)) return true;
  if (contains(start2,end2,start1)) return true;
  if (contains(start2,end2,end1)) return true;
  return false;
}

When does a horizontal line segment intersect a rectangle? First, the segment's y coordinate has to be between the rectangle's minimum and maximum y coordinate, inclusive. If it is smaller or larger, the segment is below or above the rectangle and can not intersect it.

Once we checked that the segment is in the correct horizontal strip, we need to check whether it really intersects the rectangle. This happens if and only if the intervals of their x coordinates intersect -- and this is exactly what our helper functions are for.

Vertical segments are handled in the same way, only with x and y coordinates swapped.

Now all that's left is to handle line segments that are neither horizontal nor vertical. These are the nice friendly ones with no special cases. There is always at most one intersection point. We don't even need to compute it, we just need to check whether there is one or not. To do this, we can check a simple condition:

Two line segments AB and CD intersect if and only if: A, B lie on different sides of the line CD and C, D lie on different sides of the line AB.

In our case we allow intersections at an endpoint of a line, therefore we will allow that the points A, B may also lie on the line CD, and points C, D may lie on AB. Vector (cross) product is a simple way how to check this condition:

// cross product of the vectors AB and AC
int crossProduct(const Point &A, const Point &B, const Point &C) {
  int ux = B.x-Ax, uy = B.y-A.y;
  int vx = C.x-A.x, vy = C.y-A.y;
  return ux*vy - vx*uy;
}

// do points P2 and Q2 lie on different sides of the line P1Q1 or on the line?
bool differentSides(const Point &P1, const Point &Q1,
                    const Point &P2, const Point &Q2) {
  long long cross1 = crossProduct( P1, Q1, P2 );
  long long cross2 = crossProduct( P1, Q1, Q2 );
  return (cross1*cross2 <= 0);
}

// does our segment intersect segment S?
// CAUTION!!! assumes that S is not parallel to our segment
bool Segment::intersectsSegment(const Segment &S) const {
  return differentSides(P,Q,S.P,S.Q) && differentSides(S.P,S.Q,P,Q);
}

Now we have all we need to write a function that checks whether a rectangle and a segment intersect:

bool Rectangle::intersectsSegment(const Segment &S) {
  // handle horizontal and vertical segments separately
  if (S.isHorizontal()) {
    if (!contains(P.y,Q.y,S.P.y)) return false;
    return intersect(P.x,Q.x,S.P.x,S.Q.x);
  }
  if (S.isVertical()) {
    if (!contains(P.x,Q.x,S.P.x)) return false;
    return intersect(P.y,Q.y,S.P.y,S.Q.y);
  }
  // now we know that S is neither horizontal nor vertical
  // check whether it intersects a side
  Point A(P.x,Q.y), B(Q.x,P.y);
  if (S.intersectsSegment( Segment(P,A) )) return true;
  if (S.intersectsSegment( Segment(P,B) )) return true;
  if (S.intersectsSegment( Segment(A,Q) )) return true;
  if (S.intersectsSegment( Segment(B,Q) )) return true;
  return false;
}

And finally, the main function. For each rectangle check whether it contains some endpoint. If not, check whether it intersects a segment.

vector <int> countAreas(vector <string> rectangles, vector <string> segments) {

  // parse the rectangles
  vector<Point> corners = parse(rectangles);
  vector<Rectangle> R;
  for (unsigned i=0; i<corners.size(); i+=2)
    R.push_back( Rectangle( corners[i], corners[i+1] ));

  // parse the segment endpoints
  vector<Point> endpoints = parse(segments);

  int area1 = 0, area2 = 0;

  for (unsigned i=0; i<R.size(); i++) {
    // check whether this rectangle contains an endpoint
    bool firstType = false;
    for (unsigned j=0; j<endpoints.size(); j++)
      if (R[i].containsPoint( endpoints[j] ))
        firstType = true;

    if (firstType) {
      area1 += R[i].area();
      continue;
    }

    // check whether this rectangle is intersected by a segment
    bool secondType = false;
    for (unsigned j=0; j<endpoints.size(); j+=2)
      if (R[i].intersectsSegment( Segment(endpoints[j],endpoints[j+1]) ))
        secondType = true;

    if (secondType) area2 += R[i].area();
  }

  // report the result
  vector <int> result;
  result.push_back(area1);
  result.push_back(area2);
  return result;
}

Value	500
Submission Rate	161 / 378 (42.59%)
Success Rate	61 / 161 (37.89%)
High Score	msg555 for 387.13 points (16 mins 22 secs)
Average Score	275.13 (for 61 correct submissions)

Observation 1: Gap length

The movement of all pedestrians that cross the street is continuous. Observe a gap between two pedestrians. If their speeds are not equal, its length might be increasing or decreasing, but all the time the change is continuous. Even if two pedestrians meet (and the slower one is overtaken by a faster one), the gaps around them still change continuosly.

We are looking for the firs moment when the width of one of the gaps becomes equal to or larger than carWidth. Well, but we just noticed that the lengths of gaps change continuously. A large gap can not appear by miracle, it has to grow from a smaller gap. If there is a gap carWidth+47 wide, there had to be a gap carWidth+46 wide earlier.

And thus at the very first good moment the length of the good gap will surely be exactly equal to carWidth.

(Another way of looking at this: Imagine that you are the driver. You sit in the car and watch the sizes of all the gaps change and change -- until one of them grows exactly to carWidth. At that moment you start the car and away you go.)

The only exception to this rule is the situation when there is a large enough gap right at the moment when the car arrives.

Observation 2: A pair of pedestrians

Observation 2: If there is a gap carWidth long, it has to be a gap between two of the pedestrians. (Or between a pedestrian and the side of the road where they enter. To handle this, we will add a new pedestrian that always stands there.)

Transforming the input

We will now convert the pedestrians into a more suitable format. First, suppose that the car arrives at time 0. (Subtract carArrival from the given delays.)

Now, we will imagine that the pedestrians move all the time. Not only when they cross the street, but also before and after that. The position of any pedestrian at any moment can be given as one real number: The start of the road is zero, the end is roadWidth. A negative position corresponds to a pedestrian that did not enter the street yet.

The position of pedestrian X at time 0 can be easily computed as -delay[X]*speed[X]

The advantage of this representation (position+speed instead of delay+speed) is that we can also use it to represent a pedestrian that stands at any place. Also, it will be more clear when we'll compute the pedestrians' positions at other times than 0.

Observation 3: A set of candidates

For two pedestrians with different speeds, there are exactly two moments when they are exactly carWidth apart.

Pedestrians with equal speeds are not interesting. The gap between them does not change, and thus it can not cause the event we are looking for.

Of course, at some of these moments the car will not be able to cross: Some of the events occur when the two pedestrians are not on the road, and in some cases there may be other pedestrians that block the gap.

What is important is to realize that this doesn't cause any problems. We don't care that some of these moments are bad -- all we need to know is that one of them has to be the moment we are looking for.

For N pedestrians we get at most N(N-1) moments that we need to check. (And also the moment time=0.) As there are at most 50 pedestrians, we can check all these moments, and pick the first one when the car actually can drive across.

Checking a given moment

Suppose that we picked a time T. Now, for each pedestrial compute his position at time T. Throw away those that are not on the road. Sort them, and check the gaps between them. If one of them is large enough, the car can pass, otherwise it can't.

Implementation

To avoid problems with floating point numbers, we will use fractions to represent the times and positions.

typedef pair<long long, long long> fraction;

bool isLess(const fraction &A, const fraction &B) { return A.first*B.second < A.second*B.first; }
bool isLessEqual(const fraction &A, const fraction &B) { return A.first*B.second <= A.second*B.first; }

For two pedestrians P1, P2 compute the moment when P1 will be exactly carWidth to the left of P2:

fraction process(int p1, int s1, int p2, int s2, int carWidth) {
  int d = p2-p1;
  if (d == cw) return fraction(0,1); // now
  if (s1 == s2) return fraction(-1,1); // never
  int missing = carWidth - d;
  int step = s2 - s1;
  if (step > 0) return fraction(missing,step);
  return fraction(-missing,-step); // we want a positive denumerator
}

For a pedestrian and a time, compute his position at that time:

fraction getPosition(int p, int s, fraction time) {
  long long num = p*time.second + s*time.first;
  long long denum = time.second;
  long long d = __gcd(num,denum);
  return fraction (num/d,denum/d);
}

For two positions, check whether the gap between them is large enough for the car:

bool goodGap(fraction A, fraction B, int gap) {
  fraction C(A.first + gap*A.second, A.second);
  return isLessEqual(C,B);
}

For a given moment, compute all positions and check whether the car can pass at that moment:

bool check(fraction time, vector<int> &pos, vector<int> &speed, int roadWidth, int carWidth) {
  vector<fraction> pedestrians;

  fraction LEFT(0,1), RIGHT(roadWidth,1);
  pedestrians.push_back(LEFT); pedestrians.push_back(RIGHT);

  for (int i=0; i<int(pos.size()); i++) {
    fraction now = getPosition(pos[i],speed[i],time);
    if (isLessEqual(LEFT,now) && isLessEqual(now,RIGHT))
      pedestrians.push_back(now);
  }
  sort( pedestrians.begin(), pedestrians.end(), isLess );

  int K = pedestrians.size();
  for (int i=1; i<K; i++)
    if (goodGap(pedestrians[i-1],pedestrians[i],carWidth))
      return true;
  return false;
}

And finally the main function: generate all the candidate moments, and find the first one that actually works.

#define FOREACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)

double passTime(vector <string> pedestrians, int roadWidth, int carWidth, int carArrival) {
  int N = pedestrians.size();
  vector<int> delay(N);
  vector<int> speed(N);
  vector<int> position(N);
  for (int i=0; i<N; i++) {
    stringstream SS(pedestrians[i]);
    SS >> delay[i] >> speed[i];
    delay[i] -= carArrival;
    position[i] = - delay[i] * speed[i];
  }

  vector<fraction> candidates;
  candidates.push_back( fraction(0,1) );
  for (int i=0; i<N; i++) {
    fraction F;
    for (int j=0; j<i; j++) {
      F = process(position[i],speed[i],position[j],speed[j],carWidth);
      if (F.first >= 0) candidates.push_back(F);
      F = process(position[j],speed[j],position[i],speed[i],carWidth);
      if (F.first >= 0) candidates.push_back(F);
    }
    F = process(0,0,position[i],speed[i],carWidth);
    if (F.first >= 0) candidates.push_back(F);
  }
  sort( candidates.begin(), candidates.end(), isLess );

  FOREACH(it,candidates)
    if (check(*it,position,speed,roadWidth,carWidth))
      return carArrival + (1.0 * it->first / it->second);
}

Value	1000
Submission Rate	28 / 378 (7.41%)
Success Rate	13 / 28 (46.43%)
High Score	SkidanovAlex for 706.02 points (20 mins 11 secs)
Average Score	523.45 (for 13 correct submissions)

This problem was actually simpler than it looks at the first sight.

Imagine that we are drawing a spiral according to the given rules. We already have several segments and want to add another one.

The key thing to note is that we don't need to know the actual order in which we connected the points that are already on the spiral. All information we actually need:

• The set of points we already used.
• The last two points used, in order.

Clearly this is enough to check that we don't use the same point twice. Condition 4 implies condition 1 -- if the halfline doesn't intersect or touch anything, then the segment can't intersect anything as well. Thus we can ignore condition 1. To check condition 3 the last two points are enough. And finally, condition 4 can be rephrased as follows:

Condition 4 rephrased: The line segment between the last point used and the new point must lie on the boundary of the convex hull of the spiral.

Or equivalently:

Condition 4 rephrased again: All the points we already used must lie to the left of the line given by the last point used and the point we want to add (or on the line, but the new point and the old point must be on opposite sides of the last point used).

Now it should be clear that to check whether this condition holds it is enough to have the information described above.

Algorithm

We will write a recursive function that tries to extend the spiral, while keeping the information we need: the set of points used, and the indices of the last two points. The function will be memoized to avoid computing the same thing twice. We will use a bitset to represent the set of used points.

There are at most 2^15 * 16^2 = roughly 8 million possible states, thus this approach should run in time. (In reality, most of the states won't even be reachable, the spiral-building rules are pretty restrictive.)

Implementation

We will write a helper function:

// c must be on the left side of ab, OR on the half-line reverse to ba
bool correctTurn(int a, int b, int c) {
  int ux = X[b]-X[a], uy=Y[b]-Y[a];
  int vx = X[c]-X[b], vy=Y[c]-Y[b];
  int crossProduct = ux*vy - vx*uy;
  int dotProduct = ux*vx + uy*vy;
  if (crossProduct != 0) return (crossProduct > 0);
  return dotProduct >= 0;
}

Now, the funny thing is that this function does all we need. We can use it to check whether the new point turns the spiral in the required direction, and also to check whether all other points lie on the left side of the new edge.

int N;
int X[52], Y[52];

int memo[33000][16][16];

int solve(int used, int last, int prev) {
  int &res = memo[used][last][prev];
  if (res >= 0) return res;
  res = 0;
  for (int next=0; next<N; next++) {
    if (used & (1<<next)) continue;
    bool good = true;
    for (int i=0; i<N+1; i++)
      if ( (i==N) || (used & (1<<i)) )
        if (!correctTurn(i,last,next)) good=false;
    if (good) res = max(res, 1+solve(used | (1<<next), next, last));
  }
  return res;
}

class SpiralConstruction {
public:
  int longestSpiral(vector <string> points) {
    N = points.size();
    for (int i=0; i<N; i++) { stringstream SS(points[i]); SS >> X[i] >> Y[i]; }
    X[N]=Y[N]=0;
    memset(memo,-1,sizeof(memo));

    int res=0;
    for (int i=0; i<N; i++) res = max(res, 1+solve(1<<i, i, N) );
    return res;
  }
};