| CodeFest'11 — это ежегодный фестиваль программирования, проводимый Computer Engineering Society IT-BHU. В рамках фестиваля состоится Manthan 2011 - соревнование по алгоритмическому программированию. Название Manthan or मंथन было взято из языка the Хинди и обозначает мозговой штурм. |   |
Вы должны зарегистрироваться на официальном сайте мероприятия, принимать участие в розыгрыше призов.
Детали:
- Соревнование состоится 13 марта, 19:30 (московское время)
- Правила схожи с правилами Codeforces раундов.
- Продолжительность составит 3 часа, раунд будет содержать 5-6 задач.
- Разрешено писать решения на: C, C++ , Pascal, Java, C#, Python, Ruby, PHP, F# и/или Haskell.
- Мероприятие открыто как для учащихся (школьников, студентов), так и для окончивших обучение.
- Объявление результатов состоится 16 марта.
Регистрация на соревнование будет происходить автоматически по факту вашей регистрации на официальном сайте CodeFest. Если вы правильно прошли там регистрацию, то ваш Codeforces хэндл должен появиться в списке http://codefest.org.in/codeforces-handles.php, а регистрация на контест произойдет автоматически.
Продолжительность контеста уменьшена с 4-х до 3-х часов. Желаем всем удачи на предстоящем соревновании.
In case you are registered on codeforces with the same email address as that on codefest, it will automatically register you for manthan with your codeforces handle.
If you are not registered with this email address on codeforces, it will open up a form asking for your new user-handle and password for codeforces, and will register you on codeforces as well as for manthan.
Т. е. если я здесь поменяю email всё точняк должно связаться?
[English Post]
[Russian Translation]
A Google translation is difficult for understanding :\.
Там один из организаторов отвечал.
Не исключено, впрочем, что это относилось не к Manthan'у.
Besides, if you are still facing any issue in registering for the event, please let us know in English or email to [email protected]
1)For the registration form that pops up on clicking 'Register for Manthan', provide a new codeforces handle and new password.
2) Re-register on codefest website using the same email id as in codeforces. Then when you login and click on 'Register for Manthan' no extra form pops up.
What are the differences between the rules?
- There will be 40 participants in each room.
- Distribution in rooms will be done randomly
- Difference in number of problems
More detailed rules are here: http://codefest.org.in/event.php?name=manthan#rulesРезультат -
Cайт превышает предел нагрузки на процессор
приобретенного тарифного плана хостинга.
Подозреваю, что из-за СФ)
Спасибо за задачи!
Интересно было решать, особенно взламывать =)
Видел у одного паренька в комнате копипасту с e-maxx.ru
Надеюсь, что не ошибся, и мои B и D пройдут...
Тесты:
10
RRRRLRRRR
и
10
LLLLRLLLL
там вроде несложное дп, жаль только то у меня в одном символе в преподсчете ошибка(
очень похожая задача уже была на кф: http://codeforces.me/problemset/problem/56/D
там вовсе незачем DPHope sooner or later problem writers will realize that this is not cool.
Some people earned 3000 points by hacking problem A. It is more than average person could achieve by solving C and D together. I don't know what it proves.
This is one on which I failed, and then I saw several people doing the same mistake.
My bad. I meant RRRRRL
You can see on which test your solution failed. Click on the submission ID on the status page.
Please do provide us your feedback!
Problems themselves are very good overall. I pretty much enjoyed solving all of them.
Возьмём первый пример k=2, B={1,2,1,0,0}
В массиве А перед единичкой должно стоять ровно одно число которе больше или равно 1+2=3, т.е. подходит либо 3, либо 4, либо 5. Какое именно ребро вы добавляете в граф?
P.S. Я решал жадным методом (как уже где-то было описано), и оно прошло, хотя я не доказывал верность такого решения.
Решение за O(n2), довольно очевидна его корректность.
В итоге написал такое решение за квадрат:
Вначале поставим в массив числа 1,2,3,....n.
Потом перебираем по убыванию, и на каждом шаге найдем, сколько чисел слева от данного должно быть (need) и сколько есть (have). Потом текущее число гоним влево или вправо, пока need != have.
По мне, C - самая тяжёлая и мерзкая задача.
А вообще:
A и B - халявы, ладно.
C - известный алгоритм, написанный в википедии (кстати,
неверноне совсем тот там алгоритм)D - мегабоянистая задача
E - халявная геометрия
Не знаю как всем а мне такие контесты ну не нравятся.
Ну вот совсем не нравится, когда за полтора часа до конца сидишь с написанными всеми задачами и гадаешь: на чём все всех валят... Так, кстати, и не знаю на чём сколачивались +40 по A.
Интересно, сколько людей сегодня скатали его оттуда и были похачены?
“Придумал я неправильное решение, оно не прошло. Тогда я придумал ещё несколько неправильных, но они тоже не прошли. Но я же красный! Значит, задача плохая.”
По-моему, глупо.
В моей динамике ровно один переход, отличающийся от обычных переходов в задаче о редакционном расстоянии. Решение прошло.
Я и сам, когда решаю задачу, бывает, слишком увлекаюсь подбором решения на частных случаях, и в итоге задача обычно не сдаётся. Это не значит, что задача обычно плохая. Это значит, что такой метод решения при злоупотреблении им обычно не работает.
Да что за тип-то? И почему не подходит?
“Нельзя давать на соревнования такого формата такие задачи. На АСМ я бы с радостью порешал такие.”
А почему? Потому что на ACM добрые дяденьки из жюри сразу тебя тыкают носом в номер теста, а тут надо самому больше думать о тестировании? А в формате ТопКодера это была бы тоже плохая задача?
Ещё раз повторю подробно: решать задачу угадыванием решения — очень плохой метод. Даже на ACM. Нужна очень хорошая программистская и математическая интуиция, подкреплённая годами опыта её применения, и даже при этих условиях должно ещё повезти.
NoobGuy:контест тот еще, но к задаче C
как раз никаких претензийпо условию нет претензий.претензии есть к задаче A из-за совершенно мутно написанного условия.
пришлось фактически "реверс инжинирить" условие, то есть восстанавливать, что же хотел сказать автор, по второму семплу.
на всякий случай даже английскую версию посмотрел - там тоже беда.
большинство отгадывали неправильно, я тоже вначале ошибся, потом перечитал, сделал ресабмит и 16 челленжей ^^
в B тоже условие с первого прочтения не понять, но оно хотя бы корректное.
ну и задаче D тоже скажу "фи", потому что баян, и при этом дорогой.
к сожалению, этот баян я как раз решать не умел, пришлось оставлять на потом, подсматривать в википедии и проигрывать только на этом ~1000 очков всем тем, кто умел.
а в C надо осознать, зачем там ограничение на цену обмена, и когда в итоге этот обмен вообще имеет смысл применять.
тогда случаев становится намного меньше, потому что без обменов задача совсем классическая.
те, кто писали эвристики вида "обмениваются только соседние исходно элементы" (еще раз ресабмит и еще +7 челленжей) - сами себе злые буратины.
только у меня по ней TL18 в итоге какой-то непонятный :(
если дело не в том, что алгоритм O(n*m), а в том, что он написан на жаве, то это, конечно, еще одно огромное "фи" авторам.
UPD: "так и вышло", переписывание 1-в-1 на cpp дает accepted.
UPD2: несмотря на все сказанное, новый цвет мне все равно нравится =) так что спасибо авторам хоть на этом.
ну тут подвела привычка писать динамику рекурсией.
Input
2
1 2
1 2
Output
0
Answer
1
Checker Log
wrong answer 1st numbers differ - expected: '1', found: '0'
Почему ответ равен 1? Я считал что луч сам с собой не пересекается и специально обработал этот случай.
"количество лучей в наибольшей группе лучей, в которой все пересекают друг друга."
"Профессор, есть некоторые группы лучей, в которых все лучи в данной группе пересекают все остальные лучи в данной группе.
И вообще по условию раз есть какие то остальные то они все таки есть,и тест с N=1 какой то не такой.
Очень странно..В английском варианте написано the other,что в моем понимании значит что этот the other должен существовать.Глупо на таком получить WA %)
Я про свой WA в финальных тестах. Если убрать проверку на 1=>0 то решение проходит.Да и ладно.
Плохо ,что претесты не покрывают даже самый минимальный тест.(1 1 1 )
Как любил говаривать один наш пожилой преподаватель: "В действительности все не так как на самом деле" :)
А вообще про эту ситуацию я упоминал здесь. И на контесте специально задал вопрос. Я считаю, что автор задачи сплоховал, что не упомянул этот случай в тексте условия, или в примере. А админы сплоховали, что не сделали броадкаст после этого вопроса.
http://codeforces.me/blog/entry/1473#comments
but i'm not sure when the ratings will be updated.
2
1 2
1 2
Output
0
Answer
1
Checker Log
wrong answer 1st numbers differ - expected: '1', found: '0'
I'm not agree with this.
A ray doesn't intersect itself.
And from the sentence:
"Sir, there are some groups of rays such that all rays in that group intersect every other ray in that group.
We can conclude that there is at least one group with at least two intersecting rays,since "every other" is at least one ray.
I want to be rejudged:)
It seems nobody understands me:)
We have:
Statement says:
there are some groups (at least one SUCH group exists,do you agree?some>0) of rays such that all rays in that group intersect every other (THEY DO INTERSECT).
If we have only groups with 1 ray there are no intersections.
For every pair of rays from that group, thay are intersecting.
If there are no pairs, this statement is correct in any case.
If I have no friends than statement "all my friends are girls" is correct:)
This is different from the ordinary way we use words. In the ordinary sense, if we say “all the children playing in the park are boys,” it usually implicitly means that there is at least one child playing in the park (and he is a boy). But in mathematics, we use the terms in a slightly different way.
One may argue that it is unrealistic to assume that the student used the terms in the mathematical sense. But then what would be the correct answer? If you do not think that a set of one ray satisfies the condition, I cannot see why you think that the set of zero rays satisfies the condition, either.
Thanks.Your answer is the best for me.Vacous truth is not a new thing for me.And the problem here for me was really that the statement was written in ordinary language and i didn't think that the student could have used some math approaches to express his thoughts.
Really,the set of 0 rays also makes us believe that the student told a lie in the case of ordinary reasoning.There are no intersections in this case too.You 've almost convinced me that it was my fault too that i made this bug:)
Как доказать - не знаю, написал наобум, потыкал тесты - все проходит. Сдал и получил Accepted.
Касательно задачи D. Неужели настолько очевиден факт, что она сдается НВП? Вот и в разборе написано:
>>The graph generated in this problem is permutation graph. The Clique number of a permutation grpah is Largest decreasing subsequence of the given permutation.
Я прилично думал над ней, но к НВП так и не пришел. Откровенно говоря, чувствую себя идиотом. Как доказать? Неужели факт настолько боянист, что его знал "весь дивизион". И сдали все кому не лень. Или решение легко придумывается. Или угадывается? Может гуглится? Я в смятении... :)
P.S.: пусть LIS дает ответ, но как восстановить ребра клики? Мы ведь имеем только те, что не пересекаются. Поделитесь плз хорошей ссылкой, где данная тема раскрыта...
Сам алгоритм и правда очень боянист. Вот здесь он описан. Кроме того, можно и самому догадаться, как считать LIS, если посидеть немножко с листочком бумаги, там реально нетрудно.
После легкой прогулки помутнение рассудка прошло. Конечно, "факт о lis" в этой задачке настолько же очевиден, насколько сегодня (уже) 14 марта :-)) Всем спасибо.
"Золотую середину" в претестах трудно найти. "Чуть лучше" - уже сложно пропхать неправильное решение, взломы теряют интересность.
"Чуть хуже" - ломают все, кому не лень, набирают за взломы пару тысяч за раунд, уменьшается относительная ценность решенных задач (мол, а зачем решать?.. Не буду сдавать С, половлю баги у других, все равно парней с С, но без взломов, накрою... А там, гляди, тест хороший подберу, так накрою и тех, кто одну из последних двух сдал...).
Anyway, great contest with great problems. Thanks!
Вот все говорят, что задача E - такая халява, задача C - такая сложная. Я, конечно же, согласен... Сам очевидное решение написал за несколько минут, немного подебажил (стал бы писать целочисленное и вообще проблем бы не было) и всё работает. Но! Посмотрите же на разбор этой задачи и авторское решение: http://codefest.org.in/problem.php?pid=103
За такое индусское решение спокойно можно и больше 2500 баллов просить... ;)
Меня если сильно попросят придумать решение по-сложнее, типа такого - я не смогу. Мне существование очевидного простого решения, причем за O(n), будет мешать.
P.S. А решение С - вариация почти стандартного алгоритма, который возможно просто изучается в индийских университетах. Точно так, как у нас все знают как находить НВП. Так что их можно понять - авторы больше времени думали над E, чем над C. Интересно глянуть на результаты контеста, отфильтрованные по стране - чисто индийских участников.
A = {3,1,5,2,4) and k = 1, this is how to calculate B:
B1 = 1 means there's 1 element >=1+k (3) standing before 1 in A
B2 = 2 means there're 2 elements >=2+k (3,5) standing before 2 in A
so on...
I understand now.
You(or others who knows it) know how to lock solution code?
Problems - Submit - ... - Room -....
Choose Problems, you will see locks on problems you submit and pass pretests. Click on the locks. Choose Room and click on other participants' submission to hack.
KhaustovPavel: "Есть соревнования по спортивному программированию, а есть по спортивному взлому задач. К сожалению, в последнее время популярность набирает второй тип соревнований."
Совершенно согласен. Причем уже появились люди, для которых взломы - основное. Я наблюдал на этом контесте, как участник с не самым низким рейтингом сдал A на 4-й минуте, тут же её заблокировал и 3 часа "сидел в засаде". С печальным, правда, результатом.
Получается, что тот, кто "честно" сдает A, потом B, рискует обнаружить, что в его комнате уже кто-то имеет +2000, и ломать-то, собственно, ничего не осталось.
Поэтому, есть предложение: запретить взломы в первый час контеста. Думаю, это должно исправить ситуацию.
Если кто-то уже предлагал такое, извините.
Я не предлагаю делать "TopCoder с 5 задачами". Пусть фазы будут совмещены, но одна из них несколько сдвинута (не на час, так хотя бы на полчаса). Чтобы участники, ориентированные на решение задач, не чувствовали себя дискомфортно уже с первых минут решения контеста: "я тут В решаю, а там кто-то по баллам уже на Е наломал". И чтобы дать больше возможностей решающим задачи поучаствовать во взломах.
Если считать СП отдельным видом человеческой деятельности, который не имеет ничего общего с промышленным программированием, то тогда можно соревноваться в чем угодно. Но для практически всех участников СП промышленное программирование - это будущая или настоящая профессия, и умение массово взламывать на "переполнении инта" там мало полезно (в отличие, от умения алгоритмизировать, точно и быстро кодировать, читать и понимать чужой код, в том числе).
Я, кстати, также отрицательно отношусь к соревнованиям типа «кто напишет на С код с использованием минимального количества непробельных символов». И ладно бы головоломка на часок, так чуть ли не в марафонском формате и с денежными призами.
Я против перекоса в эту сторону, когда взломам отдают предпочтение перед решением задач.
"Also, it is given that 2· te ≥ ti + td."
If this condition is not true, does anyone have an efficient way of solving this problem?
Many thanks in advance!
"References" section here http://en.wikipedia.org/wiki/Sequence_alignment
pva701 до соревнования имел рейтинг 1591. На соревновании он занял последнее место и получил -54 очка.
На ТопКодере за последнее место на СРМ 499 сняли 339 очков, что мне кажется боле правильным.
Мне всегда казалось, что рейтинг - это дополнительный стимул для развития, а если нет стимула то нет и развития.
He is calculating LIS (actually LDS - longest decreasing subsequence, but it's essentially the same) using a Fenwick tree. So it's just a DP solution of LIS using a data structure to improve running time to O(n log n)
In this almost everyone got good ratings, mainly because there were lots of "Unrated" participants.
Is this OK?
Because I saw many people not even solving a single problem got increase in rating.
(I also think that my rating would not have gone that high by getting just getting 1200 pts if there would have been less "unrated" people.)
I consider this is mainly because there were lots of "Unrated" contestants . That was only my concern that whether the rating actually reflect the performance , because u see "not even solving a single question and getting rating increase" is in my opinion weird.
As far as new contestants are concerned , they are always Welcome . :)
In theory, if someone were desperate to keep the rating without actually improving his/her skills, he/she could use a silly “strategy”: participate only in the events where many first-timers are expected. But it is unlikely that many people would try to use this “strategy,” and I do not think that we have to worry about such a possibility because it will not harm the rating of other participants anyway.
I believe that screw_it is pt1989.
You can compare the ranks from codefest results to that of codeforces standings.
Я с первого раза не нашёл и ответил по почте, что не вижу, где вводить.
Последовало молчание.
Вчера ещё раз посмотрел, нашёл:
http://itbhu.ac.in/codefest/award-winners.php#mt
В других контестах бывает другой статус, кроме Prize dispatch details to be submitted, например, тут:
http://itbhu.ac.in/codefest/award-winners.php#vc
Хочется узнать, посредством чего они собираются на бумажно-почтовый адрес отправлять денежный приз, и не лучше ли в этом смысле какой-нибудь номер счёта. Но по опыту они на электронную почту не отвечают.
CodeFest - Award Winners