Match Editorial

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 Problems

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 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;
    }

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*9⁴ + b*9³ + c*9² + d*9¹ + e*9⁰. 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;
    }

    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));
    }