CodeChef invites you to participate in the June 2012 CookOff at http://www.codechef.com/COOK23
Time: 2130 hrs 17th June 2012 to 0000 hrs, 18th June 2012 (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: http://www.codechef.com/COOK23/
Registration: Just need to have a CodeChef user id to participate. New users please register here
Problem Setter: Anil Kishore
Problem Tester: Hiroto Sekido
It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.
в Golden Trees все матрицы писали? У меня не зашло O(k3·log n), впрочем иначе на codechef и быть не могло
У меня в итоге даже на джаве зашло, правда, пришлось поупихивать. Итоговая отсечка, позволившая запихать в ТЛ, — брать по модулю k^2 раз за умножение, а не k^3.
Это не запихивание, а стандартный хак. Его одного хватает почти всегда в таких случаях. У меня кстати действительно в 8 раз ускорило.
Ну когда на локальной машине работает мгновенно, а на их тракторе не лезет в ТЛ, — имхо это всё же запихивание.
Суровая машина. У меня на i7 работало 2с. 3 теста по 101. После этого 0,3
У меня это было сразу. Спас отказ от двумерных массивов в пользу одномерных
Посмотрел сколько точно версия без этого работала, получилось 0.4с (правда, это 1 тесткейс; но это джава). Машина у меня довольно слабая, Core Quad Q8300 (64bit linux). Но даже если умножить на 3 — получается заметно меньше 2х секунд.
В общем в любом случае, по-настоящему суровые машины — это то, на чём они тестят :)
дак вот для чего модуль нестандартный...
Я долго не мог понять, почему у меня на последний тест ответ не совпадает. Сделали бы модуль 1234567 (только еще и простой) и тогда бы все копировали его. А так — привычка уже, если вижу 100..07, то вбиваю 109 + 7.
Я писал матрицами, но долго не заходило. Помогло, когда матрицы все сделал long long и убрал взятие по модулю в умножении. Брал все по модулю только после выполнения умножения (k^2 взятий по модулю на умножение). После этого зашло (локально 0.77 работало на макс тесте).
да я думаю, нас таких много
Я весь контест пихал за такую ассимптотику с разными хаками и с лонгами в том числе, так и не сдалась. Конечно такие ТЛ это просто ужас.
Is it possible to solve "Alien Chefs" in Java? My solution TLs, and the same solution translated to C++ gets AC. It seems that the issue is because of server's performance (which is terrible — I don't know why the solutions are tested on such an ancient hardware). Do jury have a Java solution for this problem?
Upd: Oh, I see EgorK managed to do it in Java. It's interesting what magic optimizations are required for this :)
I just leave this here.
When I used C++, performance issues were not this terrible (maybe because jury has C++ solutions and TLs are set with respect to them) — it was always possible to optimize program enough. But seems that it is not the case with Java. I'll add the suggested comment in my template for the next Cook-off :)
I actually do not have any magic optimizations. All my TLs were due to slow algorithm (
). When I finally got it right (
) it passed time limit instantly. It actually can further be optimized to 
. You can view it here
My solution is very simple and has complexity O((n + kq)log(n + kq)). You can view it here.
Interesting... My solution was
, and still it got TL (while locally it worked 1sec for max-test). Maybe it failed because I abused ArrayList's too much or for some other java-specific reason... Thanks for the reply, I'll try to do some experiments.
Ну что такое. На 25 минут уже продлили. Я увидел, что за 10 минут не напишу 5-ую и забил. А так...
А кто как решал Connecting Soldiers? У меня получилось только предпросчитать и забить константный массив для каждого n отрезок, на котором ответ 0.
Это английская ветка.
Я сгенерил отрезки [min, max] брутфорсом до N = 10, увидел закономерность и отправил.
UPD: код.
У меня спокойно (n^2m^2) c бряком залез.
Ну динамикой, и кучей оптимизаций. Типо заметить что максимульная сумма, которую можно получить, меньше 500. Значит динамика 30*500 а не 30*1000. Еще можно заметить, что в динамике не надо перебирать эквивалентные состояния, то указатель куда мы ставим текущего солдата тоже перебираем до середины. Вроде это все оптимизации, и да на Java мне кажется вообще без вариантов.
Wat?
я балбес, а это крутое решение :)
как-то так
Я сказал, что раз N ≤ 30, то можно хранить строчку динамики в int (динамика true/false). И тогда пересчёт не за O(nm), а за O(m).
Please check the editorials here: http://discuss.codechef.com/tags/cook23/