JOIN
 Match Editorial
2004 TopCoder Collegiate Challenge
Qualification Problem Set 2

February 23-24, 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. 2nd and 3rd 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 4th, as a first time coder, hsaniva, and a yellow, zbogi, took 2nd and 3rd, respectively.

The Problems

ASeries
Used as: Division One - Level One:
 Value 300 Submission Rate 100 / 134 (74.63%) Success Rate 55 / 100 (55.00%) High Score LunaticFringe for 287.54 points (4 mins 46 secs) Average Score 226.93 (for 55 correct submissions)

An arithmetic series is a sequence of numbers where ai+1-ai=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 jth 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:
 Value 650 Submission Rate 63 / 134 (47.01%) Success Rate 16 / 63 (25.40%) High Score reid for 606.15 points (6 mins 12 secs) Average Score 359.45 (for 16 correct submissions)

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 no-zero numbers into a regular number, subtract them, and then convert the answer back. To do the conversion from no-zero to decimal, observe that every time we increment a no-zero 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 no-zero number abcde, it has decimal value a*94 + b*93 + c*92 + d*91 + e*90. 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)