Topcoder SRM 518 - Codeforces

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

Я один за 5 минут до конца забил на кодинг и сел наблюдать за несколькими известными личностями (Петя в первую очередь), у которых одна сданная задача и текущее место в шестой сотне? :)

→ Ответить

agul	13 лет назад, # ^ \| 0 Я тоже забил) Я не могу придумать 1000. → Ответить

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

Судя по таблице результатов, мало кто смог ее придумать:)

Ограничения кусаются, очевидный метод не катит.

→ Ответить

agul	13 лет назад, # ^ \| 0 Было бы К поменьше. Раз в 10^5 (: → Ответить

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

И как это Вам поможет? Мне бы помогло, если бы L было раз в 50 поменьше, тогда было бы всё ок.

→ Ответить

Skird

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

Угу, но тогда бы она была довольно скучна

→ Ответить

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

Я могу его понять. Я вот 500 написал на шару, не знаю пока, почему это не должно падать по TL.

→ Ответить

agul	13 лет назад, # \| 0 What happened with Petr? P.S. I think he has some technical problems. → Ответить

Timus

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

← Rev. 2 →

Арена упала у всех или только у меня?

Upd. Мда не работает ни сайт, ни арена. TopCoder меня забанил?:)

→ Ответить

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

У меня работает

→ Ответить

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

yarrr

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

У меня на родном провайдере тоже упал ТопКодер и Твиттер заодно, подключился к соседу = ок.

→ Ответить

diogen

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

← Rev. 2 →

Хмм.. что-то не так с этим раундом
открыл код у одного участника из комнаты (ник Kornacker) по 500-ке. А у него весь код, отличный от дефайнов в одну строчку, 2/3 которой закоменчены... пролистал, увидел, что он возвращает переменную, которую использует только один раз, когда объявляет равной 0. ну я, не долго думая, попытался сделать челлендж третим тестом из условия. и что бы вы думали? метод вернул то что нужно!
возможно, это какие-то проблемы с отображением переносов строк у кавиги в Java коде, но это тоже как-то непонятно, т.к. обычно все нормально.
Попросил друга посмотреть, у него точно так же как и у меня отображает только одну строчку рабочего кода...

может кто-нибудь знает в чем тут дело?

UPD. у решения вердикт passed system test

→ Ответить

agul	13 лет назад, # ^ \| 0 Не могли бы вы сказать номер комнаты, чтобы было проще искать? → Ответить

KADR	13 лет назад, # ^ \| 0 Можно по нику в div summary отсортировать. → Ответить

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

а ещё можно Main->Search и по нику найти в какой комнате... он пока ещё там)

→ Ответить

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

← Rev. 2 →

~~Я думаю большой тест из 500 убрать и было бы получше - больше файлидов и челленджей...~~

не туда ушло...

→ Ответить

imslavko

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

у меня тоже в одну строчку, но никаких Каваги

→ Ответить

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

мде, либо с переводами строк проблема либо кто-то очень нехороший человек...

→ Ответить

agul	13 лет назад, # ^ \| 0 Какая-то черная магия. ИМХО, беда с переводами строк. → Ответить

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

Верно ли, что в 1000 надо использовать Карацубу либо БПФ? Я вроде приумал, как писать Карацубу, но не успел.

→ Ответить

Egor	13 лет назад, # ^ \| 0 По слухам из достоверных источников Карацуба не проходил → Ответить

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

ого, а БПФ? Или надо было что-то совсем другое?

→ Ответить

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

Скажем, у меня решение за L * (log K + log L) - некоторое подобие Фурье (точнее, сначала я придумал Карацубу, а потом понял, как можно избавиться от одной из подзадач). Кажется, оно работало примерно за десятую секунды на макстесте.
При этом важно отметить, что L * log L * log K не проходит один из тестов в условии по времени (я был крайне удивлён этим фактом на контесте, но к счастью, я довольно быстро придумал, как от этого избавиться). В Карацубе же вынести этот логарифм не получится (потому что сложность Карацубы = суммарная длина задач на нижнем уровне, в отличие от Фурье, где на нижнем уровне суммарная длина равна L). Поэтому Карацуба наверняка не должен был проходить.

→ Ответить

sdryapko

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

Наивное решение на 500-ую правильное?

→ Ответить

agul	13 лет назад, # ^ \| 0 Смотря, что вы подразумеваете под наивным. → Ответить

sdryapko

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

То что писали все :D

→ Ответить

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

У меня прошло наивное.

После контеста надо будет в практисах бинарником найти количество итераций, которые надо делать...

У тиммейта вроде бы 1000 итераций не хватило.

→ Ответить

Commandos

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

Я смог подобрать тесты, где надо около 3700 операций делать. На большее ну никак. Сидел почти весь контест, искал подвох.

→ Ответить

agul	13 лет назад, # ^ \| 0 Вроде 100000 хватало точно. → Ответить

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

200000 хватало точно-точно.

→ Ответить

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

Я писал медленно и скудно, но писал не то что все, а точнее по смыслу то же, но у меня чистый n^2 * log(MAX_VALUE) каждое число высчитывал дихотомией, исходя из предыдущих, и так что бы следующим можно было составить что нибудь.

→ Ответить

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

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

→ Ответить

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

вот и посмотрим =)

→ Ответить

Jokser

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

Если пройдет такое решение как и у всех - это будет самая худшая 500 за всю историю TopCoder :)

→ Ответить

sdryapko

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

Я возненавижу тогда эту 500-ку...Потому что я решился отправить ее только за 10 минут до конца, хотя написана она была где-то на 25 минуте контеста...Не отправлял из-за того, что думал над нормальным решением...

→ Ответить

Commandos

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

← Rev. 2 →

А для меня лучшая 500-ка. Хотя минут 5 и тормозил до отправки, ибо думал, что за нафиг такой, не может быть всё так просто... ан нет. Passed.

→ Ответить

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

На редкость скучный систем тест получился. В совокупности с такой 500 - я ставлю этому раунду жирный минус.

→ Ответить

agul	13 лет назад, # ^ \| 0 После систеста положение практически не поменялось (Div1): 250: 7 Failed 500: 28 Failed 1000: 3 Failed → Ответить

ivan.popelyshev

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

Говно.

→ Ответить

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

→ Ответить

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

С одной стороны - приятно впервые в жизни попасть в топ-60. С другой - обидно, что такой результат не на крутом проблемсете, а не несбалансированном чуде вроде "ну... сколько итераций... да ладно, 100000 пашет 0.05, значит можно даже 200000 поставить... должно быстро сходиться..."

→ Ответить

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

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

→ Ответить

ivan.popelyshev

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

Мы все равно рады за выигравших, особенно за 12-ое место :)

→ Ответить

agul	13 лет назад, # ^ \| 0 А кто такой на 12ом месте? → Ответить

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

Я лично больше рад за 4 и 6, СПбГУ сегодня молодцы =)

→ Ответить

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

На codeforces говно плюсовать любят.

→ Ответить

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

Я думаю большой тест из 500 убрать и было бы получше - больше файлидов и челленджей...

→ Ответить

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

А еще можно дать в условии только такие тесты, где достаточно одной итерации.

Но это слишком жестоко)

Зато было бы намного интересней.

→ Ответить

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

Фух, всё таки не я один писал дихотомию на 500 что бы не париться с итерациями, правда таких единицы :)

→ Ответить

ibra	13 лет назад, # ^ \| 0 не сильно бы это повлияло. Я например написал наивное решение, потом чекер. Чекер 5 минут поработал, не нашёл тл-я и я немного ещё подумал и послал за 300 очков. → Ответить

Egor	13 лет назад, # ^ \| 0 Надо помнить, что ресабмит снимает не так уж много очков, так что писать чекер 5 минут до сабмита чаще всего не выгодно → Ответить

ibra	13 лет назад, # ^ \| 0 по-моему лучше подстраховаться и написать чекер, и потратить на это 3-5 минут, чем слать, а потом понимать что послал лажу → Ответить

Egor	13 лет назад, # ^ \| 0 Ну вот так 300 очков, а если сразу послать? Тут, конечно, стоит уметь оценивать вероятность того, что решение правильное → Ответить

ibra	13 лет назад, # ^ \| 0 в принципе ты прав, но если бы я слал без этого всего, было бы у меня не 300, а 330 и вместо +101 было бы +111 к рейтингу. Не большая разница → Ответить

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

Так какая правильная идея 1000?

→ Ответить

Egor	13 лет назад, # ^ \| 0 быстро перемножать "многочлены", где степени складываются ксором → Ответить

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

Всё-таки не перемножать, а возводить в степень. Если возводить в степень перемножением, то будет TL, я гарантирую это.

→ Ответить

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

Разве что Вы знаете способ перемножать такие многочлены за линейное время, в чём я всё-таки сомневаюсь.

→ Ответить

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

Можно ввести аналогию преобразования Фурье. И нужно будет один многочлен умножить на самого себя K раз, что значит сделать прямое преобразование, возвести в новом векторе каждый элемент в K-ую степень, и провести обратное преобразование, и вернуть нулевой элемент.

→ Ответить

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

Ну так это уже совсем другое дело - нужно не просто "быстро перемножать", а "придумать ФФТ для такой фигни".

→ Ответить

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

Я значит не совсем верно Вас понял, сорри

→ Ответить

subscriber

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

Говно или нет, это дело такое.. слишком уж зависящее от собственного результата.
Условия не были особенно не оригинальными, так что все были в одинаковых условиях. Каждая задача, для решения требует определенных качеств. Видимо сегодняшние требовали в основном смелости;)
На мое мнение также повлияли результаты, но, возможно, оно подбодрит недовольных людей, как подбадривает меня после лажовых выступлений^_^

→ Ответить

ibra	13 лет назад, # \| 0 куда катиться мир... Petr - на 762-ом месте → Ответить

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

Читаю обсуждения и не пойму: а что не так с 500, почему все его ругают? Написал относительно простое решение исходя из геометрических соображений (за n²), правда думал над ним слишком долго... А в таблице результатов какой-то треш творится =)

Первая несколько огорчила - надо было писать её быстро, а шумная университетская атмосфера и убогая клавиатура нетбука к этому не располагают. Зато условия простые и понятные =)

→ Ответить

agul	13 лет назад, # ^ \| 0 Здесь ругают 500-Div1 → Ответить

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

Именно про неё и говорю =)

→ Ответить

tunyash

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

Поделитесь идеей?

→ Ответить

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

← Rev. 2 →

Построим график, отложив на оси абсцисс номер числа в заданной последовательности, а на оси ординат - его значение. Согласно условию, необходимо добиться, чтобы график был выпукл вниз (если соединить точки отрезками). Проведём прямую через первые две (например a[0],a[1]) точки. Сравним положение остальных точек относительно этой прямой. Если какая-то оказалась ниже, то сдвигаем вторую (a[1]) точку вниз на необходимое число единиц. На следующей итерации сравниваем оставшиеся справа (a[3], ...) точки с прямой, проходящей через вторую (a[1]) и третью (a[2]) точки, и т.п. Получается чистый квадрат, если я правильно понимаю.

→ Ответить

vanchope

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

Упёрто не верил во время контеста, что 500 можно решить влоб. А решить "по-сложному" не смог. Клыки ещё маловаты. Ожидал задачки 250 и 500 посерьёзнее.

→ Ответить

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

В 500 надо минимум 3897 итераций (проверено экспериментальным путем).

Откуда это число берется - не имею понятия)

→ Ответить

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

возможно, это лишь максимум на тестах, а теоретический максимум другой.

→ Ответить

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

Авторы задач не предполагали возможности такого решения что ли?

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

Если не предполагали, то это не очень хорошие авторы.

→ Ответить

KADR

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

Я думаю, если бы предполагали, то такой задачи не было бы вообще. По крайней мере на месте 500-ки.

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

→ Ответить

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

Да нет. Может, это, типа, почти максимальный тест. А теоретический максимум, скажем, 3900 (хотя это было бы ничуть не более логично). Поскольку здесь вопрос лишь во времени, то плюс-минус 3 не так уж важно.

→ Ответить

dyussenaliyev

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

peter50216 опять на высоте =)

→ Ответить

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

Забавно было весь контест пытаться вспомнить как пишется симплекс метод, чтобы загнать некую чернь по 500. Зато с помощью этой черни можно доказать, что жадняк верен =)_

→ Ответить

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

Вопрос ко всем, кто писал жадняк - можно доказать его корректность и сходимость как-нить не через симплекс-метод?

→ Ответить

KADR

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

Ну очевидно, что если для каких-то трех последовательных условие выпуклости не выполняется, то средняя должна быть опущена ниже, т.к. если мы будем опускать другие 2, то выпуклым оно не станет. Следовательно, все что мы делаем в жадном методе форсировано и обязательно должно быть выполнено в оптимальном решении.

Почему сойдется? Например, потому что мы никогда ничего не опустим ниже, чем до уровня min(x_1, x_n).

→ Ответить