Добрый вечер, друзья!
За обсуждением животрепещущей темы использования чужого кода в своих решениях можно и не заметить, что приближается зима 188 раунд платформы Codeforces!
А ведь мы постарались подготовить для вас набор задач с любопытными (и, как нам хочется думать, не сильно сложными) идеями и понятными условиями.
Мы — это авторы задач yaro и Rei, куратор раундов Codeforces Gerald и автор системы MikeMirzayanov. Отдельное спасибо Паше (PavelKunyavskiy) и Артему (RAD) за тестирование и дельные замечания.
Последний раз, когда я участвовал в проведении соревнования на Codeforces, раунды еще носили статус "beta". Но чем меньше "beta", тем больше ответственность. В связи с этим желаю организаторам и авторам еще одного успешно проведенного раунда. Участникам же — нестандартных задач и идей, чистого кода (а также чистой клавиатуры) и побольше правильно сданных решений!
Нам представляется непростой задачей оценить уровень сложности задач для всей массы участников, поэтому разбалловка будет динамическая. Все же ради любопытства сделаем следующее предположение об относительной сложности задач: div.1: B-B-C-C-E, div.2: A-B-C-C-E. Угадаем ли?
UPD Приносим извинения за проблемы с очередью тестирования Codeforces.
В любом случае, нам будет очень приятно, если вы оцените наш раунд (после его завершения): short survey.
В упорной борьбе с отрывом в один взлом победителем div.1 стал meret (Jakub Pachocki)!
Доступны результаты первого дивизиона, результаты второго дивизиона.
Не пойму С див2 оценили как Б див1?
Правда ли, что div2 CDE = div1 ABC?
Правда.
=> Это будет сложный Div2 или простой Div1 ? (речь про C=B)
Скорее всего имелось ввиду, что во втором диве задача будет стоить 1500, а в первом диве — 1000
Будет динамическая разбалловка.
Я хотел сказать, что после конца контеста стоимость задачи, по предположению авторов, окажется 1000/1500, а не, например, 2000/3000
Давно не могу понять, почему одинаковые задачи не назвать одинаковой буквой, а разные — разными? Часто сталкиваюсь с неудобствами по этому поводу. Думаю многие меня понимают.
Авторы, расскажите о себе, чем занимаетесь/увлекаетесь. Я уверен, что вам есть что рассказать, а людям, думаю, будет интересно.
Вообще было бы неплохой традицией в анонсе контеста вкратце рассказывать, кто автора, откуда, и чем занимаются.
Макс, так я к этому и клоню)
Seeing your bet on difficulty levels, Just one question: Are the last 3 questions of div2 not gonna be the same as first 3 questions of div 1..??
Yes, they are.
what is d diff b/w div 1 & div 2? i am a beginner and this is my first contest. what should i opt for- div 1 or 2? plz reply asap
Div 2 for new-comers
it seems like div 2 will be A-B-**D**-**D**-E !!!!
D1 500 = D2 1500, D1 1000 = D2 2000, D1 1500 = D2 2500
This tradition is also a bit strange. The ratios of points are different.
Are you sure that ratios of point must be equals to ratios of difficulties? It isn't clearly.
Exactly!
maybe there will be GAME OF THRONES effect on the problem statement.. :)
'We have to save Robb! He needs your help, but for this you have to find the number of .... to identify the traitor. Please, hurry up!' For example
Since you said for div 2 it's A-B-C-C-E, I guess you meant that it's A-A-C-C-E for div 1?
Or is it A-B-D-D-E for div 2??
C'mon everyone, don't be so peaky :) He only said that the 3th and 4th problem are of similar difficulty.
I hope that this round will be easier because according to the announcement, it seems that this round is going to be difficult. Thanks !
Haaa, Game of Thrones! "Growing Strong" & "As High As Honor"!
Хотелось бы что бы в раунде нужно было меньше кодить, а дольше думать над самой идеей.
contest is prepared by a lot of people thank you all but I hope it will not be like chinese contest
Contest is prepared by 2 person — yaro and Rei. I just wrote extra solutions for more checking.
Thanks yaro and also Rei for the contest!
if it is easy for you, it will also be easy for other people :D
Than the competition becomes a speed competition :D
I participated in two such contests(but it was not simple(AB — very simple and CDE or DE — difficult(solved by 5-30 users)
1) Codeforces Round 163 (Div. 2) (there were 2 very simple problems, third was solved by 80 users, and two last weren't solved) — it's really speed competition
2) Untitled contest
I had a similar experience, where just one unsuccessful hack brought me from position 200 to position 1300 XD
And my schoolmate did one successful hack and comes to position 400 from position 900(but his own solution crashed on final tests)
what is d diff b/w div 1 & div 2? i am a beginner and this is my first contest. what should i opt for- div 1 or 2? plz reply asap.
Div 2
trying opting for div1 !! (only if you could !)
I am very ill but I am take part in this contest
it's so exсiting
Перенесите раунд на 5 минут, мне мама пирожки с вишнями только принесла^^
Так задачи с пирожками вкуснее)
Задачи вкуснее с попкорном!
Вы двое едите задачи? Извращенцы. Решать их надо.
adamant, они вкусные, ты просто не умеешь их готовить.
Очередь уже в 14 страниц, что же будет дальше?
Мда, прождал 15 минут ради того, чтобы получить по А ВА. А все вовсю ломают, обидно
judgement is going very slowly... please check
What the hell is that?! 15 minutes to get a response for the submission?!!!
in queue for more than 10 minutes in Div2 B. judging sucks. :(
still in queue.
что с очередью тестирования ??
very slow judgement, this is becoming very annoying
deleted
ах если бы
Не могу взломать никого. Взлом в очереди минут 10, за это время все всех ломают. Полностью.
Пока меня ломали успел пофиксить и отослать исправленное.
Queued :(
Yeah, I think is time to upgrade those Pentium II they have, don't you think? In TopCoder this never happens, just saying...
Watch out, people are very sensitive here... My "Queued" comment presses some buttons that the other complaints don't
In topcoder problems there are not super large constraints, so the system test is evaluated quickly... Just saying.
We are talking about the pretests here, which are known for their lack of "super large constraints", whose time-limit is 2s anyway. So, please.
In fact, some pretests can have 'super large constraints' :) I don't know if this contest have it, but well... Have fun and keep coding.
There's no judge results right after the submission. How would it possible to get queue? (Solutions aren't testing on samples)
How is my solution hacked even when i ddnt lock it ??
when you didn't lock your solution it can be hacked but you can resubmit another solution again, but when you lock it, you can't resubmit another solution.
Хотелось бы иметь возможность видеть, что уже есть попытка взлома этого решения в очереди. Все-таки неприятно искать багу и узнать, что ты не первый через 10 минут.
И да, видеть стектрейс в случае весьма странно, хотелось бы человеческого сообщения, причем на языке интерфейса и не абстрактное "данная посылка не последняя", а реальную причину — посылка уже взломана.
После слитого к чертям ABBYY Cup написать этот контест было особенно приятно. Спасибо авторам, особенно за C/D. D — довольно классическая задача на "разобрать по полочкам и понять, что происходит".
C — вообще красота. Сначала долго думал, что там поток, потом придумалось красивое вроде бы верное решение с сведением к дереву.
Правда ведь, что в C авторское решение — это построить произвольный остовный лес и удовлетворять требования листьев по одному?
А по какому все-таки принципу удовлетворять требования листьев? К примеру такая ситуация: чтобы удовлетворить текущий лист, то надо протолкнуть воду из другого какого-то листа. Как это надо обходить?
Ну вроде бы понятно, что всегда можно, если суммы совпадают. Удалим лист, если в нем больше чем нужно — выльем в соседа, если меньше, чем нужно, то сперва решим, как будто бы в соседа нужно чуть больше житкости, и перельем в лист. Но возникает проблема, что можно случайно превысить v и как с этим адекватно бороться — не ясно.
Вот все решение, вроде бы умею доказывать.
Возьмем компоненту, подвесим ее за какой-нибудь лист. Пусть в этом листе избыток (если недостаток, то действуем аналогично). Рассмотрим все ребра в компоненте и направим их от данного листа в порядке обхода. После этого рассмотрим их в порядке топсорта (то есть в порядке выхода из ДФСа, запущенного из листа). После этого в таком порядке по каждому из этих ребер нужно протолкнуть максимум, сколько возможно. Утверждается, что тогда если решение существует, то из зафиксированного листа все, что можно, мы выльем. Итого не более чем N-1 итераций по N-1 переливанию.
В Div2 D можно было посчитать муравьев на одной прямой(т.е. сколько муравьев на расстоянии от 0.0 ) а на запросы отвечать посчитав расстояние и выведя заранее подсчитанный результат? Заранее спасибо
Почему на прямой? Они же еще вбок лезут. А вообще задача в лоб решается. Что написано, то и реализуем. Только на матрице, т.е. сдвигаем (0,0) в точку (100,100). Почему так? Потому что тогда хватит, проверил на макс-тесте. Еще есть оптимизация: оставить в (0,0), но считать только для одной четверти. Геморнее, но быстрее.
Спасибо такая мысль была но как написать не оставалось время думать.
я думал посчитать например для ох, а дальше для точек х у считать х+у и ,и выдавать ответ на который посчитали для такого же расстояния, но сейчас понял что это не совсем так
для начального n<=30000 достаточно поля пол -log4(n).. потолок log4(n) на столько же
т.е доски 10 на 10 вроде как достаточно
засада чуть чуть в другом — в условиях зачемто подчёркнуто что уменьшается не на все группы по 4 ,а на одну группу за такт .- можно конечно понять что безразницы и быстрее все возможные двигать и не отличать когда муравьи пришли на этом или на прошлом такте — а если зачемто задатся целью точно моделировать то очевидно tle — даже если оптимизировать со сворачиванием ( а оно кстати и не возможно при точном моделировании ибо при точном в клетках всё таки другие значение )
:(
10 на 10 недостаточно, на макстесте получается что-то около 64.
я чутка опечатался вроде как
расуждаем так
если в центре в начале 4**n то в конце самые дальнии единицы будут на манхетеновой длине n от центра
ну что бы с осями не заморачиватся пусть у нашего массива оси как обычно ориентированны тогда размер достаточного поля это -8... +8 на -8..+8 ( это если в центре 4в 8 муравьёв в начале) т.е поля 16x16 вполне достаточно.
И все же мое решение, которое получает АС, утверждает, что при n = 30000 амплитуда достигает 128. А откуда берется рассуждение
если в центре в начале 4**n то в конце самые дальнии единицы будут на манхетеновой длине n от центра,
мне совсем не понятно.
1 конец 1 4 квадратик с 1 16 квадратик 121 64 ... ага сори излишни рано индуктивно подумал.
но ...
хм надо подумать
Простое моделирование по времени заходило, если пересчитывать только те клетки, для которых на предыдущем шаге было что-то изменено. Моя реализация на Паскале работала 1.9 сек (спасибо автору за ТЛ!!!) и мне пришлось все считать лишь для одной четверти, поскольку ответ симметричен относительно начала координат.
Это с перекидыванием сразу всех четверок из точки?
Нет, все делал тупо. ТЛ мне не понравился тем, что такая же реализация на С++ скорее всего заходит без гемора с одной четвертью.
Это что, я считал для восьмушки, казалось, что не заходит. C#
Казалось? То есть ты не пробовал запуск?
У меня прошло самое простое моделирование, с пересчётом всех клеток, но только с оптимизацией в 8 раз. 1000 мс ровно)
Как решать B(div 1)? BFS с небольшой оптимизацией? Если так, то я думал будет TL.
Симулируем проходя по всему полю, пока изменяется. Утверджается, что координаты по модулю будут н ебольше 100
Ясно...я думал там решение связанное с вычислением заданного кол-ва муравьев и координаты запроса.
Правда, в B не подразумевалась симуляция? Я как-то умудрился впихнуть её в 800 мс на претестах, и судя по запуску на сервере на макс. тесте, претесты его включают.
У меня за <= 300 в запуске работает симуляция, в которой если мы можем сразу выпустить из клетки несколько четверок, мы это делаем за один раз. Порядок, в котором мы делаем ходы, значения не имеет.
ОК, спасибо, жаль. Я надеялся что там какое-то красивое решение из теории чисел.
А почему не имеет значения порядок?
Я не знаю, я проверил на разных тестах — оно заработало. Хотя идея может быть такая: если в клетке когда-то окажется четверка, то она оттуда уйдет, и нам не важно, в какой именно момент она оттуда уйдет — раньше или позже. Но формализовывать я это не умею.
The judegement is very slow. Hope the system test will be finished as soon as possible.
А в D есть решения без прекалька?
OEIS во всяком случае ничего не находит. Если я правильно нагенерил последовательность.
3889680
Не верю.
Неправильный ответ на тесте 27 =)
Упало с неправильным ответом :)
Wow, so many hacks for Div2 Problem C. I guess some coders overlooked the constraints for input data. Anyway, at least it was interesting trying to hack others. Oh and it seems to me that the writers have managed to make a nearly-perfect A-B-C-D-E problem set for DIV2, at least according to number of solvers before sys-test...
For Div2 Problem C.
Maybe some case like this:
-1000000000000000000 1 2my hacking test for problem C Div 2: -1000000000000000000 1 1000000000000000000
how cruel the C of div.2 is.
i guess one of reason that the pretest is a bit slow is because many TLE codes for C div 2 :)
thanks yaro and Rei for the contest! :) next time try to make the system testing a bit faster!
how cruel the C in div.2 is! -10^18 1 10^18 is a strong test data.^_^.
Реквестирую алерт о проверке посылки. Прождал минут 20 с тупым багом.
div1 B тестировать будут еще очень долго))))
Survey for the contest....what a democracy..!
Хороший контест.
Sad sad sad :-(|) ...
system testing has also been too slow!!! what is the reason?
I guess because of the amount of TLEs in DIV2 C and DIV1 A
All TLEs solutions in A div 1 (C div 2) were hacked, I think. And slow speed of system testing is because slow B div 1 (D div 2) solutions.
Oh,It my best rank until now.
По видимому сегодня будут явные изменения в рейтинге
Status of submission 3895303 is still "Running on pretest 8", why?
Because that code is Forrest Gump ..... "Run Forrest Run " ...... :) :
my submission 3887964 for Div-2 B failed on the last test case! :(
oh damn, i forgot to update the volume of vessels...
I don't understand why i was got RTE in div-2 B. I just assign the size of sting s to n and it gets AC. AC link http://codeforces.me/contest/318/submission/3895790 RTE link http://codeforces.me/contest/318/submission/3888165 Can any one explain it?Thanks in advance.
same thing happening to me too...but i got MLE instead of RTE..
RTE: 3887964, AC: 3895821
But i want to know what's the problem with "i<s.size()-4" instead of "i<n-4" where n=s.size().
s.size() returns an UNSIGNED integer, so if s.size() is less than 4
This statement ( s.size() — 4) won't be a negative number! It will be a really big positive number and the loop won't end and it will try to access out of bounds places in the array
You need to cast s.size() to (int), signed int in order to avoid this..
You can print the value of s.size()-4 when s has size less than 4 and see the output yourself.
I had the same problem, and I got the answer.
thank you guys for asking and answering the question.
s.size()is unsigned, so whens.size() < 4,s.size() - 4would be a large unsigned integer, and you'll get RTE.Edit: That's why some people (including me) has a predefined macro
#define SZ(x) (int)x.size():DThank's peter50216. Now i have my answer.
Happened with me as well. I should never have ignored those compiler warnings.
the worst thing about codeforces is that the main testing takes place after the contest ,
if it would have told that my solution is wrong after running the test cases during the contest ,i would have corrected my solution this thing needs to be changes,i m not sure even after passing pre test cases whether my solution will increase or not
that's why it's called 'pre'-test
Waiting
Contest ratingupdate.I think it's A-B-B-D-E for Div 2
And it seems like A-B-E-C-F for Div 1 .^_^.
what do you mean by F ? F...K ?
I mean it's harder than E...it has 3000 point
Я просто тащусь от системы СF.
Мое решение В — одно из двух, которые упали с TL36.
Я отправляю его в практис — система, как я понял, для экономии времени просто содрала вердикт с сабмита на контесте — ТЛ на том же 36 тексте, который появился моментально; вердикты по времени на остальных тестах вроде бы совпадают (пересмотрел где-то половину).
После этого я делаю 8 подряд сабмитов своего сорса, добавляя только пробелы, из них 7 подряд — под тем же компилятором. Все 8 укладываются, при этом ни у одного из них нету АС 1.000, все хотя бы на 1 тик быстрее.
После этого я беру решение naagi, которое тоже получило странный TL36 и было отправлено с интервалом 34 секунды относительно моего. Отправляю его в практис — оно тоже проходит с запасом.
Вообще возникает естественное желание реквестировать реджадж сабмитов, которые получили тл36) Да и вообще — сабмитов, у которых ТЛ30+.
Ну я, честно говоря, ни на что не расчитывала, учитывая 951мс на претестах и 891 в запуске на макстесте без чтения и вывода. На тестировании оно бывает чуть медленнее, это и раньше так было. Я тоже видела ваше решение с тем же вердиктом, когда оно тестировалось, и гадала, у кого раньше упадет. Упало почти одновременно :)
Но если что я не против реджаджа :)
D (Div. 1) was very similar to TCO 2A Hard. I was able to copy & paste 1/3 of the code.
Is div-2 C can be solved by Extended Euclid?
Div-2 C is simple brute force, but you need to take care of the corner cases where the answer is 0 or -1 or when one of x and y is negative.
It's not a 'simple brute force'. Consider the Test Case -1000000000000000000 1 1000000000000000000. With a pure brute force this TC would definitely give TLE. The trick is to consider the case, when one of the numbers is <0 and the other one >0. And only then you can do brute force. Edit: oh, sorry, I missed the last part of your comment JuanMata
Can any one tell me about SergeiFedorov's solution for Problem E? ... My solution get TLE when Princess && Shadow are within a same block....
Well, I could ))
Idea: if we could reach point outside of the forest, than do it with both points. Then find two nearest trees on the border (one by x coordinate and one by y coordinate) and win :)
If we stand inside the forest and could not get out of it, then just go to the position where shadow stands. Then again to the new shadow position and so on, until we reach it. Of course one should check that they lie in the same component.
I use simple dfs to move from one point to another while inside forest. And greedy one to move to the border trees while points lie outside.
... Wow, this is better ... I have learnd a lesson ... .. Thanks ~~
Контест-бомба! Спасибо авторам, надеюсь вы будете давать контесты чаще :)
For all those who solved problem D, where do you get the array?
One way to get it is to precompute it. I left the code I used in my solution: 3891054.
Or precompute it like this: 3896247 (only compute the masks you actually need instead of all; runs 5 secs on my computer).
Как понимать взлом игнорирован, в протоколе:
Похоже, что человек, которого хочешь взломать, перепослал решение.
challenged submit is not the last accepted nowЭто может значить, что участник перепослал решение, или что его кто-то взломал раньше, чем дошла очередь до проверки этого взлома, или что-нибудь более редкое. Что именно произошло, можно узнать в логе этого участника.
Действительно, не очень понятно и не очень удобно.
Interesting round! Can't wait to see editorial for Balance.
link
when is the next round comming?
any hint about Div1 D ?
There is always an option to find our analysis. It's not that hard (I know at least three ways to find it)...