Всем привет!
Через несколько часов начнется Codeforces Round #159 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Иван Фефер (Fefer_Ivan), Павел Холкин (HolkinPV), Виталий Аксенов (Aksenov239) и Геральд Агапов (Gerald). Кроме того мы выражаем благодарность Марии Беловой (Delinur) и Михаилу Мирзаянову (MikeMirzayanov).
Традиционно всем удачи, полных решений и удачных взломов!
UPD: В раунде будет использована динамическая система оценки задач. Задачи отсортированы, по мнению авторов, по предполагаемому порядку увеличения сложности.
UPD: разбор на русском языке доступен тут.
UPD: контест закончен, поздравляем победителей!
3.Dakurels
4.ytqiaqia
Thank You ! We Were Waiting for The First Contest in This Year ! :)
Correction Required :It is obvious, but traditionally it is Round #159.
In Indian culture, it is considered good to make minor mistakes when you do something good (like a small typo in the wedding card). So hope this NEW YEAR CONTEST is good for all.
I can't wait to do it >_< thank u very much
Nice, waiting for tutorial :)
hey senior ,do u still need :)
wow it seems all the comments here get negative votes. so here i am! :d
happy new year and good luck :) :*
thanks
Динамика... Хорошо год начинается :) Мне лично понравилось! Желаю всем УДАЧИ и повышения рейтинга!
C-C-C-COMBO BREAKER!
Не успел! Жалко!
Вот вам и динамическая система оценка задач: Б-шка падает на один балл с А-шкой, хотя она на порядок сложнее.
А по мне, так они обе одинаковой сложности. Разве что Б пишется в одну-две строчки, а А — в семь-восемь.
D тоже пишется в 7-8 ;)
странно, что стоимость задач не такая: 500-500-500-500-3000 )
У меня одного в начале контеста упал КФ на пару минут?
У меня он весь контест периодически подвисал...
У меня люди застряли в лифте, я не успел их вытащить...
Не подскажете метод решения? На ум пришло только декартово дерево по неявному ключу.
разбор уже опубликован, ссылка в посте :)
У меня два сумматора, один для людей, которые ждут у лифта, второй для людей в лифте, которые хотят попасть на текущий этаж. Так можно быстро считать нужные суммы. Ещё у меня для каждого этажа очередь людей, и для каждого этажа, куда люди из лифта хотят выйти, тоже очередь. Так можно людей реально распихивать туда-сюда, и ответ записывать, храня для каждого человека индекс. Ещё, если лифт стоит без дела, то я путешествую во времени на следующий момент, когда кто-то подойдёт, так можно избавиться от больших t.
Problem A description was so hard to interpret. It took me more than 15 minutes to get what the problem was asking.
Как Д решать?)
За 40 минут не застрессилось такое:
Идём с конца и ставим + или ‒ так, чтобы сумма была как можно ближе к 0. В конце, если получили отрицательное — инвертируем знаки.
UPD это заходит.
Заебись)
In problem A , I was really getting confused through a lot of words like supply line filters , devices , sockets , electric sockets. I was really changing the symbols through and forth.
I could not even understand the meaning of the problem :(. I need to improve my English.
Its not about how good your English is! The problem statement was the worst ever!!
humm...really, I've not understood too... :(
Отличный контест, но сложность видимо вещь ооочень субъективная.
p.s. Как решалась C и что там может быть в 6 тесте ?
Вы можете смотреть тесты. Для этого зайдите в раздел "Попытки" в вашем профиле и кликните на номер сабмита.
Секунд 15 до конца контеста -> Нашел потенциальную ошибку, исправляю пару символов, Ctrl+A, Ctrl+C -> Открываю окно "Отослать" -> Ctrl+V -> Выбирал задачу -> Бросив взгляд на таймер(оставалось приблизительно 8-10 секунд) понимаю, что успел... -> Нажимаю "Отправить" -- кнопка не кликабельна -> Завершается контест -- кнопка становится кликабельной. Конечно не факт, что исправленный код был правильным, но все равно такая вот беда...
how amazing testing system
About Problem C
Why
atan2()have error, butacos()is ok?PS: Oh,
atan2()is ok. The error occur becausecoutandprintfhave some diff.Got AC with atan2 (after contest). Here 2893071.
UPD: I know who are downvoting to these comments. People who had no fun in this contest.
THOSE WHO USE RUSSIAN-CF ARE LUCKY THIS ROUND.
atan2() works. May be just careful boundary crossing angles handling.
I get AC using atan2(),,
I used atan2, no trouble whatsoever. But you can just check your solution with the test data you get the error at, and find the bug.
This is Contest or english lessons?,problem A is so hard who does not know english,Fuck english
Let me rephrase your question: are the problem setters foreign language experts? English is the main scientific language, too bad.
It's okay. On ICPC we were calling such problems English problems. Sometimes they were two A4 papers long. But we were able to dedicate time for that, concentrate, read and sometimes solve.
Hi,
I believe there is a problem with the solution judging system for Problem D: Sum.
My corrected submission after the round (now registered for practice) can be found at the following link: @ http://mirror.codeforces.com/contest/257/submission/2893122
For test 1, which is: 4 1 2 3 5
My solution output: +--+, which works, because this translates into 1-2-3+5 = 1, whereas my solution was judged WA, because the system was expecting "+++-" instead.
The problem statement clearly states "If there are multiple solutions, you are allowed to print any of them."
Could someone please verify this/provide me some clarification please?
Thanks, Lee Wei
Hi, your solution outputs extra symbols (it seems with code 0) after the answer. So, problem's checker reads token <<+--+__>> (symbol _ for clarity only) and considers this token not a valid answer.
I think everything is ok.
Hi,
I've done further tests to narrow down the issue. It seems that if i only print a single character up to n times, instead of traversing the whole vector (which I've initialised to be max size n), i break when a counter i inserted hits n, then the solution is ACC — see 2903009.
is my STL container traversal macro correct?
#define TR(c,itr) for (typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)Yes, it seems correct. Could you show a working and a failing solution that differ not so much, or elaborate on what is wrong?
By the way,
vector<char> b(n);creates a vector of actual size n, not of "max size n".Can someone tell me why long double doesn't work, but same code with double gives AC? here are submits :
WA : http://mirror.codeforces.com/contest/257/submission/2893123
AC : http://mirror.codeforces.com/contest/257/submission/2893207 (in this code shorten "ld" is for double, not for long double...). When I execute same TP with long double on my computer, it outputs correct result for me. And if I use cout, it truncate the last 6 digits, so I get WA again.
You must not print
long doublewithprintf("%lf", d);because%lfreadsdoublebut notlong double.To print
long doubleyou should write like this:printf("%.10lf", (double)d);. Or you can usecoutlike this:After
cout.precision(10)andcout << fixedprogram will always output real numbers with exactly 10 digits after the.I know %lf is for double, but I have used in code %llf, and it worked fine on my computer. I have tried Custom test and I have found few things. $llf and %Lf doesn't work with gnu C++ 4.7 compiler, but If I switch compiler to Microsoft Visual C++ 2010, I get correct answer no matter do I use %llf or %Lf for long double. I have submitted WA code from previous post, with different compiler, and I got AC. :( so sad I didn't realized this before. Thanks anyway on answers. I hope this mistake will not recur.
in Microsoft Visual C++ long double == double.
sizeof(double) == sizeof(long double) == 8
in GNU C++ long double != double.
sizeof(double) == 8
sizeof(long double) == 12
That's why Visual C++'s printf works with "long double"
http://mirror.codeforces.com/contest/257/submission/2890819
check out this solution. I know the solution is incorrect, but the reason why I got WA is really surprising.
I did exactly what all u told, I set the precision as 12 digits after the '.' Still answers didn't match.
more surprises... outputs are different in codeforces and Ideone.com. following are the links-
IDEONE : http://ideone.com/43Vxq6
CODEFORCES : http://mirror.codeforces.com/contest/257/submission/2892803
Does anyone have any idea that how I can get TLE with GNU C++ 4.7 and AC with Microsoft Visual 2010 with the same code on both??!!!! I stuck on this problem for 90 mins in contest and I almost felt this contest. :(((
Sorry for sending this to Russia
Does anyone have any idea that how I can get TLE with GNU C++ 4.7 and AC with Microsoft Visual 2010 with the same code on both??!!!! I'm stuck on this problem for 90 mins in contest and almost missed other problems. :(((
no one can answer this question?!!!
Mr.MikeMirzayanov answered: "Yes, the compilers are different. You may contact their developers :-)" Thanks everyone.
Div 2 — Problem A:
My solution is giving correct output for the testcase: 5 50 6 2 1 3 1 3
with output -1 on my computer and ideone:http://ideone.com/hM20Vq but giving a different answer on custom test here and hence judged wrong. Please do something about it.
If k > n, then this loop goes outside the array, so the variable
sumis added an undefined value ofa[n]. You can use customtest to debug directly on CF.Changing it to min(n,k) gets ACC. Thanks alot for pointing this out.
my solution is producing correct output for all the test cases,but my code is failed during the system testing on case 17,although it gives correct output -1. can anyone answer why this happened ? my solution can be viewed here
I tried it locally, it gives incorrect output 6. The issue is in your code.
sir,I have checked on custum test indivisually only for that case. It gives output -1.
The bug is in line 15: for(i=0;i<=k;i++)
Here must be no k, it must be n.
ohhh...thanks. Its my fault.I got it. sorry for troubling you all.
I wrote a solution about problem B long 3 lines in O(1) time. Looking among the submitted solution almost everyone has solved the problem in O(n) in more complicated way. I wanted to ask why, is there any case where my idea fails?
Some of my friends solved it with 1 liner solution O(1) and their solutions passed the system test!
I don't know how or why till now!
The optimal strategy is the simplest one: as long as you have a choice, use the cube that gives you a point. I don't have a solid proof for this, but it's sort of the obvious way (especially given it's just problem B and those rarely involve more than brute force/greedy).
How will the situation look, then? Suppose there are A cubes of the color which the first player chooses as the first cube, and B of the other, on the input. Then the adding of the cubes only gives 1 point to the player making the move, until there are no more cubes of the desired color; then, each turn only gives a point to pl. 1.
From this, it's easy to see that the sooner there's only 1 color left, the more points pl. 1 gets, so A <= B. And it's just simple math from here on out.
(This is just my opinion on the solution. I used the greedy approach, though, since I code faster than think so logically :D)
Okay, here is my comment on this contest.
This was the worst contest I ever played on codeforces! The problem statement of the first problem was the worst ever! More than 15 minutes of reading and I couldn't figure out what the problem is talking about!!
For the second problem, it was not clear as well! Many people submitted O(1) solutions which passed the system test for non obvious reasons (at least for me!)
huh, funny?!
Contests aren't just about thinking/coding, but also about being able to efficiently understand the prob. description (and other stuff).
For my opinion on the solution of prob. B, read above.
I actually liked this contest, because there weren't crazy jumps in difficulty.
But still the statement of task A was unecessarly overloaded of test.
edited ..
editorial in Russian published here @ http://mirror.codeforces.com/blog/entry/6357, use google translate pls, at least until a translation (will it come?) arrives.
What about the English editorial?
Is there a tutorial?
Still no tutorial?
BTW can you update the tag for problem 1 it can also be solved using binary search approach.
Can't find the editorial..