codeladder

Про 250 задачу уже нечего сказать, она решилась просто, хотя я спросонья притормозила и тут.

550 задача - вычислить маршрут из одной точки в другую на поверхности, испещренной кругами, так чтобы пересечь минимальное количество границ с кругами.


Алгоритм очень прост - если точка отправления находится внутри круга, а точка прибытия не находится в том же круге, или наоборот - то границу круга придется пересечь.

Первоначальный код:

public class CirclesCountry {

    public int leastBorders(int[] X, int[] Y, int[] R, int x1, int y1, int x2, int y2) {
        int road = 0;
        for (int i = 0; i < X.length; i++) {
            if (inCircle(x1,y1,X[i],Y[i],R[i])) {
                road++;
            }else if (inCircle(x2,y2,X[i],Y[i],R[i])) {
                road++;
            }
        }

        return road;
    }

    public boolean inCircle(int x, int y, int cx, int cy, int r) {
        double rad = Math.pow(x - cx, 2) + Math.pow(y - cy, 2);
        if (rad  <= r * r) return true;
        return false;
    }

}

Засабмитив, нашла в коде ошибку. Если точка отправления и точка назначения находятся в одном круге - количество пересекаемых границ не увеличивается.


Переписала часть:

for (int i = 0; i < X.length; i++) {
   if (inCircle(x1,y1,X[i],Y[i],R[i]) && !inCircle(x2,y2,X[i],Y[i],R[i])) {
      road++;
   }else if (inCircle(x2,y2,X[i],Y[i],R[i]) && !inCircle(x1,y1,X[i],Y[i],R[i])) {
      road++;
   }
}

или, не зря же в языке есть логические операторы

if (inCircle(x1,y1,X[i],Y[i],R[i]) ^ inCircle(x2,y2,X[i],Y[i],R[i])) {
   road++;
}

Сделала тест для челендж фазы, проверила что все тесты включая мой для маршрута внутри концентрических кругов проходят, посмотрела третью задачу, поняла что сконцентрироваться уже не могу, и расслабилась на 20 минут до конца кодинг фазы.
Во время челендж фазы обнаружила что тот код, который я понимаю, пройдет мой тест, а тот который я не понимаю, челенджить не стала.

А вот мой код как-то зачеленджили.
С нетерпением дождалась когда откроются practice rooms, чтоб прогнать код на системных тестах. Тесты все прошли. Как мой код смогли зачеленджить - непонятно. Даже попробовала зачеленджить свой код на граничном условии - когда одна из конечных точек находится на границе круга - нет, такой тест не проходит, все как в условии задачи.

В результате вернулась в комнату контеста, и таки выяснила как удался челендж. За оставшиеся 20 с лишним минут после исправления и тестирования кода я его не засабмитила.

Epic fail.

Осталось немного потренироваться чтоб справляться с двумя задачами. На сей раз уже традиционно просто справилась с первой задачей. Причем, только я нажала кнопку Submit, как скакнуло напряжение (у нас тут была гроза) и машина пошла перезагружаться. Тем не менее я успела решить и засабмитить вторую задачу, потенциально на 460 баллов. Но к сожалению мой код для вычисления простых чисел оказался сильно неэффективным по времени и на больших числах превышал лимит в 2 секунды, так что кому-то сильно повезло в челендж фазе.

Задача: Представление натурального числа в виде произведения простых называется факторизацией числа. Например для 12 это 2*2*3 (1 не является простым числом). Underprime (не нашла перевода) это натуральное число, факторизация которого содержит также простое число множителей. Например то же число 12 - сожержит 3 множителя, а 3 - простое чсило. Для заданных А и В вернуть количество чисел системы "underprime" (знать бы как это по-русски) между ними (включительно).
link

Вот мой первоначальный код. Выдает правильные результаты, но на интервале от 2 до 100000 (по условиям задачи) задумывается на 85 секунд.

public class Underprimes {
    public int howMany(int A, int B) {
        int number = 0;

        HashSet primes = getPrimes(B);
        ArrayList fact = new ArrayList();

        for (int a = A; a <= B; a++) {
            int b = a;
            divide:
            while (b > 1) {
                for (Integer i : primes) {
                    if (b % i == 0) {
                        b = b / i;
                        fact.add(i);
                        continue divide;
                    }
                }
                break;
            }
            if (primes.contains(fact.size())) {
                number++;
            }
            fact.clear();
        }
        return number;
    }


    public HashSet getPrimes(int B) {
        HashSet primes = new HashSet();
        int fac = 0;
        for (int i = 2; i <= B; i++) {
            for (int j = 2; j <= i / 2; j++) {
                if (i % j == 0)
                    fac++;
            }
            if (fac <= 0) {
                primes.add(i);
            }
            fac = 0;
        }
        return primes;
    }
}

Уже после прекращения фазы кодирования нашла ошибку в методе нахождения простых чисел. Ошибка по невнимательности, про диапазон перебора делителей до квадратного корня я знала. Исправление уменьшило время выполнения до 13 секунд.

    public HashSet getPrimes(int B) {
        HashSet primes = new HashSet();
        boolean isPrime = true;
        for (int i = 2; i <= B; i++) {

/* Было for (int j = 2; j <= i / 2; j++)  - пустая (и огромная) потеря времени */
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primes.add(i);
            }
        }
        return primes;
    }

Последовав мудрым советам renatm и убрав некоторые другие свои ляпы получила для интервала 2-100000 время 150мс. Системные тесты пройдены, жаль что не во время SRM 8)

    public int howMany(int A, int B) {
        
        int number = 0;

        Integer[] primes = getPrimes(B).toArray(new Integer[]{});
/* Был опробован LinkedList в виде возвращаемого отсортированного списка простых чисел, 
но в итоге код выполнялся 6 секунд.
 С использованием массива - 150 мс */ 

        Arrays.sort(primes);
        int fact = 0;
/* Еще один мой баг на Топкодере: делать не то, что написано в задании.
 Нигде не было написано *составьте список простых множителей*, 
было написано сосчитать их. Так что и тут список заменен на число. */

        for (int a = A; a <= B; a++) {
            int b = a;
            for (int i = 0;  primes.length>i && primes[i] * primes[i] <= b; i++) {
                while (b % primes[i] == 0) {
                    fact ++;
                    b = b / primes[i];
                }
            }
            if (b > 1) {
                fact ++;
            }

            if (Arrays.binarySearch(primes,fact)>=0) {
                number++;
            }
            fact = 0;
        }
        return number;
    }


    public HashSet getPrimes(int B) {
        HashSet primes = new HashSet();
        primes.add(2);
        if (B%2 ==0) B /= 2; 
        for (int i = 2; i <= B; i++) {
            boolean isPrime = true;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primes.add(i);
            }
        }
        return primes;
    }

Пропустила 3 матча подряд - ездила на родину за загранпаспортом, меняла работу, было не до топкодера.

SRM441 застал меня на работе, но к концу рабочего дня. Так что местами меня отвлекали и сконцентрироваться не удавалось. В итоге стабильно решаемая первая задача о 250 баллах и буквально пары секунд не хватило чтоб засабмитить вторую задачу.

Первое задание решила минут за 5. Впрочем все в комнате кто его открыл, решил его в промежутке 0-10 минут 8). Буквально все время ушло на то чтобы набить текст и прогнать имеющиеся тесты (несмотря на легкость задания на этот раз я не решилась пропустить ни один тест, прогнала все что были). Осталось больше часа на остальные. И тут приехали - я не смогла решить второе задание за этот час, минут за 15 до конца открыла посмотреть третье, там тоже было нечего ловить.
Сижу теперь, разбираюсь со вторым заданием.
Ну хоть рейтинг немного подрос.

По 500 заданию
Написала программу-франкенштейн, которая таки проходит систем тесты.
Франкенштейн - потому что после того как написала, прогнала начальные тесты и вроде как убедилась что "работает", пришлось тут и там латать ее на предмет заваленных системных тестов. То есть в любом случае был бы провал.

сейчас выложу себе "на добрую память" этот франкенштейн, а завтра подумаю снова, как можно сделать красиво, опять же, на форуме может что появится...

import java.util.*;

public class TheSwap {
    public int findMax(int n, int k) {
        if (n < 11) return -1;

        LinkedList maxPossible = new LinkedList();
        LinkedList digits = new LinkedList();

        int equaldigit = -1;

        while (n > 0) {
            int low = n % 10;
            maxPossible.addFirst(low);
            if (digits.contains(low)) equaldigit = low;
            digits.addFirst(low);
            n = n / 10;
        }

        Collections.sort(maxPossible);
        Collections.reverse(maxPossible);

        String max = maxPossible.toString();

        while (k > 0) {

            String number = digits.toString();
            if (number.equals(max)) {
                // тут еще красиво и нет трупного запаха
                if (equaldigit == -1) {
                    if (digits.size() == 2 && digits.getLast() == 0) return -1;
                    int swap = digits.getLast();
                    digits.set(digits.size() - 1, digits.get(digits.size() - 2));
                    digits.set(digits.size() - 2, swap);
                }
            } else {
                // Осторожно! Франкенштейн! Он хочет мой мозг! Пусть поищет, ага...
                int iToSwap = 0;
                while (digits.get(iToSwap).equals(maxPossible.get(iToSwap))) {
                    iToSwap++;
                }
                int q = 0;
                for (int j = 0; j < Math.min(maxPossible.size() - iToSwap - 1, k); j++) {
                    if (maxPossible.get(iToSwap + j).equals(maxPossible.get(iToSwap))
                            && !maxPossible.get(iToSwap + j).equals(digits.get(iToSwap + j))) {
                        q++;
                    }
                }

                int jToSwap = digits.lastIndexOf(maxPossible.get(iToSwap));
                int betterIToswap = iToSwap;
                int min = digits.get(betterIToswap);
                if (q > 1) {
                    for (int i = iToSwap; i < Math.min(iToSwap + k, digits.size()); i++) {
                        if (digits.get(i) < min) {
                            min = digits.get(i);
                            betterIToswap = i;
                        }
                    }
                }

                int num = digits.get(betterIToswap);
                digits.set(betterIToswap, maxPossible.get(iToSwap));
                digits.set(jToSwap, num);
            }

            k--;
        }

        String s = "";
        for (Integer i : digits) s += String.valueOf(i);

        return Integer.valueOf(s);
    }

    public static void main(String[] args) {
        TheSwap swap = new TheSwap();
        int res;

        // А это я так тестирую

        res = swap.findMax(512909, 2);
        assert res == 992501 : res;

        res = swap.findMax(3615, 7);
        assert res == 6531 : res;

        res = swap.findMax(65, 7);
        assert res == 56 : res;

        res = swap.findMax(392289, 3);
        assert res == 998322 : res;

        res = swap.findMax(35766, 3);
        assert res == 76653 : res;

        res = swap.findMax(100757, 1);
        assert res == 700751 : res;

        res = swap.findMax(5, 2);
        assert res == -1 : res;

        res = swap.findMax(90, 4);
        assert res == -1 : res;

        res = swap.findMax(432, 1);
        assert res == 423 : res;


        res = swap.findMax(16375, 1);
        assert res == 76315 : res;

    }
}

Так неудачно получилось - пришлось пропустить мартовский контест, две недели ушло на разъезды и на грипп. Грипп оказался неприятным - заболела еще в поезде, и несколько дней могла только спать с перерывом на почитать минут 15, так что и речи об шевелении мозгами не было.
Тем временем прошел SRM436.
Мне он достался уже в виде practice room.
Первая задача довольно простая - простой перебор. Где-то полчаса поскрипывания извилин все равно заняла у меня.
Вторая задача для кого-то тоже свелась к перебору, но не для меня, увы.
Задача такая - есть линия небоскребов разной длины, надо выбрать из них такой, с которого видно максимальное количество небоскребов, и вернуть это максимальное значение видимых зданий.
Вот и картинка.

Задача сводится к перебору зданий и проверке заслоняет ли какое-то здание вид с текущего здания на другое здание в ряду.
Я застряла (о горе мне!) на выведении формулы прямой от одного здания к другому. Зная формулу прямой, проведенной от вершины одного здания до вершины другого, мы можем точно сказать, пересекает ли какое нибудь другое здание эту прямую (оно должно быть выше или равно значению формулы прямой в точке где оно находится).
Формула прямой. Уравнение прямой. Это же проходят в средней школе, и кажется даже не в старших классах. Вот так застряла, со своим высшим образованием и шестилетним опытом программирования на Java.
Вывела я эту формулу, по клеточкам выводила, нет, я не блондинка. Предположим что в данный момент мы находимся на здании i и пытаемся с него рассмотреть здание j. Прямая, соединяющая вершины i и j описывается уравнением:
Высота[i] - (Высота[i] - Высота[j]) * (k - i) / (j - i)
где k - любая точка между i и j.
То есть все, что нам нужно знать - это высота небоскреба в точке k и значение уравнения нашей прямой в той же точке, если небоскреб задевает нашу прямую - значит он портит нам весь вид.
Собственно, это все, если бы я сумела вывести формулу прямой (!) за вменяемое время, я была бы молодец.
Но как минимум поскрипела мозгом, вывела сама нужную формулу, решила задачу.
Завтра SRM437, удачи мне.

public int numberOfBuildings(int[] heights) {
        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            int visible = 0;
            for (int j = 0; j < heights.length; j++) {
                if (i == j) continue;
                if (Math.abs(i - j) == 1) {
                    visible++;
                    continue;
                }
                boolean hasview = true;
                for (int k = Math.min(i, j) + 1; k < Math.max(i, j); k++) {
                    double formula = heights[i] - (heights[i] - heights[j]) * (double) (k - i) / (j - i);
                    if (heights[k] >= formula) {
                        hasview = false;
                        break;
                    }
                }
                if (hasview) visible++;
            }
            max = Math.max(max, visible);
        }

        return max;
    }

Вчистую продула квалификационный раунд. Обычно мой результат - 1 задача из трех за отведенный час соревнований. Это мало, я планирую немного разработать мозговые мышцы и журнал в первую очередь завела для анализа результатов. В этот раз первая задача оказалась мне не по зубам и через полчаса бесплодных потуг я решила перейти ко второй

Задание - сосчитать для каждой цифры (от 0 до 9) сколько раз она встретится на номерах страниц от 1 до N. После задачи с шахматной доской, от которой надо отрезать куски и перекрашивать клетки, эта показалась мне совсем элементарной. Поэтому я быстро накидала код:

public static int[] getCountsBad(int n) {
  int result[] = new int[10];
  String s = "";
  for (int i=1;i<=n;i++){
    s += i;
  }
  for (Character c:s.toCharArray()){
    result[c-'0'] ++;
  }
  return result;
}

Так как код элементарный, прогнала первые четыре теста, буквально чтобы исключить ошибки из-за невнимательности, и решив не заморачиваться с кучей тестов быстро засабмитила решение на 450 баллов. В первые же 5 секунд челлендж фазы осознала как была неправа. Ведь я, прогнав 4 первых теста (для чисел от 7 до аж 999), даже не удосужилась провернуть скроллер дальше, а там...

4)    
543212345
Returns:
{429904664, 541008121, 540917467, 540117067, 533117017, 473117011, 429904664,
 429904664, 429904664, 429904664 }
Watch out for the time limit.

У нас принято сравнивать плохой код с *работой индусских программистов*. Но, пользуясь анонимностью журнала,
хочу заметить, что на Топкодере много индусов, и многие имеют высокий рейтинг, повыше моего. Так что предрассудки это все,
а моя задача - перестать быстро ваять тупой код, а начать эффективно думать.

Ладно, Большие Гонки позади и бездарно проиграны еще до начала, можно сесть и подумать над тем как правильно сосчитать цифры в страницах, не прибегая к потрясающе неэффективным алгоритмам бесконечного перебора цифр на пальцах. Опять же раз журнал анонимный и мой работодатель меня не вычислит, признаюсь - чтобы разродиться решением у меня ушел весь следующий день.

Итак, возьмем число из того самого провального теста: 543212345

Посмотрим сколько раз там встретится цифра 4.
Справа налево. В десятичном числе каждая цифра представляет собой x*10^i где i - разряд числа, в нашем случае справа налево от 0 до 8.

Ищем сколько раз 4 на первой справа позиции (i = 0)

разбиваем число на диапазоны 543212340 и 5
именно 543212340 раз нам встретится 4 на последней позиции в различных сочетаниях
от 4 до 543212334 и 1 раз число 4 встретится в диапазоне от 1 до 5.

4 на второй справа позиции (i = 1)
543212300 и 45
соответственно 543212300 мы встретим 4 на второй позиции (от 40 до 543212249) и 6 раз от 40 до 45

третья позиция (i = 2):
543212000 345
543212000 раз от 400 до 543211499 и ни разу дальше

четвертая позиция (i = 3):
543210000 раз и снова ни разу в диапазоне 2340

Принцип понятен. Даже мне 8)

Остается разобраться с нулями.

По нашему алгоритму мы сосчитали также и нули, так как реально мы взяли в расчет диапазон 000000000 - 543212345, вместе с нулями, тогда как номера страниц так не нумеруются, так что лишние нули придется оставить. Легко заметить что лишних нулей у нас будет ровно 10^i. Например из диапазона 0-9 мы вынуждены выкинуть 1 ноль с позиции i=0, с позиции i=1 (от 00 до 10) уже 10 нулей, а с позиции (i=2) 100 нулей (от 000 до 100), и так далее.

Итак весь алгоритм:
Проходим по числу справа налево, для каждой цифры подсчитываем количество вхождений на текущей позиции, вычитаем из счетчика нулей лишние нули, переходим к следующей позиции.
Легко и просто. Практика, практика, еще раз практика. Закрывает ЖЖ и переходит к закладке http://www.topcoder.com/tc

public class PageNumbers {

    public static int[] getCounts(int n) {
        int[] result = new int[10];
        int orig = n;
        int pow = 0;
        while (n > 0) {
            int high = n / 10;
            int low = n % 10;

            for (int i = 0; i < 10; i++) {
                int positioncount = 0;
                if (i < low) {
                    positioncount += Math.pow(10, pow);
                }
                if (i == low) {
                    positioncount += orig - n * Math.pow(10, pow) + 1;
                }
                positioncount += high * Math.pow(10, pow);
                if (i == 0) positioncount -= Math.pow(10, pow);
                result[i] += positioncount;
            }
            pow++;
            n = high;
        }

        return result;
    }
}