Привет всем!
Я автор задач сегодняшнего раунда. Раунд будет проходить сразу в двух дивизионах. Всего будет 7 задач, первые 5 из которых будут для второго дивизиона, а последние 5 - для первого.
О разбалловке. Сегодня она будет не совсем стандартная, а именно:
для див2: 500-1000-1500-2000-2000
для див1: 500-1000-1000-1500-2500
Так что будьте внимательны.
Раунд помогал готовить RAD. На английский язык задачи перевела Delinur.
Всем удачи и приятного времяпровождения.
победители в первом дивизионе
1. peter50216
2. tourist
3. ACRush
победители во втором дивизионе
1. iamcs1983
2. zyx3d
3. seanwupi
Разбор задач.
UPD.
К сожалению, в авторском решении задачи E этого раунда была обнаружена ошибка. Спасибо участнику LinesPrower за ее обнаружение. Авторское решение было обновлено, а все решения перепроверены. Вскоре будут обновлены рейтинги всех участников, кроме Egor и Jacob. Мы приносим извинения за данный инцидент.
http://codeforces.me/blog/entry/2144#comment-43294
Что еще надо? :)
Very Nice : Surely will have a good contest :D
P.S. У меня из-за этого 2 взлома увели, и я так один взлом сделал.
А я всегда раньше как только меня ломали, честно переставал ломать :(
Scorpy
01:30:24 Решение взломано участником Nadezhda
01:30:47 Успешный взлом участника rogerfgm
01:29:07 Успешный взлом участника 19910517
01:59:24 Успешный взлом участника yuri.pechatnov
?
Или себя тоже считаешь? :-)
. This is really helpful ..
PS: .. The version of the Ruby compiler isn't clearly ...
... .. which induce me lots of CE && RE submissions more than once ..
Maybe the version is 1.9.0 or higher .. cause the String::[] is return a char ...
... And one more suggestion ... there should be one more language option named .. "Auto" .. ;)
.. literal meaning .. auto-distinguish the language according to your suffix name ...
..simply "cpp" stands for GNU CPP .. "pas" stands for "Free Pascall / Delphi "...
which could also be some user-preset perhaps ..
(о, вот куда ушел этот коммент! а я думал, где он?)
Тогда беру свои слова обратно)
Вообще, рассуждения в стиле "Что было бы, если бы" лично я недолюбливаю, потому-что в них, ИМХО, маловато достоверности.
поэтому чуть подробнее:
для каждой вершины в начале посчитать ее ближайших непустых соседей с каждой стороны, делается в лоб.
каждая непустая (не "." и не вычеркнутая ранее) клетка, таким образом, участвует ровно в двух двусвязных списках - по своей горизонтали и по своей вертикали.
удаление из двусвязного списка, как и получение следующего элемента, как известно, можно делать за O(1).
только надо не забывать восстанавливать попорченные списки на каждой итерации (я перестраховался и сохранял копию массива, но можно даже в лоб их заново пересчитывать).
Я куда-то выкинул полчаса контеста... =(
А задачи клёвые =)
А еще я зачем-то запустил свой генератор теста, и у меня повис комп - после перезагрузки 2 взлома уплыли :(
At the first time i read the statement , I thought n,m<=5000 ,so i have to look for a O(N*M) solution and It 's really hard to solve , why so many people accepted ? I can only solve it in O((N*M)^2) . It takes me 50 minutes to notice that n*m<=5000 , it's 1:53:00 , too late . My rating continues to decreases :( . this is the fourth consecutive time
не поверите
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
return 0;
} так тоже можно)
I tried to see the input used to hack my problem A viewing my code
at "my submissions" and by double-clicking the score/points of problem A
at the "room" area. But in both cases I just saw the pretest cases, it didn't
show the hack input.
Thanks.
i think for increase speed of process!
Но задачки достаточно интересные были, спасибо автору!
Хотя, я так понимаю, у меня не самое простое решение...
I hope the UI of current hack window will be improved.
Link.http://www.ideone.com/BcunL.
Edit: During the contest my submission ids were:
492767
492737
492505
492349
492236
492131
492074
492035
After contest:
494437
494398
494274
494260
494238
494173
494293
You need System.out.flush() in the end
ouups, nevermind, you have closeSystem.out.println(res.toString())But did it work under your system? I have been using my template for a while now and never had problems.
Submitting it many times and getting a wrong answer on Pretest 1 is a bit frustrating. Could you post your observations on what could have gone wrong.
.
My template is similar to Egor's. I will go through it.
Edit: Oops, I meant whether my solution ran in your system.
Where was this mentioned ?
http://en.webhex.net/view/c8002611d83e594863797cee7fc5e3c6
After carefully going through Egor's Template, I corrected 2 bugs, both related to reading empty lines.
C\DIV 2.
can anybody explain me why the answer is 0 for the test case like this
5 2 9494412
5484 254 1838 18184 9421
Why does he need to do at least 3 operations? Why can't he move one diamond from 5484 to 254, and then take one from the 1838 for a total of 2 operations and resulting in 5483 255 1837
Nevermind, that would change the sums on the later parts of the array. Sorry for the confusion.Sum 1838+18184 will differ from 1837+18184.
Хороший раунд, жаль не получилось с результатом. В В забыл помечать просчитанные виджеты в рекурсии, в С написал массивы вместо векторов (естественно падало по памяти). На дорешивании обе добил.
З.Ы. Задача С падает под Visual Studio по времени, на гну - полное решение =) Решал через что-то похожее на систему непересекающихся множеств.
(edit: I can't use this editor correctly...)
During the contest I used a O((R*C)^2 log (R*C)) algorithm for problem C which I thought that would work but surprisingly it got TLE. when I debugged my code after the contest, I found out that copying the "map"s takes too much time...
Chip Play For every point, starting from it dfs a time to find the length ,whether the complexity is O ((n * m ^ 2)?
1 5000
RR..R(2500)LL..L(2500)
for this test case, the complexity is O(n3).
you can use linked-list for AC , for each cell which has chip, consider four pointer.
How long can it continue? Of course, min(all(a[i])) where i is even
Consider: a[0], a[1], a[2] ... a[n-1].
Sums are (a[0]+a[1]), (a[1]+a[2]), ... , (a[n-2]+a[n-1]).
(n-1) sums mustn't change, and their sum mustn't, either.
We can see that a[0] and a[n-1] are counted once, while the others are counted twice. Therefore, if Joe want to get 1 more diamond, he will move 1 diamond from a[0] (or a[n-1]) to the middle, so it will be counted once more, and move 1 diamond from a[n-1] (or a[0]) to his pocket.
This is how Joe should move diamonds:
Move 1 diamond from a[0] to a[1] -> (a[0]+a[1]) won't change, but (a[1]+a[2]) will increase by 1. So Joe doesn't need to move from a[1], but a[2] to a[3]. And so on ...
0->1 , 2->3 , 4->5, ... , (n-1) -> Joe's pocket.
Joe can get more diamonds unless 1 number in a[0],a[2],a[4],...,a[n-1] = 0.
Could you make the system to where when I get AC the number of problems I solved in the problemset increase by 1 regardless of where I solve it?
К сожалению, в авторском решении задачи E этого раунда была обнаружена ошибка. Спасибо участнику LinesPrower за ее обнаружение. Авторское решение было обновлено, а все решения перепроверены. Вскоре будут обновлены рейтинги всех участников, кроме Egor и Jacob. Мы приносим извинения за данный инцидент.
Непонятно, почему кроме Egor и Jacob.
================================================================
Конечно, я плююсь от ярости, что у меня было 7-ое, а не 5-ое место, это же так ужасно! =))) Более того, если бы Вы были повнимательнее, а не советовали бы мне решать задачи, Вы бы, возможно, заметили, что как раз-таки теперь они меня на два места не опускают. Это к сведению.
Теперь по существу. Я ни капли не сомневаюсь в мастерстве Егора и Jacob'a, и мне совсем не жалко, чтобы им добавили хоть по сотне рейтинга, за дело, разумеется. Я не злорадный и не ставлю себе цель получить побольше рейтинга, а всем остальным чтобы досталось поменьше. Но мне кажется, что пересчитать рейтинг справедливо всем, в том числе и этим двум участникам -- просто потому, что неправильное авторское решение никак не влияло на ход контеста для них. В чём я не прав?
> В чем не правы? Ну хотя бы в заминусовывании комментариев.
А может ещё в написании, нет? Или в присутствии на codeforces?
> Ну а если серьезно, то "закон обратной силы не имеет".
А почему тогда остальным пересчитывать? Двойные стандарты?
> Кстати, а почему бы тогда на ACM-style контесте не отбирать очко?
Выше уже ответили: потому что это влияет на ход контеста. Человек/команда сдаёт задачу, видит АС, перестаёт над ней работать. Потом забрать это очко несправедливо. Здесь разницы никакой нет, Егор и Jacob всё равно не знали о своём "ложном" АС до конца соревнования.
Хром обо мне настолько низкого мнения? =)))))
Да, мы принимали решение исключительно из этих соображений.
Странные рассуждения. Если бы это был какой-то онсайт с медалями и грандиозным шоу, то я согласен. А поскольку это локальный контест, один из сотни, то я думаю, вполне справедливо либо вообще ничего не делать, либо всем всё пересчитать.
А как же бан читеров? После соревнований же смотрят исходники на похожесть и т.п. В этом случае результаты вполне себе меняются. Так вот интересно, какая разница, там люди получили очки несправедливо из-за своей подлости, а здесь из-за ошибки жюри, но тоже несправедливо.
Ещё — не снимать плюсы можно ещё и по человеческим, а не формальным причинам. Эти причины я тоже считаю важными.
С этим ясно. Но, раз уж речь зашла, я слышал когда-то давно, что если ты после раунда находишь корректный тест, который валит некоторые passed решения, то тебе просто навешивают +50 рейтинга. Может кто-нибудь из знающих как-нибудь прокомментировать?
Of course, this peter is awesome too... He reminds me of what Petr did in TC when he first entered the website years ago.
GL, HR & HF Everyone!
sorry: he didn't actually won, i should have checked before posting..
Edit: http://www.topcoder.com/tc?module=MemberProfile&cr=22929522 Thats his handle,participated in only one srm.