| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
Ну и собственно парочка вопосов от меня:
Правильно ли я понимаю, что:
Рануды на ТС редко на рейтинг влияют. А вот раунд этот — рейтинговый, до первой серьезной проблемы)
Разделения на дивизионы нету.
Задачи... С учетом того, что тут фактически отсутствуют топ-200 мира, а так же принимает участие второй дивизион — логично, что должны быть проще. В прошлом году была халва, в этом немного поменяли систему квал. раундов... Но первая квала вроде как была... И должна быть опять халва. Целая толпа решит все 3)
А этот раунд будет как обычный раунд(сколько он длится?)
Правила:
Можно же играть в любом из раундов 1A, 1B, 1C, они равноценные?
Да, можно участвовать до тех пор, пока не пройдешь или раунды не закончатся.
а если пройдешь в 1А, то можно участвовать в 1В?
Нет
сколько человек проходит?
600
а из раундов 2A(2B)?
Там, где узнали про их сущестование можно были и посмотреть:))
По 50 человек.
ТСО — это халявный рейтинг, главное не тупить)
Вначале надо просто быстро нарезать халву; а в следующих раундах — красиво нагибать красных ветеранов, которые уже далеко не красные) Но экспу за которых дают, как за красных.
Ах, вот в чем секрет успеха-то. Научишь не тупить?) Массивы маленькие не объявлять и int'ы не умножать тоже?)
Ок. Главное не тупить слишком сильно) Т.е. реально тут получить плюс намного проще, чем на обычных раундах.
В это я верю, но видимо одна мелкая бага тут стоит гораздо больше рейта, чем обычно тоже. Засчет толпы низких по рейтингу, у кого этой баги нет)
не тупить. Например не делать как я сегодня. вторая не прошла потому что написал 1<<(x) вместо 1LL<<x
Будет урок на будущее.
Мне хватило раз погореть на таком, чтобы начать юзать это через раз, и еще раз, чтобы потом писать ll везде, где у меня хоть какая-то переменная может быть хотя бы больше 20, пусть даже не та, на которую шифтую:)
Up to 350 Competitors with highest Ranks during Online Stage 2 (as defined above) Limited edition 2012 TopCoder Open t-shirt
так, а кто майки получает то?
за час до контеста написали? почему не за 20 минут? или чтобы вам подняли рейт, нет разницы во сколько писать?
Такое впечатление, что Вам весь мир что-то задолжал...
да нет, я к тому что человек просто по-видимому создал тему для поднятия себе рейтинга, а не для напоминания
Наверное, если тема создана не за 20 минут, а за час, то больше вероятность того, что те, кто собирался участвовать, но забыл про раунд, её увидят.
Вспомнил, зарегался, посмотрел — не написано — написал.
problems?
no problems!
как решалась вторая??
рано вы. еще челендж
через 15 минут узнаешь :)
понятно уже.
посмотрев код Станкевича, все сразу становится ясно.
Раунд не понравился.
3 халвы. Из них нормальная задача — только вторая. Потому что в ней думать надо, хотя бы минимально.
Первая — или думайте что-то умное, или... забил на придумывание, с учетом времени сдачи этой задачи другими (как всегда, начало пропускал, следя за монитором), понял, что там в 3 строки не получится. Ок. Пишем реализационную ерунду. Ну а что же, тут ведь серенькие да зелененькие, им нельзя умные задачи давать, не придумают, пускай с этой играются.
Ну ок, черт с ней, не умею я быстро писать много скучного кода, сдал кое-как, открыл вторую. Понял — Уррря, тут что-то алгоритмическое, наконец-то. Подумал, придумал, сдал. Если бы сразу думал не над тем, что после такой первой вторая не может быть хорошей, то было бы больше баллов.
Дальше третья. Вот за такую третью надо ломать руки и ноги. Даже я, человек, который в жизни ни разу не использовал тусат, и даже не знал до сегодня толком, как он работает, понял с условия, что надо мутить тусат. В результате 10 минут ушло на ознакомление с предметом, потом еще 15 минут пробовал честно кодить самостоятельно, потом забил и взялся сдирать... Содрать немного не успел:)
Какой смысл давать такую безидейную задачу на 1000? Пусть даже это первая квала ТСО, где надо дать что-то простое...
P.S. Да, я уже понял, что я тупой:)
Вроде без 2SAT можно решить
2SAT не будет работать, он не минимизирует ответ
А как решать нормально?
У меня, пока я знакомился с 2SAT, вообще возникло легкое подозрение, что в текущих условиях ответ всегда однозначный. Хотя теперь понимаю, что подозрение — это далеко не строгий факт.
попробую объяснить, у меня как-то сложно и запутанно.
сделаем записи такого вида для пар переключателей "x имеет такой же тип, как и y" или "x имеет противоположный тип, чем y". Это можно сделать, потому что степени лампочек не более чем 2. Тип — это нажмем мы переключатель или нет.
Далее разбиваем граф переключателей на компоненты связанности, каждую компоненту пытаемся сделать двудольной по отношению "x имеет противоположный тип, чем y".
Эти две доли проверяем на корректность, берем минимум из тех, кто корректный.
На каждом этапе — проверка, получилось ли сделать его. Например, если одна из компонент не двудольна, то ответ сразу - 1, если есть включенная лампочка, а переключателя для нее нет — тоже, и т.д. Много проверок...
Объяснил плохо, посмотри мой код.
P.S. Систестов не было, не знаю, пройдет или нет. Идейно вроде правильно
P.S.S. Прошло. FUCK YEAH.
Я думаю, что здесь просто система линейных уравнений по модулю 2. Не успел закодить...
Как минимальность проверять?
ем, не знаю :)
Приятного аппетита)
У меня получилась линейная с-ма по модулю 2, но не до конца уверен что это верно.
Надеюсь пройдет, разбиваем на компоненты связности, теперь выберем переключатель мы его нажмем либо нет, если с выбором определились то остальные переключатели в этой компоненте однозначно определяются. Поэтом в каждой компоненте берем минимум и суммируем.
Так в первой же есть решение и в 3 строки, хотя может оно не правильное, но я еще у многих кроме себя видел. Просто считаем сколько кто входит, потом если >= 2 то может быть победителем, иначе нет. Плюс частный случай когда всего один игрок.
меня как раз зачелленжили на этом случае... обидно
Ясно, что правильное.
Пусть хотя бы 2 раза встречается — первым выпьет обе половины — выиграл
Если 1 раз, то тот, кто пьет второй, если такой есть выпьет не меньше, чем мы.
Правильно я понимаю, что в 1000 meet-in-the-middle не зайдет? На раунде чуть-чуть не успел сдать, потом дописал — сэмплы проходит, правда у меня на компе под релизом работает 40 секунд, но на ТК компы помощнее, насколько я помню. Суть такая — перебираем 2^25 масок для первой половины выключателей, пихаем в map (отсюда логарифм, может рукописный hash_map уменьшит время работы в 25 раз и такое решение пройдет?), потом перебираем еще 2^25 масок — если получили mask, то ищем в map'е mask ^ init и обновляем ответ. В теории работает 2^25 * 25 ~= 8 * 10 ^ 8. Можно добавить hash_map и подсчет количества битов в числе за O(1).
Там если учесть что максимум по 2 выключателя, то достаточно перебирать 2^25.
Я совсем забыл про это условие и сейчас, честно говоря, не понимаю, как его использовать.
посмотри мое решение выше
Серенький парень в моей руме сдал первую задачу с результатом 249.36, лучший результат по первой задаче среди всех. Наводит на мысль...
Как решается третья?
Правда, что можно решать рекурсивно для пары текущее число, текущий бит, и выбирать не более 2хвариантов каждый раз, при этом запоминая естественно(что я не успел дописать). Что-то не могу сообразить, как это оценить
Да так можно делать, там выйдет не более 2^25.
И правда зашло, обидно, что так тупил и не успел(
Если я прошел в этом раунде, то дальше я квалы писать не смогу (вне конкурса)?
В прошлом году так было, и до этого, кажется, тоже. В этом, помню, прочел о каком-то соревновании, что одновременно с раундами будут матчи для тех, кто не прошел в этот раунд... Но у меня стойкое ощущение, что я попутал с VK Cup.
Хорошо хоть структуру второго раунда поменяли, с первого раза я вряд ли квалифайнусь, так что получу несколько дополнительных рейтед-ивентов)
Да, путаешь с VKCup или чем-то еще.
Правильно прочел, но это начиная со второго раунда (то есть будут параллельные раунды на основе 2B, 2C и 3B для прошедших)