Google Code Jam 2011 Online Round 2

13 лет назад, # |

+23

С одной стороны - круто, что футболок в этом году аж тысяча, многим дополнительный стимул. С другой стороны - получается, футболки опопсели:)

→ Ответить

13 лет назад, # ^ |

+22

думаю, что футболки с топкодера, асм и кодеджема будут актуальными достаточно долгое время ;)

→ Ответить

JKeeJ1e30

13 лет назад, # ^ |

-62

А, может быть, уровень программирования стал выше?

→ Ответить

caustique

13 лет назад, # ^ |

+19

Получил футболку, высокоуровневый?

→ Ответить

JKeeJ1e30

13 лет назад, # ^ |

Я не принимал участия в этом году.

→ Ответить

unprost

13 лет назад, # ^ |

А скольким давали в прошлые годы?

→ Ответить

AndreySiunov

13 лет назад, # ^ |

-9

Кажется что-то около 300-350

→ Ответить

taras.klaskovsky

13 лет назад, # ^ |

+22

В прошлом году 500.

→ Ответить

agul	13 лет назад, # \| -6 Поясните case #2 в задаче А. → Ответить

13 лет назад, # ^ |

-11

Что там объяснять особо?

Оптимальное решение - бежать с самого начала. Тогда за 3 секунды добежим до первого эскалатора, за секунду пробежим 3 метра по нем, и потом за полторы секунды пройдем оставшиеся 3 метра.

→ Ответить

agul	13 лет назад, # ^ \| -8 Спасибо, я неправильно понял условие. → Ответить

13 лет назад, # |

-70

гавно, а не раунд

→ Ответить

13 лет назад, # ^ |

-13

Хороший раунд.

Правда, я почти час убил из-за того, что невнимательно прочел условие первой - думал, что в большом наборе не время бега до миллиона, а число тестов - от этого я завис:)

Но теперь вот дописываю вторую... Прочитал третью... Хорошие задачи. И уровень выше, чем в прошлом году.

→ Ответить

13 лет назад, # ^ |

-41

первую жадно решили?

→ Ответить

13 лет назад, # ^ |

Пусть раунд закончиться, тогда и обсудим:)

→ Ответить

13 лет назад, # ^ |

+25

Слишком простой, да )

→ Ответить

13 лет назад, # |

-58

как решать 1ю?

→ Ответить

13 лет назад, # ^ |

Самое время спросить

→ Ответить

13 лет назад, # ^ |

-11

Нен, ещё 27 минут.

→ Ответить

agul	13 лет назад, # ^ \| -6 Опять капитан? → Ответить

13 лет назад, # ^ |

Раунд ещё 36 минут примерно длился после твоего вопроса, к чему такие вопросы до конца раунда?

→ Ответить

agul	13 лет назад, # ^ \| ← Rev. 2 → +3 Правильно ее нужно решать. → Ответить

13 лет назад, # ^ |

-19

конкретней можно?

→ Ответить

agul	13 лет назад, # ^ \| +8 Только после контеста. → Ответить

13 лет назад, # ^ |

+25

Для особо одарённых.
До конца раунда обсуждать задачи запрещено.

→ Ответить

13 лет назад, # ^ |

-53

я понимаю, но все таки, че там, как там,а?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

+22

Там решать дисквалификацией с соревнования.

→ Ответить

agul	13 лет назад, # ^ \| 0 Все равно, даже если вам расскажут, то одна решенная задача вам даже майку не даст. → Ответить

13 лет назад, # ^ |

-20

никто этого и не говорил, что она мне майку даст, ну мне просто че то интересно. ну вы б уже сказали, ничего в этом такого нет....

→ Ответить

agul	13 лет назад, # ^ \| +13 Есть - никто не хочет быть дисквалифицированным. → Ответить

13 лет назад, # ^ |

← Rev. 2 →

-30

вы удивительно рассуждаете, я ж не код прошу... да вы не волнуйтесь, жизнь наладится, никто никого не дисквалифицирует...

→ Ответить

agul	13 лет назад, # ^ \| +16 Код, не код - обсуждение решений => дисквал. → Ответить

13 лет назад, # ^ |

-13

ну вы беспалева в личку, оп, и жизнь удалась

→ Ответить

agul	13 лет назад, # ^ \| +16 =========================================== вы уже спалились с личкой) → Ответить

13 лет назад, # ^ |

-8

я думаю тут ничего такого нет, это личное дело каждого, что писать в ЛИЧНЫХ сообщениях

→ Ответить

agul	13 лет назад, # ^ \| +11 ============================================== как хотите, а я правила нарушать не хочу. → Ответить

13 лет назад, # ^ |

-16

думаете админы code jam отслеживают все сайты по олимпиадному программированию, и их форумы.... так что пишите, ниче страшного в этом не будет

→ Ответить

13 лет назад, # ^ |

+14

Вы очень наивны. Вот, смотрите, еще как отслеживают.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

+24

ты время не трать на читера с левым акком, а пиши контест ;)

→ Ответить

13 лет назад, # ^ |

ну как бы это мой один единственный акк на кодфорсе....

→ Ответить

agul	13 лет назад, # ^ \| 0 Мне уже ничего не светило... → Ответить

ACube

13 лет назад, # ^ |

+14

Это не читер, это тролль!

→ Ответить

13 лет назад, # ^ |

+17

==============================
Может, это сотрудник Google, пытающийся обнаружить здесь нечестных участников?

→ Ответить

shilov

13 лет назад, # ^ |

+26

======================

И ник такой выбрал, чтоб не палиться)

→ Ответить

13 лет назад, # ^ |

Просто из любопытства, что вы называете словами "я понимаю"?

→ Ответить

13 лет назад, # ^ |

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

как то так

→ Ответить

agul	13 лет назад, # ^ \| +1 Под freopen'а косите с гуглом и википедией? :D → Ответить

13 лет назад, # ^ |

а что я должен был ответить? мне кажется более, чем логичный и исчерпывающий ответ

→ Ответить

13 лет назад, # ^ |

+13

Тогда мне интересно, как еще можно понять фразу "только после контеста", кроме того, что вам никто ничего не скажет в ближайшие n минут?

→ Ответить

13 лет назад, # ^ |

есть такое слово-надежда, так вот она умирает последней

→ Ответить

13 лет назад, # ^ |

так что за мою вменяемость не беспокойтесь

→ Ответить

Perlik

13 лет назад, # ^ |

-13

а ты подумай, может все-таки нужна помощь санитаров из codeforces?

→ Ответить

13 лет назад, # ^ |

какие санитары codeforces? ни разу не слышал, поподробней можно?

→ Ответить

13 лет назад, # ^ |

+37

Да, почитал выше и осознал. Попробую обьяснить. Дело в том, что в олимпиадном программировании уже сложилась традиция не читерить на соревнованиях, если есть такая возможность. Это же просто спорт, он не дает особых бонусов кроме умения думать, которое можно получить только не считерив, тут уж никого не обманешь. Поэтому люди соревнуются даже не в том, кто лучше напишет контест, а в том, кто лучше решает задачи. К тому же олимпиадное программирование некоторыми(в частности, мной) воспринимается как общество необычных в какой-то мере людей. Людей, которые умеют то, что не умеют другие. Людей, которые стремятся достичь совершенства через труд и терпение. Людей, которые, видя свои достижения, гордятся, что добились их своими силами. Поэтому позиция сообщества на подобные вещи, как мне кажется, должна быть общей - никакого читерства.

А вообще это очень интересная тема, у кого другой взгляд - интересно его узнать.

→ Ответить

k-va	13 лет назад, # ^ \| ← Rev. 2 → +12 Безусловно, в отдельный топик надо вынести. И с эпиграфом из "Понедельник начинается в субботу"... → Ответить

13 лет назад, # ^ |

Вот, что-то вышло.

→ Ответить

maincpp

13 лет назад, # ^ |

Утром у меня вышла черепааха... :D

→ Ответить

13 лет назад, # ^ |

Предлагаю игнорировать все посты этого участника.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

не туда

→ Ответить

13 лет назад, # ^ |

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

→ Ответить

Egor	13 лет назад, # ^ \| 0 А еще можно заметить, что нас интересует только e - b, а все остальное можно в один кусов с 0 скоростью → Ответить

13 лет назад, # ^ |

← Rev. 2 →

и так я тоже делал, но только опять же сортировал по времени прохождения участка

→ Ответить

13 лет назад, # ^ |

хм, странно что у меня не прошло, я делал так же, только сортировал не по скорости, а по времени прохождения участка

→ Ответить

13 лет назад, # ^ |

Ну а надо было как раз по скорости.

→ Ответить

13 лет назад, # ^ |

-12

капитан конечно...

→ Ответить

13 лет назад, # ^ |

А надо было по скорости. Легко заметить, что можно длинный отрезок разбить на много маленьких, отчего порядок в массиве изменится, изменится и ваш ответ. А вот не должен.

→ Ответить

13 лет назад, # ^ |

действительно.... спасибо

→ Ответить

13 лет назад, # ^ |

обидно конечно, сначала и хотел по скорости

→ Ответить

13 лет назад, # ^ |

10 1 2 1 1
2 10 2

ваш алгоритм пойдет по более долгому участку и пройдет за 2+(1+4/3), а надо было за 1+(8/3)

→ Ответить

13 лет назад, # ^ |

да спасибо, я уже понял

→ Ответить

13 лет назад, # |

← Rev. 2 →

Расскажите условие D, пожалуйста

UPD: спасибо

→ Ответить

taras.klaskovsky

13 лет назад, # ^ |

Условие?

Дан граф, нужно найти минимальный путь из 0 в 1 с максимальным количеством вершин "на расстоянии в один ход(в которые можно попасть из какой-нибудь вершины пути за один переход)" от этого пути

→ Ответить

natalia

13 лет назад, # ^ |

Нужно найти кратчайший путь из вершины 0 в вершину 1, чтобы множество вершин, смежных с вершинами этого пути, было как можно больше.

→ Ответить

13 лет назад, # ^ |

а лучше - решение...)

→ Ответить

13 лет назад, # ^ |

+16

Дийкстра обычная. Весом будем считать длину пути * 1000 минус количество вершин, которым мы угрожаем. Понятно, что для очередной вершины на пути множество вершин, которые она атакует, может пересекаться только с множеством для предыдущей вершины, и для позапредыдущей (если бы оно совпадало с поза-поза-предыдущей, то это было бы странно -- это бы означало что между ними есть путь длины два, а на нашем кратчайшем пути они на расстоянии три).

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

→ Ответить

Egor	13 лет назад, # ^ \| +13 Только зачем там Дийкстра если это динамика? Циклов то в этом новом графе нету → Ответить

13 лет назад, # ^ |

походу у него нет нового графа, он не делает бфс вначале, а сразу пускает эту дейкстру.

→ Ответить

13 лет назад, # |

Контест интересный, несмотря на то, что футболочку я не выиграл :(.
А всё из-за того что, в первой задаче время которое можно бежать у меня было int и при вычитании не целых величин всё было плохо. Как результат задача решенная на 30-ой минуте была сдана в 2:10 и шансов закодить что-нибудь ещё не осталось.
Мораль: будьте внимательны :)

→ Ответить

Monyura

13 лет назад, # ^ |

-11

Ядрёна мать! Спасибо! Полностью та же ситуация, только я так и не нашёл ошибку на контесте ибо решил, что неправильный алгоритм. А сейчас смотрю коммент, лезу в код, и что я там вижу?) int t; Чтоб его...

→ Ответить

13 лет назад, # ^ |

А разве, если из int вычесть double, получится не double?

→ Ответить

13 лет назад, # ^ |

Потом все равно в int записывается

→ Ответить

13 лет назад, # ^ |

Должен double. Возможно, дело в том, что int поделить на int будет int, хотя тут лучше видеть код.

→ Ответить

Monyura

13 лет назад, # ^ |

Если использовать -= то получиться int, а я именно так и делал.Ну видно совсем был плох - потом ещё и к целочисленное координате += дабл применял.

→ Ответить

13 лет назад, # ^ |

int a = 10; double b = 5.5; a -= b;
Невероятно, но Java на это забивает и спокойненько исполняет, Eclipse даже не написал warning; не ожидал я такого. Студия warning выдает хотя бы.

→ Ответить

13 лет назад, # ^ |

g++ с -Wall тоже молчит =)

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

======================================
Да просто Java все подобное вообще компилировать не должна, это ж из серии if (a = b)....
Я так думал. Но вот найден прецедент, теперь надо быть внимательнее с этим.

→ Ответить

13 лет назад, # ^ |

А я из-за двадцати warning'ов про то, что scanf и freopen древние функции не заметил :(.

→ Ответить

Kostroma

13 лет назад, # ^ |

← Rev. 2 →

юзайте #define CRT_SECURE_NO_WARNINGS впредь :)

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

→ Ответить

13 лет назад, # ^ |

Ещё можно в параметрах компиляции писать /D_CRT_SECURE_NO_DEPRECATE (ну, или аналогично дефайном) - так лучше, ворнинги остаются, но те, которые надо. Хотя, впрочем, unused variables студийный компилятор автоматически не ловит - видимо, тут погуглить надо, но лень :)

→ Ответить

13 лет назад, # ^ |

Мне визуалка тоже не очень нравится :).

→ Ответить

13 лет назад, # ^ |

Могу представить, неприятно, когда тебя на пенсию вот так отправляют.
Когда-то давно один мой сокомандник принципиально называл счётчик кейсов в мультитесте моим именем - и потом в коде красовалась строчка
--ferlon;
- меня тоже почему-то слегка смущало.

→ Ответить

13 лет назад, # ^ |

Ну так ясно почему - ник с маленькой буквы написан.

→ Ответить

13 лет назад, # ^ |

Вообще там была такая тема, что это по-хорошему в опциях компиляции надо писать. Но я не знал, что такое опции компиляции, мне просто не нравилось --, вот было бы ++ - было бы здорово. Ещё над Саней Бахтуриным тоже прикалывались, что его команда пишет с директивой
#include <alphastream>.

→ Ответить

13 лет назад, # ^ |

Я уж про
freopenа не говорю.

Тут вообще всемирный флешмоб какой-то.

→ Ответить

13 лет назад, # ^ |

Ну он-то, прямо скажем, сам виноват :-X
(Кэп с вами)

→ Ответить

13 лет назад, # ^ |

Ээм? В чем я виноват? В том, что Microsoft считает одноименную функцию старомодной?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

=================
Сейчас я имел в виду не deprecated, а вообще всяческие кривые использования одноимённой функции. Здесь я исхожу из предположения, что C-библиотека stdio всё-таки старше Вас.

→ Ответить

13 лет назад, # ^ |

=======================
Я думал, что в какой-то ветке мы уже перешли на "ты". Сходу так не найду ее.

А то, что компилятор ругается на неправильное - правильно делает, нечего freopen неправильно использовать.

→ Ответить

13 лет назад, # ^ |

=========================
Хм, не помню такого. Ну да ладно, я-то не против перейти на "ты".

Это-то так, однако понятно, что люди его всё равно будут использовать как угодно, а в том числе и как попало, так что выбор такого ника - it is your own risk :)

→ Ответить

niyaznigmatul

13 лет назад, # ^ |

Java при компиляции раскрывает это выражение как
a = a - (int)(b)

→ Ответить

cerealguy

13 лет назад, # ^ |

JLS подсказывает, что на самом деле a = (int) (a-b).

15.26.2 Compound Assignment Operators
A compound assignment expression of the form E1 op = E2 is equivalent to E1 =(T )((E1) op (E2)), where T is the type of E1, except that E1 is evaluated only once.

→ Ответить

niyaznigmatul

13 лет назад, # ^ |

хм... действительно

→ Ответить

yeputons

13 лет назад, # |

← Rev. 2 →

~~Почему могло не зайти тупое решение на D-small:~~

~~Нашли BFS'ом кратчайшее расстояние~~
Далее перебрали все кратчайшие пути (идём по ребру, только если d_b = d_a + 1, где a и b - концы ребра, а d_i - кратчайшее расстояние от нашего дома до вершины i) "в лоб" и посчитали вторую величину.
~~PROFIT Oops, wa...~~

?
Код

Нашёл баг. Был специфичным: не проверял в переборе условие, что мы достигли вершины компа за минимум (опустил проверку последнего ребра в пути).

→ Ответить

13 лет назад, # ^ |

А D-large могло не зайти если не проверять что последняя вершина смежна с 1 )

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Потому что твой перебор может обнулить лишние пометки когда backtrack'ится, надо делать не булевый пометки а счетчики увеличиваемые/уменьшаемые на 1..

Что-то я сегодня совсем невнимателен)

→ Ответить

13 лет назад, # ^ |

Ты не поверишь :о)

→ Ответить

13 лет назад, # |

Блин, C.large после C.small такой капитан, а я не сдал(

→ Ответить

13 лет назад, # ^ |

Я чуть было не зафейлил C-large; нельзя считать логарифм как floor(log(a)/log(b)), лучше написать цикл из умножений, он даже быстрее работает

→ Ответить

http://dl.dropbox.com/u/90953/B-large.zip

13 лет назад, # ^ |

Я цикл из умножений и делал. Я не догадался, что можно не все простые искать а только до корня..

Прошел бы в рануд3, если бы сдал

→ Ответить

Kostroma

13 лет назад, # ^ |

да ладно, ты уже обрадован футболкой :))

→ Ответить

yarrr

13 лет назад, # |

← Rev. 2 →

Подкажите правильный результат на B-large, пожалуйста:

→ Ответить

yeputons

13 лет назад, # ^ |

http://pastebin.com/nuC2cGxp

→ Ответить

yarrr

13 лет назад, # ^ |

Странно как-то, на Small правильный ответ, на Large полную фигню.

Спасибо за помощь, пойду баг искать.

→ Ответить

Shtrix

13 лет назад, # ^ |

Если вы делали с даблами, то советую увеличить точность до 1е-10 и использовать long double.

→ Ответить

yarrr

13 лет назад, # ^ |

← Rev. 2 →

Не, я лонгами делал. Г

Где-то в проверке квадрата с чётной стороной ошибся.

→ Ответить

13 лет назад, # ^ |

я так понимаю моё решение B-large упало из-за точности double.

как правильно решать эту задачу?

→ Ответить

13 лет назад, # ^ |

Там только деление на два в формулах -> можно решать целочисленно.

→ Ответить

13 лет назад, # ^ |

в каких формулах деление на два? очевидно у меня не такие формулы, иначе бы не спрашивал :)

→ Ответить

13 лет назад, # ^ |

Ну я делал так. У меня были матрицы a[i][j] исходных данных, h[i][j]=a[i][j]*j и v[i][j]=a[i][j]*i, а также их частичные суммы. Выделяем квадрат со стороной r, левым краем x и верхним y. Сумма h по квадрату будет учитывать координату y первого столбика с коэффициентом y, а должна с коэффициентом y-(y+(r-1)/2). Значит к этому значению надо прибавить значение суммы a на квадрате с коэффициентом (y+(r-1)/2). Получим координату x центра масс. Также со второй координатой.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

наверное h[i][j] это не число a[i][j] * j

а некоторая структурка с массой a[i][j] и координатой j? иначе я вообще не понимаю о чем речь. если это структура, то координата при их сложении становится дробной. если дробь сделать втупую на long long то должно переполнится, я придумал изрвать чтобы не переполнилось. но как вы говорите решать в целых числах я так и не понял.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

--------------------------------------------------------------------------------

Нет, все правильно, именно число. 1) Заметим что координаты центра масс можносчитать независимо друг от друга. 2) координата i считается по формуле sum(aij *i) / sum(aij) Обе суммы у нас досчитаны, поэтому сравнить координату с нужной полуцелой можно в целых числах

→ Ответить

13 лет назад, # ^ |

-8

Нет, просто число. Чтобы посчитать центр масс по горизонтали, надо складывать суммы в столбцах с коэффициентами (-r/2),(-r/2+1),...,0,...,r/2. А у нас есть суммы с коэффициентами x,x+1,...,x+r. Поэтому их надо нормировать. Чтобы сдвинуть все на 1, надо прибавить к ответу просто сумму в квадрате, тогда столбцы будут с коэффициентами x+1,...,x+r+1. Вы почитайте мое решение, может, вам понятнее будет.

→ Ответить

I_love_natalia

13 лет назад, # ^ |

Мое решение отличалось только тем, что в функции я передавал (l, t, r, b) :) там набаговать меньше шансов, вроде, потому что сразу можно r и b смещать на 1

→ Ответить

Edvard

13 лет назад, # |

У меня два вопроса:

1. Все решения уже проверили или ещё ожидается проверка

2. Сколько человек проходит в следующий раунд

→ Ответить

13 лет назад, # ^ |

1. вроде как все проверили

2. 500

→ Ответить

Edvard

13 лет назад, # ^ |

Блииин я не попал с следующий раунд(((

→ Ответить

13 лет назад, # ^ |

если это тебя утешит, то я тоже не попал(

→ Ответить

Edvard

13 лет назад, # ^ |

К сожалению нет((

→ Ответить

13 лет назад, # ^ |

+18

меня тоже не утешает то, что я не попал))

→ Ответить

13 лет назад, # ^ |

может тогда вас обоих утешит тот факт, что я даже футболку не получу? ;)

→ Ответить

13 лет назад, # ^ |

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

→ Ответить

13 лет назад, # ^ |

+10

переквалифицируюсь в журналисты, пока не поздно ;) может меня хотя бы трофей блоггера найдёт =)

спасибо за сочувствие :)

→ Ответить

Xazker

13 лет назад, # ^ |

Я тоже за 1000, epic fail :)

→ Ответить

13 лет назад, # ^ |

предлагаю создать клуб неудачников GCJ =)

→ Ответить

13 лет назад, # ^ |

+12

"Клуб тех, кто в следующем году всех порвет на GCJ"

→ Ответить

ArtemKadeev

13 лет назад, # ^ |

Я с вами если что...

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

=================
И я тоже с вами. Четыре раза участвовал в GCJ, все четыре не смог войти в топ-500 (и да, сейчас я даже майку не получил).
Формат слишком уж отличный от ACM и TopCoder, тут тактика совсем другая нужна, а какая - не знаю.

→ Ответить

13 лет назад, # ^ |

========================
По-моему, почти ничем не отличается от формата ACM. Разве что баллами - но это даже более справедливо

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

===========================
Да ну?
Эта задача вроде проще, но она и дешевле стоит, чем другая, - так какую же мне решать?
Я знаю, как решать для маленького теста, так стоит ли мне думать над большим или же решить для маленького с тем, чтобы переключиться потом на маленький для другой задачи?
И, наконец, вот здесь я знаю решение, про которое мне интуиция, наработанная годами игры по другим форматам, подсказывает, что в две секунды оно не уложится, но уложится ли в две минуты? стоит ли писать?
И даже если я могу точно оценить, что в худшем случае моё решение не уложится в восемь минут, насколько близок будет большой тест к худшему случаю, к тому гипотетическому, где все кейсы - одинаковые и самые плохие?
Все эти вопросы не возникают, конечно, если ты точно можешь решить все задачи, и так решить, что наверняка уложишься в TL. Но я ведь простой смертный.

→ Ответить

yeputons

13 лет назад, # ^ |

==================
Я лично просто читаю+решаю задачи тупо подряд, и, если есть больше часа, сразу на Large.

→ Ответить

13 лет назад, # ^ |

-9

Я первый раз в жизни участвовал. Получилось плохо. Я все время как какой-то ненормальный в суете еле как сдавал даже самые простые задачи. Сегодня до последнего дебажил B-Large написанную в целых (чтобы уж наверняка) и за 53 секунды до конца послал. Это не принесло мне выхода в следующий раунд, зато принесло футболку.

→ Ответить

13 лет назад, # ^ |

первый раз в жизни? а как ты отборочный прошёл? =)

мои поздравления, с футболкой вас :)

→ Ответить

caustique

13 лет назад, # ^ |

Молодец.

Чую, если б ты не получил футболку, не миновать срача на тему "синие да зеленые повылазили" ^__^

→ Ответить

13 лет назад, # ^ |

Не вижу никакой связи. GCJ - это соревнование, совершенно непохожее на TopCoder, CF, ACM ICPC и так далее. Я не знаю почему, но мне не удавалось быть спокойным в течение всех трех моих раундов. Все время суетился почему-то. Даже на самом тупом квале, где только ленивый не набрал 100 очков, я до последнего проверял свой код и думал, что у меня что-то там может упасть.

Да такого игрока, как я на GCJ, можно и нужно побеждать. Я таким был, когда решал свои первые раунды на TopCoder'е. Сейчас, на соревнованиях кроме GCJ я гораздо более спокойный и делаю в разы меньше ошибок. А синие и зеленые - это тут, внутри Codeforces, там за его пределами все мы одного цвета.

P.S. А что, их на самом деле так много "повылазило" там на GCJ?

→ Ответить

dkirienko

13 лет назад, # ^ |

===============================

Я тоже участвовал в gcj впервые и понял, что здесь надо рисковать. Уверен в алгоритме? Немного поотлаживал? Тогда - сдавай. Если будешь дебажить и тестировать до конца тура, то потеряешь баллы на других задачах. Поэтому - надо рисковать и сдавать.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

+14

===============================
И я впервые участвовал, но вот волнения не было, скорее наоборот. Я писал так же, как и любой другой контест - по порядку и то, что знаю.

По тем ощущениям, что я получил, GCJ - это лучший контест на свете. Мне он очень понравился. Обязательно буду играть каждый год.

И да, по-видимому, многие из "клуба неудачников GCJ" решали задачу B вместо задачи C, и из-за этого не прошли.

P.S. Я был синим один контест назад и повылазил, это считается? :)

→ Ответить

Kenny_HORROR

13 лет назад, # ^ |

-8

===============================

А что реально сложного в задаче B? По моему вполне себе нормальная задача. Хотя С пожалуй более халявная (с точки зрения писать, а не понять условие).

→ Ответить

13 лет назад, # ^ |

-26

ИМХО в ней самый оцтой это переолпение дабла, ну блять давать задачу на то что дабл это недержит это как-то тупо, хоть что говорите. Ну блять ну ладно, реальной жизни бывают такие задачи, но наёбывать на этом во время контеста это дибилизм

→ Ответить

13 лет назад, # ^ |

Не совсем ясно в чем риск проявляется. В любом случае засылать нужно тогда, когда уверен, что код решает поставленную задачу. Риск может быть только в выборе: думать ли над large, если по нему идей сходу нет, или же писать small.

→ Ответить

13 лет назад, # ^ |

============================

На последнем раунде у меня был выбор после сдачи A-Small, A-Large и B-Small: решать B-Large, в решении которой я уверен и осталось только написать или решать C-Small, которую я еще даже не читал. Я выбрал решать C-Small (которая мне так и не далась) и потерял кучу времени из-за чего в конце в попыхах еле успел написать B-Large.

→ Ответить

13 лет назад, # ^ |

Ситуация специфична не только для GCJ. На ACM контесте вполне может быть такое. Знаешь решение на задачу, но не слишком простое + подозреваешь, что другая задача решается быстрее и проще, но ты её не читал)

→ Ответить

13 лет назад, # ^ |

На ACM это несколько компенсируется пятью часами и большей информацией из монитора.

→ Ответить

13 лет назад, # ^ |

Да ладно, я ведь не хочу доказать, что соревнования равнозначны. Я просто уверен, что побеждает сильнейший. Остальное - нюансы. А если хочется риска - это в покер нужно подаваться.)

P.S. Мы с тобой как-то синхронно цвет меняем)) Ты был желтый - я был желтый. Сча оба сиреневые))

→ Ответить

13 лет назад, # ^ |

Да, надо завтра синхронно сменить обратно на оранжевый.

→ Ответить

13 лет назад, # ^ |

Можно. Но нежелательно. Лучше - сразу красный)

→ Ответить

13 лет назад, # ^ |

=======================

Ваня, ты сам сказал, что независимо от соревнования побеждает сильнейший. Но в каждом виде соревнований есть свой сильнейший. По определению кто-то в чем-то лучше, а в чем-то хуже. Например, Codeforces я решаю более успешно, чем TopCoder. Впрочем, стоит заметить, что сложно что-то решать хуже, чем я решаю TopCoder :)

→ Ответить

dkirienko

13 лет назад, # ^ |

================================

Риск не сдать large, очевидно. Сидишь и думаешь - попробовать сдать или еще потестировать?

→ Ответить

I_love_natalia

13 лет назад, # ^ |

← Rev. 3 →

================================
Не знаю, ничего не тестировал, все зашло)
На самом деле small является очень хорошим претестом, если писать аккуратно.

→ Ответить

13 лет назад, # ^ |

аналогично))

→ Ответить

AlexErofeev

13 лет назад, # ^ |

1. Все. Их вроде потом будут вручную запускать и/или ловить читеров сверкой кода, но серьезно это на результаты не повлияет
2. Наверху же написано. 500 - в 3 раунд, 1000 - футболочки

→ Ответить

13 лет назад, # ^ |

1. Все решения проверяются по ходу контеста. Сравнить два 50kb файлика недолго. Как только контест оканичивается - результаты полные.
2. 500 человек, вот правила.

→ Ответить

natalia

13 лет назад, # |

Отправила по B-large не тот файл (вероятно, это ответ на B-small). Отправленный код генерирует правильный ответ на B-large, однако он (по причинам, не связанным со злым умыслом :) не соответствует файлу output.txt. Меня интересует вопрос, должна ли я как-то уведомить об этом жюри, чтобы они не дисквалифицировали меня совсем?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Дисквалифицировать они не будут:
"If, after the close of any Round, an alleged discrepancy is discovered between the source code and the output file for any of a contestant's submissions that were judged correct during or at the conclusion of the round, a panel of two or more judges consisting of employees of Google and/or its subsidiaries shall examine the source code for all submissions of the contestant for that round. The judges shall determine, in their sole discretion whether a discrepancy exists, and if so whether the discrepancy is trivial or non-trivial. In the event of a trivial discrepancy, the contestant shall be assessed an additional 4-minute penalty for that input/output set. In the event of a non-trivial discrepancy, the contestant shall forfeit all points for that input/output set. In the event the judges rule that there is no discrepancy, no change will be made in the contestant's score for that input/output set and no penalty minutes shall be assessed. "

→ Ответить

13 лет назад, # ^ |

Если ты их уведомишь, то, по крайней мере, хуже точно не станет :о)

→ Ответить

13 лет назад, # ^ |

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

→ Ответить

Jokser

13 лет назад, # |

Блин, поленился написать тупой перебор с суммами в B-Large. Думал, там решение за чистый R*C
Как решать C? А то даже n! неправильно работал, т.к. я неправильно понял что считать за call, а что нет.

→ Ответить

Egor	13 лет назад, # ^ \| +5 В С нижнее число - это число простых не больше n, верхнее - сумма целых частей логарифмов по всем простым основаниям + 1 если n > 1 → Ответить

13 лет назад, # ^ |

Заметим что если зашли люди i1,..,iN, то после них LCM(i1, iN) - сумма

Заметим, как мы можем менять его, если мы хотим это делать долго, тогда нужно добавлять по 1 простому, это можно сделать выписав p,p^2 ... p^k для каждого p в таком порядке, потом заметим, что если мы хотим это делать быстро, то нужно наоборот сразу выписать p^k для каждого p. Заметим, что нельзя выписать макс.степени сразу у 2х простых. Отсюда ответ. Сумма степеней простых - их кол-во. А это Кол-во таких p^e<=n, что e>1

→ Ответить

maksay

13 лет назад, # ^ |

Максимум получается, когда мы берем все степени всех простых до Н в порядке возрастания, минимум - когда берем сначала их максимальные степени. (Понятно, что ЛЦМ и есть произведение этих максимальных степеней).

Ну а дальше ясно что простые после корня из Н встречаются 1 раз в обоих случаях. Значит ответ - сумма степеней всех простых до корня из Н минус их количество.

→ Ответить

VArtem

13 лет назад, # ^ |

← Rev. 3 →

Ясно, что в конце мы получим заказ на сумму = LCM(1, 2, ..., N). Посмотрим, как эту сумму можно набрать:

Минимум: берем каждое простое в разложении LCM в максимальной степени(это число не превзойдет N). Ответ - количество различных простых, не больших N.

Максимум: возьмем сначала 1, затем каждое простое в 1 степени, затем во 2, и т.д. Ответ - 1 + количество степеней простых, не больших N

Простые, большие $\text{[math]}$ , можно не учитывать, так как в оба ответа они войдут в точности 1 раз.

→ Ответить

GeLo	13 лет назад, # ^ \| 0 Я вот что-то туплю. Если сначала заходит p^a, а потом q^b, то сумма же может стать уже не кратной p^a? И тогда ему (p^a) придется звать официанта еще раз. Почему тогда для достижения минимума мы берем все максимальные степени простых ровно по одному разу? → Ответить

taras.klaskovsky

13 лет назад, # ^ |

← Rev. 2 →

Они зовут официанта один раз, и потом делают много заказов не отпуская его, пока не получится нок -- это считается за один вызов

→ Ответить

GeLo	13 лет назад, # ^ \| 0 А, вон оно что.. Ясно, спасибо. → Ответить

13 лет назад, # ^ |

Вот я тоже так думал :о(

→ Ответить

13 лет назад, # |

По задаче Б, почему в тесте:
1
4 4 0
5491
7653
8595
2281
ответ невозможно, а не 4?
Как по мне сумма сверху = сумма снизу, а сумма слева = сумме справа, или я в чем-то не прав?

→ Ответить

13 лет назад, # ^ |

Нужно ещё на рычаг домножать насколько я понял.

→ Ответить

13 лет назад, # ^ |

Эм, а вы читали определение центра масс там же ниже?

→ Ответить

13 лет назад, # ^ |

Читал, я имел ввиду "сумма", как сумма чисел умноженных на коэффициенты , это вроде-бы то-же самое будет, или я не прав?

→ Ответить

13 лет назад, # ^ |

А ну тогда извиняюсь, проверил на своем решении(Bsmall correct - выводит 4)

→ Ответить

13 лет назад, # ^ |

А большие тесты прошли?

→ Ответить

13 лет назад, # ^ |

Нет, решение тормозное.

→ Ответить

13 лет назад, # ^ |

А у Гены вывело Импоссибл.

→ Ответить

13 лет назад, # ^ |

У меня тоже IMPOSSIBLE
Если что, $\text{[math]}$

→ Ответить

alexey.enkov

13 лет назад, # ^ |

Вы на неправильные коэффициенты умножаете. Первая строка находится в 3 раза дальше от центра чем вторая.

→ Ответить

13 лет назад, # ^ |

оО, действительно, спасибо

→ Ответить

md5

13 лет назад, # |

В задаче А читал t в интегральный тип, поэтому когда пробегал неполные секунды, жестко терялась точность, в итоге 7 неудачных попыток. Задача С большая упала, т.к. прозевал что простые около 1e6 в квадрате переполнят int.

Если бы не это прошел бы с 48 и 1:26. А так даже футболку не получу. Думал что я адский неудачник, но почитав эту тему понял что не все так плохо... :)

→ Ответить

13 лет назад, # ^ |

-13

Не называйте тип целых чисел интегральным. Интегральный - это немного другое.

→ Ответить

md5	13 лет назад, # ^ \| ← Rev. 3 → 0 "In computer science, the term integer is used to refer to a data type which represents some finite subset of the mathematical integers. These are also known as integral data types." → Ответить

13 лет назад, # ^ |

По вашей логике и Crystal переводился как Кристальный?

→ Ответить

md5	13 лет назад, # ^ \| ← Rev. 2 → 0 Если честно - да, хотя зависит от контекста. В любом случае я не хотел задеть ничьих чувств, в отношении языка. Мне русский не родной, думал что такое слово есть, и обозначает именно целочисленный тип данных. → Ответить

13 лет назад, # ^ |

← Rev. 3 →

Crystal ни в каком контексте не может значить Кристальный :о) Жаль, что переводчики рекламы Lenor об этом не знают, и переводят нонсенс вроде "кристальной белизны" :о)

~~Также как integral не значит интегральный.~~

Это не правда

→ Ответить

caustique

13 лет назад, # ^ |

Lingvo говорит, что может

Как и integral может быть интегральным - но, очевидно, не в этом случае.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

+13

Ничего личного, но Лингве я верю больше, чем SkidanovAlex'у ;)

→ Ответить

13 лет назад, # ^ |

integral может значить "интегральный", но не в данном контексте. Иначе в вашей статье они были бы под одной цифрой.

→ Ответить

13 лет назад, # ^ |

Напали на человека средь бела дня =) По-моему, сразу видно, что человек не на родном языке пишет, к чему его подкалывать по этому поводу?

→ Ответить

13 лет назад, # ^ |

-53

1. Не средь бела дня а в 22:00msk. В вашем случае это 9 вечера, что тоже не слишком день.
2. Если бы автор указал страну проживания, можно было бы догадаться. Из сообщения я этого не понял, наречия типа "жестко" говорят об обратном, как мне кажется.

→ Ответить

13 лет назад, # ^ |

+25

1. В нашем случае это поговорка. А людей, которые воспринимают их в буквальном смысле, называют занудами =)

2. Сообщение больше адресовалось SkidanovAlex'y, собственно говоря, оно и помещено как ответ на его сообщение.

3. Если уж на то пошло, у него сейчас как раз день.

4. А Вы реально знаете русского, который называет C-large -- "С большая"?

→ Ответить