Отборочный тур Google Code Jam прошёл по плану

Сегодня в час по местному времени прошёл системный тест решений программистов-участников для двух задач. Я набрал плановое количество баллов, равное нулю.

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

С момента открытия первой из двух задач начинает капать счётчик обратного отсчёта, выставленный на 60 минут. Одна задача приносит максимум 250 очков, вторая - 500. Каждую секунду какое-то количество очков снимается, т.е. 250 очков за первую задачу можно получить только если мгновенно после открытия засубмитить правильный код.

Задачи можно было писать на Java, C++ или C#. Я выбрал C++, поскольку это максимально близко по синтаксису к РНР, который я знаю хорошо. Разумеется, мои знакомые недоумевали, как так можно - не знать C++ и участвовать в конкурсе програмистов на этом языке. Отвечаю: конкурс был не на знание C++, а на скоростное решение трудных задач.

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



Задачу-250 я решил, судя по тому, что 5 тестовых заданий дали правильные ответы, плюс решения других людей похожи на моё (их можно было посмотреть по окончании тура). Почему за неё не дали очков? Было ограничение, что программа должна решать задачу не дольше 2 секунд. Я закодил немного недодуманный алгоритм, поэтому, я думаю, не уложился, когда/если системный тест задал максимально допустимые входные параметры (50х50). Задача состояла примерно в следующем (постить оригинал не буду, это запрещено, но смысл передам): есть двумерный массив, состоящий из букв (квадратный). Требуется посчитать, сколько нужно сделать исправлений букв, чтобы каждая строка и каждый столбец стали полиндромом (читались одинаково слева направо и справа налево). Как я теперь думаю, можно было ограничиться проходом только по одной четверти квадрата, а я проходил по половине (почему-то вот так я решил).

Задача-500 была посложнее: есть 3-мерный массив координат астероидов. На каждом астероиде стоит излучатели, направленные на каждый из излучателей на других астеридах. Излучатели испускают лучи друг в друга, по которым передаётся инфа. Например, между двумя астероидами расстояние 5 парсек; один излучатель испускает луч длиной 2 парсека, а второй 3 (зависит от мощности излучателя, т.е. максимально возможной длины луча). Чем мощнее излучатель, тем он дороже. Ответ: найти минимальную требуемую мощность излучателя, которому приходится испускать самый длинный луч. Я решил втупую: проходим по массиву и находим максимальное расстояние по формуле sqrt(x*x + y*y + z*z), которую я придумал по аналогии с 2-мерной формулой. Полученное расстояние делим на 2 (типа каждый излучатель простреливает половину требуемого расстояния). Такое решение не прошло 3 из 5 тестовых заданий, давая больший ответ, чем надо, так что я не рассчитывал набрать баллы на ней.

Трудно себе представить, что за задачи будут дальше.

Зато я теперь более трезво оцениваю свои программерские силы. А так хотелось футболку...