| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Собственно, только что закончился третий раунд SNWS 2014. Хотелось бы узнать 2 вещи:
1) Можно ли как-нибудь решить E без использования длинной арифметики?
2) Кто-нибудь может объяснить вот это? Всегда думал, что Java 7 x32 самая быстрая, а тут наоборот оказалось.
я Е сдал double-ами на С++
Странно, ведь третий тест, кажется, не самый большой.
Да, не самый большой. В остальных посылках самое большое время на 5 тесте.
Объясните мне, пожалуйста, вот это:
Какой тут 24-часовой период в примере? Во-первых, по моей арифметике разница между "инициированием" звонков в примере — 24 часа и 20 минут. Во-вторых, даже если считать, что мы учитываем время "на линии", а не только время начала звонка, то у меня получается, что первый звонок был с 6:00 до 6:19 (включительно), а второй начался через день в 6:20, то есть все равно получается получается больше чем 24-часовой интервал.
Я вижу, как тут можно подогнать понимание под пример, но как то же самое понять просто из условия я не понимаю.
Мои два понимания условия были точно такими же.
По-моему всё ок, если считать, что звонок начинается ровно в момент начала минуты и заканчивается в момент конца последней минуты, что есть момент начала новой минуты. Первый звонок закончился в конце 6:19, что есть начало 6:20, а второй начался в 6:20. Берём 24х часовой интервал и получаем, что у этого интервала есть пересечение с каждым из временных интервалов по одной точке.
А такое понимание получает AC?
Я не сдавал эту задачу. Только высказал вполне очевидную для моего понимания логику, которая вроде совпадает с условием. А есть сомнения?
PS. чуть позже попробую сдать.
В AС решении — ровно 1440 минут это еще ок. Если отнять от продолжительности промежутка времени между началом второго звонка и началом первого звонка продолжительность первого звонка, то полученное число должно быть <=1440 для того, чтобы ребро между пользователями было.
Да, получает. http://mirror.codeforces.com/contest/1/submission/5767046
Да, кстати, я соглашусь, что можно придраться к слову "инициировал". Но всё же в условии дан отличный пример, который полностью поясняет всё. Причём пример расписан в тексте условия, а не в тестах.
Я подчеркну:
Меня в основном вот это смущает. Пересечение у интервалов может и есть, но я бы не назвал это "инициированием" звонка.
Как решать F?
Динамикой по парам префиксов за |A|n^2. Я сам не стал это писать, но идея в том, что нужно для каждой буквы хранить все возможные пары совпадающих подпоследовательностей, умноженных на количество встреч данной буквы после них.
Пользуясь случаем, скажу, какие ужасные условия на SNWS 2014. Уже третий раунд ужасные условия. Если ты слышишь меня Олег, сделай что-нибудь, чтобы таких условий больше не было. Я потратил кучу времени, разглядывая самплы задачи A, чтобы хоть что-то понять. Тоже самое с задачей E. Каждый раунд такое. Читаешь задачу, вникаешь в условие минут 10, иногда даже самплы ничего не дают (как в задаче, кажется, Д раунда 2).
Я, конечно, наверняка, слишком субъективен. Но у меня желание писать SNWS пропадает от таких условий. Не удовольствие от задач, а недовольство от чтения условий только лишь одно. Ума не приложу, как другие участники понимают быстро, что просят в задаче. Надеюсь, этот комментарий хоть на что-нибудь повлияет.
Это видно невооруженным глазом. Я уже говорил о том, что кажется, что это делается специально, с целью усложнить контест...
Весьма странная причина, я предлагаю дождаться каких-нибудь комментариев Олега. Все-таки мой комментарий набрал уже +58, наверняка, это большая (ударение на А) доля участников SNWS.
У меня было предположение, что условия задач редактирует (или переводит, не знаю откуда там берутся задачи) какой-нибудь не очень опытный в олимпиадах участник. Возможно, это сам Олег, может кто-то другой. Должно же быть логичное объяснение, почему условия стали такие плохие. Я участвовал в прошлом году, вроде, даже в позапрошлом, возможно, я надумываю, но таких плохих условий как в этом году я не видел. Если мое предположение является правдой, я готов после раунда оставлять feedback тому человеку, который работает с условиями, чтобы они стали лучше. Это весьма не просто — написать понятное условие. Я хорошо это знаю, потому что часто редактирую условия авторов Codeforces, и не всегда у меня получается это удачно сделать, несмотря на то, что раундов уже приготовил больше сотни.
Ждем официальных комментариев. Кстати, кто-нибудь пробовал задавать вопросы в систему? Это работает? Я нажимал несколько раз на кнопку, чтобы посмотреть ответы на вопросы, которые уже задавали, но таковых не было. Значит, что все всё понимали и вопросов не задавали?
Я не вижу большой проблемы с условиями. На первом раунде была задача с двойным пониманием, всё остальное вроде однозначно и понятно (ну была ещё задача, которую нужно раза три прочитать, но в ней всё логично). По-моему в прошлых годах было больше проблем, были даже неправильные тесты или ещё в таком духе, когда принимались два решения.
Я писал вопросы в систему по поводу понимания условия. Но, к сожалению, это совсем бесполезно. На мой вопрос мне ответили через сутки.
В этом году перевод идёт более-менее дословный (то есть текст условия практически такой же, как и был в исходных задачах). Непонятные места закрываются дополнительными сэмплами или переделкой сэмплов. Никакого намеренного усложнения на уровне перевода нет — возможно, что это делалось авторами в исходных контестах (судя по их результатам, весьма правдоподобная версия).
Возможно, что раньше, действительно, готовые тексты задач несколько больше отстояли от оригинала — как минимум потому, что исходные условия были очень некачественными и приходилось по тестам и решению додумывать часть условия за автора. В этом году "вход" в целом поприличнее... но, как оказалось, всё же недостаточен для того, чтобы ограничиться "идентичным" переводом.
Feedback, естественно, приветствуется. Как минимум, будет понятно, за качеством условий из каких источников надо будет больше следить. Хотя вроде такое понимание уже есть и сейчас.
Что касается вопросов в систему: "broadcast" ответы бывают крайне редко, так как по итогам задания вопросов правка вносится в условие задачи (если правка требуется и ответ не No Comments) и для следующих участников вопрос и ответ критичными уже не являются.
Я сдал E на double в Java http://mirror.codeforces.com/contest/1/submission/5759793 (см. метод solve())
У меня вопрос, как сдавать нормально A? У меня получилось только пропихивать: сразу определяем можно ли достичь нужную сумму, потом на каждом шаге есть массив достижимых значений, добавляем в следующий шаг достижимые значения из предыдущей вершины, но не добавляем значения больше максимума, если максимум уже превысил необходимую сумму. По-моему, это решение не должно проходить при хороших тестах.
В А же просто рюкзак/32.
А как рюкзак? там же n=100 чисел, по v=4000 каждое, да ещё и t=100 тестов. Если я правильно понимаю, сложность порядка t*n*(n*v), что много.
Ну 100*100*4000*100/32 = чуть больше чем 10^8.
А что за /32?
Просто храним "достижимые" суммы в виде битсета. Обработать очередное число — сдвинуть текущие достижимые значения на это число и сделать OR с ними же.
Ааа. Прикольно :) Спасибо. Но всё равно, как-то неприятно сдавать задачу, у которой в лучшем случае сложность 10^8.
Ну там ТЛ вроде 4с, у меня на джаве это работало где-то 250мс.
Заходило и без поделить на 32, если что.
Код
Помогите, пожалуйста, по задаче D. У меня WA3, не понимаю почему. Написал бинпоиск с дейкстрой. вот код http://mirror.codeforces.com/contest/1/submission/5759867 (см. метод solve())
В твоем сете не может быть двух вершин с одинаковым расстоянием.
Спасибо!
А как надо было решать В? Моё решение за
получает TL.
Например так: http://mirror.codeforces.com/contest/1/submission/5767046 . 0.6s на java7. Просто будем хранить все звонки для каждых пар и потом для каждой пары находим .higher() — время ближайшего звонка в обратную сторону, делаем вывод.
Очень в стиле КФ — минусовать рабочий код в обсуждении задач после контеста.
Задачу B можно было и за квадрат решать — тупо перебираем для каждого, кому он звонил, и кто ему звонил. Почему-то тесты были подобраны таким образом, что это проходит.
Ещё в задаче C со второго раунда тоже квадрат проходил (при n<=1000000). Интересно, как у жюри получилось сделать такие тесты...
К сожалению, не нашел темы для пятого раунда, а новую создавать слишком поздно, поэтому задаю вопрос здесь. Как решать задачу B (Hypercube) с SNWS 2014 Round 5? (http://contest2.yandex.ru/contest/426/problems/B/) Заранее спасибо.
Для удобства считаем, что колонки бывают только 000, 001, 010, 100. В колонки первого типа можно ставить хоть что. Если в колонки остальных типов поставить x0, x1, x2 единиц, то получится 2 уравнения и 3 неизвестных, то есть через одну выражаются две другие. Перебираем её значение, перемножаем три цешки, все это складываем.