Match Editorial

The div 1 easy/div 2 medium proved to have a couple tricky cases that weren't in the examples, which caused many submissions (including the reference solution) to fail. The div 1 medium and div 2 easy were both more reasonable, as quite a few people got the div 1 medium, and almost everyone got the div 2 easy. In division 1, Eryx won handily, beating second place LunaticFringe by almost 250 points. In third place was Zis, doing well in only his 8th competition. In division 2, Mozg beat first timer joose by about 90 points, and sun_agr rounded out the top 3.

The Problems

Value	250
Submission Rate	160 / 167 (95.81%)
Success Rate	157 / 160 (98.12%)
High Score	eleusive for 249.53 points (1 mins 14 secs)
Average Score	234.57 (for 157 correct submissions)

The most straightforward way to solve this problem is with two nested loops. The outer loop iterates over the elements of the input, and the inner loop iterates over the characters in the current element. If the letter is not a '-', then increment the return value.

Value	500
Submission Rate	125 / 167 (74.85%)
Success Rate	26 / 125 (20.80%)
High Score	mariusmuja for 380.08 points (17 mins 7 secs)
Average Score	272.85 (for 26 correct submissions)

Value	250
Submission Rate	159 / 164 (96.95%)
Success Rate	58 / 159 (36.48%)
High Score	cnettel for 240.45 points (5 mins 42 secs)
Average Score	193.70 (for 58 correct submissions)

This problem proved to be way more difficult that expected, as even the writer and testers missed some cases. The most common problems people had were with cases like {"A","-","B"} and {"A","B"}, considering one or the other to have only a single word.

There are a few ways to solve this problem. One way to solve it is to do everything with a couple of nested loops. In this approach, you keep a count of the number of words, and a count of the total number of letters. As you are iterating over all of the characters in the input, you should increment the number of words each time you get to the end of a word (alternatively, you can increment the word count each time you get to the beginning of a word). A word ends whenever you get to a letter (character j of element i) and the next character is not a letter and the special hyphen case does not occur.

  boolean hyphen = 
      j + 2 == lines[i].length() && 
      lines[i].charAt(j+1) == '-' &&
      i + 1 < lines.length && 
      isLetter(lines[i+1].charAt(0));
  boolean nextLetter = 
      j + 1 < lines[i].length() && 
      isLetter(lines[i].charAt(j+1));
  if(!nextLetter && !hyphen){
      words ++;
  }

   String all = "";
   for(int i = 0; i<lines.length; i++){
      all = all+lines[i]+"\n";
   }
   int chars = all.replaceAll("[^a-zA-Z]","").length();
   int words = ("A "+all).replaceAll("[a-zA-Z]\\-\n","A").
      split("[^a-zA-Z]+").length-1;
   return 1.0*chars/words;

Value	1000
Submission Rate	51 / 167 (30.54%)
Success Rate	8 / 51 (15.69%)
High Score	sun_agr for 725.27 points (19 mins 4 secs)
Average Score	514.42 (for 8 correct submissions)

There are a couple ways to do this. The brute force way to do it is to move one square at a time, and put all of the locations reached in some sort of a set as you go. If you ever get to a point already in the set, then return the index of the segment that first reached that point. However, this approach is a bit risky because it requires putting a lot of points in a set, which can be relatively slow, and you might time out.

A better solution is to look at all pairs of segments and check if they intersect. If the two segments are defined by (x1,y1)-(x2,y2) and (x3,y3)-(x4,y4), where x1 < x2, and x3 < x4, and similarly for y. A simple way to tell if two segments intersect is the following:
intersect = x1 < x3 && x2 < x4 && y1 < y3 && y2 < y4
The only special case to watch for is that two segments are allowed to touch at a single point if they are consecutive. The only case in which a pair of consecutive segments count is when they are going in opposite directions. We can do this all with something like this:

for(int i = 0; i+1<segs.length; i++){
    if(direction[i] is reverse of directions[i+1]){
        return i;
    }
    for(int j = i+2; j<segs.length; j++){
        if(segs[i].touches(segs[j])){
            return i;
        }
    }
}
return -1;

Value	500
Submission Rate	138 / 164 (84.15%)
Success Rate	106 / 138 (76.81%)
High Score	antimatter for 455.30 points (9 mins 4 secs)
Average Score	290.82 (for 106 correct submissions)

The first step in this problem is to figure out how many spaces to put between columns. If you wanted to, you could iterate over all spacings, until you found one that worked. However, it isn't too hard to figure it out from the title input. Between titles i and i+1 there need to be
title[i].length()/2+(title[i+1].length()-1)/2 + 1
characters - the extra 1 is for the space, and we use integer division to deal with the fact that we can't center the columns when the number of characters in a title is even. The number of characters between columns is the maximum of the number of characters required between two adjacent titles.

Once we know how many characters go between each pair of columns, we can start placing the 'X's in each column. Since the first title goes at the beginning of the last String of the return, the first column of 'X's is in column (title[0].length()+1)/2. Starting from there, we can easily figure out the rest of the columns with 'X's in them, based on the number of columns between 'X's (which we calculated earlier).

Finally, the hard part is placing the titles. We already know where the centers of the titles go though, so we can figure out where the first character of each title should go based on that. If the center of a title, t, is at character i, then the first character of t should go at i - ((t.length()-1)/2). Once you have all of the 'X's and titles placed, make sure you trim the trailing spaces, and you're set.

public String[] draw(String[] title, int[] value){
   int l = 0,h = 0,first = (title[0].length()-1)/2;
   for(int i = 0; i<value.length; i++)
      h = Math.max(value[i]+1,h);
   char[][] ch = new char[h][1000];
   String[] ret = new String[h];

   for(int i = 0; i<ch.length; i++)
      for(int j = 0; j<1000; j++)
         ch[i][j] = ' ';

   for(int i = 0;i+1<title.length;i++)
      l = Math.max(l,title[i].length()/2+(title[i+1].length()-1)/2+1);

   for(int i = 0; i<value.length; i++){
      for(int j = 0; j<value[i]; j++){
         ch[h-j-2][first+(l+1)*i] = 'X';
      }
      int idx = (first+(l+1)*i) - ((title[i].length()-1)/2);
      for(int j = 0; j<title[i].length(); j++){
         ch[h-1][idx+j] = title[i].charAt(j);
      }
   }

   for(int i = 0; i<ret.length; i++)
      ret[i] = ("A"+new String(ch[i])).trim().substring(1);
   return ret;
}

Value	1000
Submission Rate	25 / 164 (15.24%)
Success Rate	6 / 25 (24.00%)
High Score	Eryx for 840.24 points (12 mins 54 secs)
Average Score	640.36 (for 6 correct submissions)

A bit of background in number theory was important for this one. The key to solving this was to know (or figure out) that given two integer, a and b, any multiple of gcd(a,b) can be realized by adding and subtracting some multiples of a and b. From this, it follows that given integers n₁,...,n_k any multiple of gcd(n₁,...,n_k) can be realized. So, we'll start be setting a target sum of this gcd.

Due to the tiebreaker rules, we start with the first element of the input, call this a. We then calculate the gcd of the remaining elements, call this b. We want to find the smallest integer x such that x*a+y*b == target or -x*a+y*b == target. This amounts to finding x such that (target-x*a)%b == 0 or (target+x*a)%b == 0. There is a fast way to do this, but simply starting at 0 and counting up until we find an x that works is fast enough. Once we find this x, we set the first element of the return value to x or -x. Now, we adjust the target to target + x*a or target - x*a and move on to the second element. In the next iteration, we set a to the second element of the input, and b to the gcd of the third through last elements. We continue in this way until we get to the last element of the input. When we get to the last element, we are guaranteed that target%a will be 0, so we can just set the last element of the return to target/a, and return the result.