Qualification Problem Set 2 February 2324, 2004 Summary Qualification Round 2 turned out to be the hardest of the set, and unfortunately only 58 coders ended up with scores greater than 0. 2^{nd} and 3^{rd} seeds reid and John Dethridge both ended up in this room, and reid ended up taking the win by a large margin. John Dethridge also advanced, but only got 4^{th}, as a first time coder, hsaniva, and a yellow, zbogi, took 2^{nd} and 3^{rd}, respectively.
The ProblemsASeriesUsed as: Division One  Level One:
An arithmetic series is a sequence of numbers where a_{i+1}a_{i}=C, for some constant C and for all i. Hence, once we know the first two terms of the series, we can tell what all the rest of the terms will be, if they exist. This observation suggests an approach for finding a solution: take all pairs of numbers in the input, and set one of them to be the first term, and the other to be the second. Then, see how far we can go from there, given the first two terms. The tricky part of all this is that if the first two terms are equal, then we need to be careful to mark the used terms as having been used, or else treat this as a special case. Alternatively, rather than worrying about marking some terms used, we can start be sorting all the terms. Then, if we pick terms i and j as our first two terms, respectively, with i < j, we know that all terms in the series must be greater than or equal to the j^{th} term. Hence, we can iterate starting from j+1 and we will be sure to only count each value once. Note that we can assume, without loss of generality that the first term is less than or equal to the second term since every series is symmetrical: public int longest(int[] values){ Arrays.sort(values); int ret = 0; for(int i = 0; i<values.length; i++){ for(int j = i+1; j<values.length; j++){ int cnt = 2; int next = 2 * values[j]  values[i]; for(int k = j+1; k<values.length; k++){ if(values[k] == next){ next += values[j]  values[i]; cnt++; } } ret = Math.max(ret,cnt); } } return ret; }Coming up with the algorithm proved difficult for a lot of people, as evidenced by the low submission rate, and there were a few special cases, like when there are only 2 elements in the input to deal with. I also saw a few submissions where people incorrectly assumed that the first two terms of the series must be adjacent in the sorted input. NoZero Used as: Division One  Level Two:
There are a few ways to do this one. I'll describe two of them, and you can read about a third here in the round tables. The first way is to convert each of the nozero numbers into a regular number, subtract them, and then convert the answer back. To do the conversion from nozero to decimal, observe that every time we increment a nozero number the right most digit increments, and if it gets to 10, it goes back to 1. The next digit from the right would normally go up by one every 10 times we increment a number, but in this case it only goes up by 1 every 9 times. The third digit from the right goes up once every 9 times we increment the second digit from the right, and hence once every 81 times we increment the rightmost digit. Therefore, if we are given the nozero number abcde, it has decimal value a*9^{4} + b*9^{3} + c*9^{2} + d*9^{1} + e*9^{0}. I'll leave the conversion in the other direction to the reader to figure out from the code below: int convert(int n){ int ret = 0; int d = 1; while(n>0){ ret += n%10*d; d*=9; n/=10; } return ret; } public int subtract(int big, int small){ int b = convert(big)  convert(small); int ret = 0; int d = 1; while(b>0){ ret += b%9*d; if(b%9==0){ret += 9*d;b=9;} d*=10; b/=9; } return ret; }The other solution is based on the method of borrowing that we use to do subtraction by hand and is courtesy of schveiguy. Basically, you just subtract one digit at a time, starting at the right. If you need to borrow, you do so from the digit to the left, and if it is a 1, you borrow from the digit to its left, and so on. The one difference is that instead of borrowing 10, as we normally would, we borrow 9. This is really quite similar to the solution outlined above, working from the same general principal. void borrow(char[] arr1, int pos1) { if(pos1 == 0  arr1[pos1  1] == '0') { // cannot borrow return; } if(arr1[pos1  1] == '1') borrow(arr1, pos1  1); arr1[pos1  1]; arr1[pos1] += 9; } public int subtract(int big, int small) { char[] arr1 = Integer.toString(big).toCharArray(); char[] arr2 = Integer.toString(small).toCharArray(); for(int i = 0; i < arr2.length; i++) { int pos1 = arr1.length  1  i; int pos2 = arr2.length  1  i; int f = Integer.parseInt(new String(arr1, 0, pos1 + 1)); int s = Integer.parseInt(new String(arr2, 0, pos2 + 1)); if(f < s) throw new RuntimeException("BAD"); else if(f != s && arr1[pos1] <= arr2[pos2]) borrow(arr1, pos1); arr1[pos1] = arr2[pos2]  '0'; System.out.println(new String(arr1)); } return Integer.parseInt(new String(arr1)); } 
