Saturday, November 22, 2008 Match summaryIn this TCHS match 132 participants took part, 100 out of them correctly solved the easy problem, 72 correctly solved the medium one and 42 correctly solved the hard one. First place went to lyrically from Japan, gnocuil (China) and Zuza (Croatia) were second and third respectively. The ProblemsTeamSelectionUsed as: Division One - Level One:
The easiest way to solve this problem was just to brute force over all triples of students, check whether they can work together in a team and to pick the team with the maximal possible summary rating. Such an approach needs O(n^3) operations where n is the number of students. Such a solution easily fits into timelimit because n ≤ 50. Java implementation of this approach can look as follows.
public class TeamSelection { public int selectBestTeam(int[] rating, String[] compatibility) { int n = rating.length; int ans = -1; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { if (compatibility[i].charAt(j) == 'Y' && compatibility[j].charAt(k) == 'Y' && compatibility[k].charAt(i) == 'Y') { int cur = rating[i] + rating[j] + rating[k]; ans = Math.max(ans, cur); } } } } return ans; } }NumberFormatter Used as: Division One - Level Two:
As in most implementation problems to solve this problem one needs only to implement everything from the statement carefully. First of all, you need to split the number into integer and fractional parts. This can be done using string manipulation functions which are included into standard library of programming language. After it one need to format the integer as described in the statement. To do it you need to process characters fror right to left and insert space after each character which number is divisible by three (characters are numbered from right to left with integer numbers starting with one). This step should carefully implemented to not insert the space before the first character of integer part. Some of coders had made such a mistake and they failed system test or were challenged (for example, on test case "123" their programs returned " 123" instead of "123"). Java implementation of this approach can look as follows.
public class NumberFormatter { private String insertSpaces(String s) { String res = ""; int len = s.length(); for (int i = 1; i <= len; i++) { res = ("" + s.charAt(len - i)) + res; if (i % 3 == 0) { res = " " + res; } } return res.trim(); } public String format(String number) { int commaPos = number.indexOf(','); if (commaPos == -1) { return insertSpaces(number); } else { return insertSpaces(number.substring(0, commaPos)) + '.' + number.substring(commaPos + 1); } } }DecreasingNumbers Used as: Division One - Level Three:
First of all let's note that a one-to-one correpondance between decreasing numbers and non-empty subsets of set of digits {0..9} exists. All digits in a decreasing number are different (so they form a subset) and exactly one decreasing number can be formed from each subset (you need arrange elements of it in a decreasing order). So there exists only 2^10 - 1 = 1023 decreasing numbers. They can be easily generated. After it one need to sort them increasingly and return the answer for the problem. Java implementation of this approach can look as follows.
public class DecreasingNumbers { ArrayList<Long> list; void go(int pos, String s) { if (pos == -1) { if (s.length() > 0) { list.add(Long.parseLong(s)); } return; } go(pos - 1, s + pos); go(pos - 1, s); } public long getNth(int n) { list = new ArrayList<Long>(); go(9, ""); Collections.sort(list); if (n >= list.size()) { return -1; } return list.get(n); } } |
|