Tuesday, June 17, 2003 Match summary The two matches prior to SRM 151 saw very few submissions on both the division one medium and hard problems, but this time the coders in both divisions submitted merrily. In division one, newcomers aneubeck (2nd place) and tomek (4th place) pushed hard, but it was for the "oldster" radeye to take the top spot. It is notable that bilingual tomek submitted in both C++ and Java, an event rarely seen with the top finishers. noah won division two finishing only 9 points ahead of JWizard. First timer m00tz finished third and was the only first timer to hit the yellow rating category. The ProblemsPrefixCodeUsed as: DivisionII  Level 1:
Surprisingly many submissions on this problem failed, mainly because not the lowest index of a prefix was returned, but any index of a word
that had a prefix.
Java public String isOne(String[] words) { for (int i=0; i<words.length; i++) for (int j=0; j<words.length; j++) if (i != j && words[j].startsWith(words[i])) return "No, " + i; return "Yes"; } Birthday Used as: DivisionII  Level 2:
There are several possibilities for solving this one.
One of the possibilities is the following:
Extract the day and the month from the current date and from all birthdays.
In a loop, first check if the current day coincides with any of the
birthdays. If so, return that day. If not, set the current date to
the following day (paying attention to the start of a new month/year). C++ string getNext(string date, vector<string> birthdays) { sort(birthdays.begin(), birthdays.end()); for (int i=0; i<(int)birthdays.size(); i++) if (birthdays[i].substr(0, 5) >= date) return birthdays[i].substr(0, 5); return birthdays[0].substr(0, 5); } MergeSort Used as: DivisionII  Level 3: Used as: DivisionI  Level 2:
Implement the MergeSort algorithm as described, run it on the input, and count the number of comparisons made.
C++ int howManyComparisons(vector<int> a) { return mergeSort(a); } int mergeSort(vector<int>& a) { if (a.size() <= 1) return 0; int k = a.size() / 2; vector<int> b = vector<int>(a.begin(), a.begin()+k); vector<int> c = vector<int>(a.begin()+k, a.end()); int cb = mergeSort(b); int cc = mergeSort(c); return cb + cc + merge(a, b, c); } int merge(vector<int>& a, vector<int>& b, vector<int>& c) { unsigned ai = 0, bi = 0, ci = 0, comps = 0; while (bi != b.size() && ci != c.size() && ++comps) if (b[bi] == c[ci]) { a[ai++] = b[bi++]; a[ai++] = c[ci++]; } else if (b[bi] < c[ci]) a[ai++] = b[bi++]; else a[ai++] = c[ci++]; while (bi != b.size()) a[ai++] = b[bi++]; while (ci != c.size()) a[ai++] = c[ci++]; return comps; }Archimedes Used as: DivisionI  Level 1:
The solution to this problem may be the shortest a TopCoder problem has ever seen.
However, there is some basic geometry to be done before the return statement can be written.
Java public double approximatePi(int numSides) { return numSides * Math.sin(Math.PI / numSides); } Gauss Used as: DivisionI  Level 3:
What came to my mind first is the following
(it is too slow on the given constraints, but the technique
may be useful for other problems):
Start with lower = 1, upper = 1 and sum = 1 (sum is
supposed to be the sum of all numbers from lower to upper). Do a loop
while upper <= target/2 + 1:
If sum equals target, add [lower, upper] to the solution.
If sum <= target expand the interval (upper++ and sum += upper),
and if sum > target shorten the interval (sum = lower and lower++).
This way all intervals can be found but the running time is
linear in target, which is too much since target can be as high as
100.000.000.000. n = 30 m = 5 4 5 6 7 8 n / m = 6 n % m = 0 n = 30 m = 4 6 7 8 9 n / m = 7.5 n % m = m/2If m is odd and n/m is integral, n/m is the number in the middle of the numbers that add up to target. If n/m is not integral, there is no solution for m. (Informally, n/m is the 'average weight' of the numbers that need to be added; take n/m and (m1)/2 numbers to the left and to the right of n/m, respectively.) If m is even, n/m must be x.5 for a solution to exist (for some integer x). The solution is the next m/2 integral numbers less than and greater than n/m, respectively. (Again informally, n/m is the 'average weight' of the numbers that need to be added, and if n/m = x.5 each 'pair' of numbers from the left and the right of n/m has this average weight.) The complexity is O(sqrt(target)).
Java public String[] whichSums(String target) { java.util.Vector v = new java.util.Vector(); long t = Long.parseLong(target); int n = (int)(Math.sqrt(0.25+2*t)  0.5); for (int i=n; i>=2; i) { if (i % 2 == 1 && t % i == 0) v.add("[" + (t/ii/2) + ", " + (t/i+i/2) + "]"); if (i % 2 == 0 && t % i == i/2) v.add("[" + (t/ii/2+1) + ", " + (t/i+i/2) + "]"); } return (String[])v.toArray(new String[0]); } The number of ways to represent n as the sum of consecutive positive numbers is equal to the number of odd divisors of n. Try to prove it yourself or take a look at the proof at the end of this old newsgroup post and read more at the OnLine Encyclopedia of Integer Sequences. 
