?

Log in

No account? Create an account

elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
[topcoder SRM 246] Ignorance is bliss
elizarov
Сегодня учавствовал в topcoder SRM 246. Вот ведь верно говорят, что "ignorace is bliss". На самой сложной 1000 очковой задачке я написал правильное решение совершенно случайно! Дело в том, что в пылу соревнования мне как-то не пришло в голову, что искать ближайшее число X к корню из N это совсем не тоже самое что искать ближайшее число X2 к N. Ведь A2-B2 = (A-B)*(A+B), где A+B меняется, то есть минимазиция абсолютной разницы квадратов в общем случае (sic!) не тоже самое, что минимизация разницы оригинальных чисел. Как хорошо что это не пришло мне в голову во время соревнования, так как в противном случае я бы точно провозился с её решением намного дольше (в классе BigDecimal нет готового метода sqrt).

Теперь мне мне не дает спать проблема: почему же мое "неправильное" решение все-таки выдает правильные ответы на этой конкретной задаче?

  • 1
А чего дальше было, после контеста? Тебе дали очков и велели "песать исчо"? ;)

Ну да :) Для меня это в основном for fun и чтобы могзи размять. Хотя выброс адреналина такой, что действительно не мог заснуть до 3-х утра. Ух... забытые ощущения :)

А они сейчас пускают из России?

Сейчас пускают всех. Более того, они сделали рейтинг по странам и Россия сейчас занимет 4-ое место. Есть еще над чем работать!

Какой, позор, 4-е место:) Думаю поправим:)

I tested on all possible testcases (within problem constraints), and (wrong?) solution, looking for A/B such that A^2/B^2 is closest to N, passes them all.

Why should it be the case, I still can't understand.

Как ты написал "правильное" решение чтобы оно работало быстро? Его нельзя просто писать на Java или C# в типе double, так как его точности не хватает. Например, двойной точности не хватает чтобы на тесте 736848, 1000 понять что 575127/670 ближе к правильному корню чем 460960/537. Можно писать на C++ так как хороший оптимизатор производит все вычисления в вещественных регистрах процессора с расширенной точностью не пытась привести отрезать их до двойной точности. Ты производил поиск на C++ или умудрился написать "правильное" решение на Java? Или написал через тип extended на Delphi?

The correct solution:
    public String approximate(int N, int D) {
        long c = N, d = 1;
        for (long b = 1; b <= D; b++) {
            int q = (int) Math.round(Math.floor(b * Math.sqrt(N)));
            for (long a = q; a <= q + 1; a++) {
                if (c * b - a * d > 0) {
                    if ((c * b + a * d) * (c * b + a * d) > 4 * b * b * d * d * N) {
                        c = a;
                        d = b;
                    }
                } else if (c * b - a * d < 0) {
                    if ((c * b + a * d) * (c * b + a * d) < 4 * b * b * d * d * N) {
                        c = a;
                        d = b;
                    }
                }
            }
        }
        return "" + c + "/" + d;
    }

Кстати,
int q = (int) Math.round(Math.floor(b * Math.sqrt(N)));
это принципиально? Мне кажется, что что то же самый эффект будет иметь выражение
int q = (int)(b * Math.sqrt(N));


А вообще супер элегантное решение! Признаю, что я достаточно долго тормозил, чтобы убедить себя что оно правильно.

Жаль только, я не написал его вчера на контесте =(

FEuzPzqFOtxkxPAJ

(Anonymous)
a6a7d2745ee994377352f07b209ce0d6

  • 1