Match Editorial

SnapDragon started out quickly with the first 250 submission, but then, shockingly, he dropped back into the pack when he was forced to resubmit the easy problem. tmyklebu ended up with the fastest successful time on the Div-I 250 of 4 minutes and 5 seconds. All in all the 250 went pretty quickly. SnapDragon also got the fastest successful submission on the medium problem of 19 minutes and 22 seconds. This put him in within 100 points of the current leader antimatter who submitted in 13 minutes and 3 seconds on the medium. Things really slowed down when the coders got to the hard problem. The problem was simple to state, but had many complex special cases hidden deep inside. As the clock ticked down, it became clear that if anyone got that problem they would win the match. In the end there were only two serious submissions on the problem by SnapDragon and Eryx but both went down in the system tests, as did antimatter's medium. After the dust settled, nicka81 came out the winner with 686.89 points, SnapDragon in second with 568.01, and hauser in third with 562.41.

In Division II krijgertje finished with 874.03 points on the strength of quick submissions on the easy and medium to win in an impressive debut SRM. This shoots krijgertje up to a initial rating of 1820. krijgertje submitted the hard also, but like in Div-I this time, no one was successful on the Div-II hard (which was shared as the Div-I medium). riveria finished in second with 679.07 points and mkschmidt took third with 658.80.

The Problems

Value	250
Submission Rate	138 / 172 (80.23%)
Success Rate	116 / 138 (84.06%)
High Score	SlimJim for 246.19 points (3 mins 32 secs)
Average Score	189.41 (for 116 correct submissions)

You are asked how many itemX by itemY by itemZ unit items can fit in a boxX by boxY by boxZ unit box, will all items in the same orientation. The number of boxes that can fit in one dimension is easily calulated by the convienient floor rounding built into integer division. A long slow way to type this in is shown below for illustrative purposes.

xcount = boxX / itemX ;
ycount = boxY / itemY ;
zcount = boxZ / itemZ ;
totalcount = xcount * ycount & zcount ;

But in the heat of battle, you would do something more like this for the fastest submission.

c=(bx/ix)*(by/iy)*(bz/iz);

Then you just have to do the six different cases, switching around itemX, ItemY and ItemZ (or boxX, boxY and boxZ) and pick the biggest one. This is a quick job with cut and paste (or "^K^K^Y^Y^Y^Y^Y^Y" if your are using a real nerd's editor like me).

int c, m=0;
c=(bx/ix)*(by/iy)*(bz/iz); if(c>m)m=c;
c=(bx/ix)*(by/iz)*(bz/iy); if(c>m)m=c;
c=(bx/iy)*(by/ix)*(bz/iz); if(c>m)m=c;
c=(bx/iy)*(by/iz)*(bz/ix); if(c>m)m=c;
c=(bx/iz)*(by/ix)*(bz/iy); if(c>m)m=c;
c=(bx/iz)*(by/iy)*(bz/ix); if(c>m)m=c;
return m ;

The only thing to be careful about is making sure you got all six cases. You could use nextperm() in C++ but that is really overkill and probably slower to type in.

Value	500
Submission Rate	80 / 172 (46.51%)
Success Rate	29 / 80 (36.25%)
High Score	riveria for 435.03 points (11 mins 19 secs)
Average Score	294.93 (for 29 correct submissions)

BigCube asks you to find the largest perfect cube within a bunch of intervals. The key to this problem is to see that you must generate cubes and test them to see if they are contained in the intervals (there are 100,000 possible cubes) and not go through the intervals testing to see if each member is a cube (that would be 50,000,000,000,000,000 tests). Examples were included which would demonstrate that looping within the intervals would time out. There was an unfortunate typo in the constraints which listed the maximum as "1000000000000000000 (1e15)" Those who counted the zeros found there were 18 not the intended 15, which is quite different. But most people trusted the 1e15 and didn't bother to count the zeros.

Here is all you needed to do except make some variables.

for(i=0;i;>ranges.length;i++)
   { low[i]=Long.parseLong(ranges[i].split("-")[0]);
    high[i]=Long.parseLong(ranges[i].split("-")[1]); }
long n;
for(n=100000;n>=0;n--)
   for(i=0;i;gt;ranges.length;i++)
       if ( n*n*n <= low[i] && n*n*n >= high[i] )
          return n*n*n+"" ;
return "" ;

Value	1000
Submission Rate	4 / 172 (2.33%)
Success Rate	0 / 4 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

Value	500
Submission Rate	84 / 170 (49.41%)
Success Rate	37 / 84 (44.05%)
High Score	SnapDragon for 359.95 points (19 mins 22 secs)
Average Score	245.66 (for 37 correct submissions)

Eigenvector is a big scary math word. But you don't have to do any big scary math in this problem. In fact it turned out that some coders that were familiar with eigenvectors and eigenvalues were at a disadvantage on this problem, because the problem statement disallowed eigenvalues of zero, which is a perfectly good possible eigenvalue. A second difficulty with this problem was one of the example answers was incorrect, which when discovered, showed the reference solution had a bug, and the test solutions of two problem testers also had the same exact bug (what are the chances?), so it had crept by unnoticed. Oh, yeah, L₀ should have been L₁ too. Ouch.

The solution was not nearly as bad as the problem statement. Because the range of the allowable answers is so small, you can just generate all the possible answers and test each one to see if it works. If you generate them in order by L₀₍₁₎ norm and then in lexicographic order, you don't even have to write any comparison code, just return the first one you find.

The basic algorithm looks like this.

For (L0=1;L0<10;L0++)
   {
   vec=first(L0);
   while ( ok(vec)) ;
      {
      if ( proportional(vec,multiply(matrix,vec))
         return vec ;
      vec=next(vec,L0) ;
      }
   }

All you have to write is a parser() for the input into "matrix", multiply(), proportional(), first(), next() and ok() which are all pretty straightforward.

Value	250
Submission Rate	166 / 170 (97.65%)
Success Rate	122 / 166 (73.49%)
High Score	tmyklebu for 244.95 points (4 mins 5 secs)
Average Score	188.64 (for 122 correct submissions)

Find the longest substring of digits in single which has a corresponding substring in multiple that is a digit by digit multiple of single's substring. This problem is very similar to the DNA sequence matching problems we saw recently, so everyone should have been exposed to lots of different algorithms that could be used here. The 50 character limitation on the length of the strings allowed inefficient algorithms of O(n⁴) or so. The thing to do for the most points, is to go with the fastest one to type in and debug.

Oh yeah, there is an O(n) algorithm for this problem, if the base of the number system is considered constant, but that is really really really overkill for a level 1 (easy) problem. But if you had a prewritten maximum substring matching algorithm that runs in linear time you could do this (or any other prewritten matcher).

m=0 ;
for(k=0;k<9;k++)
  {
  for(i=0;i<single.length();i++)
      {
      vec[i]='0'+(single[i]-'0')*k ;
      }
   m=max(m, linearmatcher(vec,multiple));
   }
return m ;

Otherwise, coding from scratch, something like this suffices.

max=0;
for(offset = -single.length() ;
    offset < multiple.length(); offset++ )
   for(k=0;k<10;k++)
   {
   count = 0 ;
   for(i=0;i<single.length();i++)
      if (i+offset >=0&&i+offset<multiple.length())
         if ((single(i)-'0')*k==(multiple[i+offset]-'0'))
         {
         count ++ ;
         if ( count>max) max=count ;
         {       
      else
         count = 0 ;
   }     
return max ;

Here multiple is compared to single character by character, noting the length of the longest consecutive sequence of matches. Then the process is repeated for a different character offset between the two strings. This is O(n²) which isn't bad (if the base of the number system, b, is allowed to vary then there is an additional factor of b in the complexity because there is a loop from 0 to b-1, but it is a constant in this problem.)

The matching code is much simpler if the k loop is outside the i loop. It is possible to do it the other way, but takes more bookkeeping.

Value	1000
Submission Rate	3 / 170 (1.76%)
Success Rate	0 / 3 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

Given a set of points, do they determine a unique square? The problem statement is so simple, you would think this problem would be easy. The problem is trivial for circles. Not so. It is a mess. This is clearly a "think about the problem and reason out all the cases" kind of problem than a just "remember the right algorithm" kind of problem.

If you have five or more points on a square, by the pigeonhole principle, of the four sides at least one side must have at least two points. So you only need loop over all the pairs of points to find one side of all the possible squares. There are at most 1225 pairs with 50 points. And once you find a valid square for a particular slope (or multiple of 90 degrees rotation of that slope) you don't have to check that slope again, as you would be recounting the same square.

So the basic algorithm is to count squares trying all the pairs of points with slopes that don't (so far) have a valid square detected. As soon as we find two squares we know the configuration is ambiguous, or some configurations will immediately signal ambiguity. If we go through all the points and only one square is found, the configuration is consistent. If no squares are found the configuration is inconsistent.

To reduce the number of variables, and simplify the calculations, what I did was to first select the pair of points, then rotate all the points about the origin so that the selected pair is horizontal. Then translate all points so the selected points so that are on the x-axis. Now we are almost in a standard configuration for testing. Then find the bounding box of the points. If the bounding box extends above and below the x-axis, then no square through these two points is possible and this pair is discarded (although a square with an edge containing two other points, parallel to these two might still be possible).

Now we know the bounding box is either up from the x-axis or down from the x-axis. If it is down, I reflect all the points about the x-axis. Now all the points are in a standard configuration where it is easier (for me) to analyse and test all the possible cases.

About rotations: Many people shy away from rotating a coordinate system because they are afraid they will get the transformation matrix wrong. Do not fear. In two dimensions rotating about the origin is very easy and every coder that is good enough to try to solve a Div-I hard problem should have this formula memorized.

xr = xo cos(a) - yo sin(a)
yr = xo sin(a) + yo cos(a)

This rotates the point (x_o,y_o) by an angle of "a" counterclockwise about the origin.

Back to the problem: If any point is not on the edge of the bounding box, (then it is in the interior) consideration of the current pair of points is terminated. But other pairs of points may still yield valid squares.

Next we classify the locations of the points and determine if any of the following cases hold (where "edges" refers to edges of the bounding box). Remember, we are inside a loop over all pairs of points, and we are keeping track of a count of how many squares we have found, and marking the slopes of those found squares as "used". Actually we exit the loop and return "ambiguous" if we find two squares, so we only need ever mark one slope as used. Here are the cases:

Case "-": All points colinear. Return "ambiguous".

Case "L": All points on two adjacent edges. Return "ambiguous".

Case "U": At least one point on bottom edge not a vertex, and a point on each side edge with x > 0. Increment count and mark this slope as used if the bounding box height is less than or equal to the bounding box width.

Case "n": Similar but upside down. Only two points on bottom "edge" each a vertex of the bounding box. At least one point on one vertical edge not a vertex. At least one point on both vertical edges with y > 0. At least one point on the top edge not a vertex. Same test as case "U", Increment count and mark this slope as used if the bounding box height is less than or equal to the bounding box width.

Case "C": Same thing on its side. Reverse height and width in test. At least one point on top edge not a vertex. At least one point on one side not a vertex. No points on the edge on the other side except possibly vertices. Because we start out knowing that there are at least two points on the bottom "edge" the three cases U, n, and C are not quite exactly same to detect, although they are just rotations of the same kind of configuration.

Case "L'": (L prime) At least one point on bottom edge not a vertex. At least on point on one side edge not a vertex. No points on the other side edge which are not vertices. Top vertex of "other" side must be present. This configuration always yields a square, increment the count and mark slope used.

Case "||": No non-vertex points on the top or bottom edges. Return ambiguous if the bounding box height is less than the bounding box width. Increment the count and mark the slope used if they are equal.

Case "_-": The parallel case on its side. No non-vertex points on either side edge. Return ambiguous if the bounding box height is greater than the bounding box width. Increment the count and mark the slope used if they are equal.

Case "O": Non-vertex points on all edges and the default if none of the other cases hold. If bounding box height == bounding box width, increment count and mark slope used.

There, that wasn't so hard was it? Ok, It was pretty hard. But did we learn anything? I learned how to spell "ambiguous".

If I were writing a production code for this problem, I would probably do the rotations, then test each point and set one of eight bits in an int. One for each vertex of the bounding box and one for each side of the bounding box excluding the vertices. Then with a the results of the height/width of the bounding box comparison (three possible values), just use a hardwired lookup table with 768 entries. Not quite a many cases as the four-color map problem, but pretty impressive. Good luck for the guy after me that has to debug it.