Всем привет!)
Завтра 19 марта в 19:30 MSK состоится очередной раунд Codeforces #237 для участников из 2 дивизиона. Традиционно, участники 1 дивизиона могут написать соревнование вне конкурса.
Подготовкой задач занимались Игорь Кудряшов (Igor_Kudryashov) и Геральд Агапов (Gerald). Кроме того, выражаем благодарность Михаилу Мирзаянову (MikeMirzayanov) за прекрасный ресурс Codeforces и Марии Беловой (Delinur) за перевод условий задач на английский язык.
Желаем всем участникам удачи, высокого рейтинга и удовольствия от решения задач)
UPD: Распределение баллов будет стандартное 500 — 1000 — 1500 — 2000 — 2500.
UPD2: Соревнование завершено, благодарим всех за участие.
Поздравляем победителей:
UPD3: Разбор задач можно найти здесь
Gerald's rounds are always nice. Thank you for preparing this contest!
Yes, I agree with you.
Why always there is some unrated users in top 5??
A day before Nowruz!
Wish this good round completes the happiness of starting of our new year!
Happy 1393 (Solar Hijri calendar) to all Persians arround the world ;-)
Wish everyone happiness and good luck!
P.S: You can follow the exact time of year delivering (March equinox) in Iran here
Edit: Year delivering is the national word (تحویل سال) but the scientific name is March equinox
Happy new year!
...What country is New Year?
Iran.
Is it standard distribution?
EDIT: Why people are so opposed to asking a simple question? Obviously when I asked this information was not in the main post...
Good luck everyone~ This must be a good contest! :)
I hope this will be my last Div.2 Round (1699 now) :)
Before last contest you've got 1666, also nice :D And I've got 1697 :)
404 contest not found! ++id; :D
Oops. I guess I didn't register. I feel like it let me register with out being logged in so I thought I had registered but I actually hadn't. Next time. Good luck. Zoz
Опять в среду =( Пичалька.
Next time you'd better get a DECENT translator to translate the problems! OR release the problems in RUSSIAN ONLY!
This time I firmly disagree with you, translation quality was decent enough, Can you specifically point out which problem had poor translation or possible issues so that translation might be improved in future.
I don't get it neither... Even if some problems were tricky, I haven't found statements being hard to read.
The statements were extremely vague and poorly written! I would read each line over and over again to understand what the writer is trying to get at!! Also many points were unclear, some samples clarifications should've been added!
They were not much clearer in Russian.
However it is a free contest and you pay nothing to practice here, so probably it is not just to complain. "Take it or leave it", you know. :)
Well this depends on how you define "free". I don't like to sound rude but this whole thing is not made up for charity you know! Codeforces is getting well known a day after the other and it can attract many sponsors and companies that would host their competitions on it, so it's not free, what you are saying might apply to something like UVA but not Codeforces! When you make a platform, users are your capital. You wanna make something, make it the best possible or don't.
And by the way, I don't mind paying if this would result in a better platform! Actually I'd be very glad to do so. That's not the point I'm trying to make, I appreciate their work and efforts and everything but they need to consider this feedback if they really want to achieve something!
first to note, other people reads the same description
second, what it's like good a problem has good description ?
every people has different kind of understanding, you should not blame the problem if many other peoples understand it, try reread it, if you still dont understand, ask here or send clarification (while contest)
What exactly you suggest? Magically improve the skills of existing translator or hiring a new one?
But you know the amount of work is not sufficient to hire full-time employee. At the same time it is not possible to hire the same free-lancer for short job each time. So it will be necessary to rely upon several at least.
And it is not easy since CF team is deeply concerned of keeping the problem statements in secret.
I think it is too bold and too careless statement. If understood literally that means you and me should not participate in this round, since we did not get in top-5 :D
I think I missed (or at least die trying) in my statement :D. This problem (poorly translated or vague statements) has been around for a big while now (along with other problems, like the increase in number of cheaters, servers' outages, etc) and I believe that the time is overdue to consider a solution for this! I really believe that this should be taken into consideration. I know it's a bit unfair, but I always compare Codeforces to TopCoder. TopCoder is a very big company with big resources comparing to Codeforces, but I do really believe in Codeforces and their potential to become as good as them someday, all it takes is just paying attention to their users' feedback to improve the platform.
Nice problems and nice contest...!!! Thanks to authors...
Что не так с таким решением в С? У нас есть множества с одинаковым значением в массиве d. Если ноль стоит у более, чем одной вершины, то -1. Если "пропущено" какое-то значение в d, то -1. Далее пытаемся построить граф: проводим рёбра в множество со значением d на единицу больше, пытаясь минимизировать число исходящих ребер. Так проделаем последовательно для всех d. Проверим количества рёбер, обойдём граф и сравним массивы d.
Hi Igor_Kudryashov, I can not understand the reason behind giving constraints of length of string being upto 1e6 in problem D. I think you could have checked peoples logic even with the length being 1e5 and it would have let dp solution with slightly more space pass in the contest (eg mine) !!
One round with problems descriptions containing so many unspecified points.
was it just me, or is the statement of problem B a bit too complicated to understand?
IMO, either the statement should have been worded a bit easier to understand, or the second example case should have been explained (preferably with diagram).
unless, ofcourse, this problem was intentionally designed so that everybody spends more time understanding the statement than coming up with the solution! :P
It was not only you, I had a very hard time too.
the statement was very clear imo...
Как-то грустно, что уточнение условия по C пришло спустя >30 мин после начала. До этого, получается, решал другую задачу. Думаю, не я один такой.
Мне кажется, это вполне естественно, что если граф невзвешенный, то расстояние — это количество ребер в кратчайшем пути. Какое другое понимание возможно?
Просто про "невзвешенность" не сказано нигде. Правда, по-моему, что граф невзвешенный итак из условия понятно было...)
Действительно, про "невзвешенность" сказано не было. Перечитывая условия и ограничения теперь уже очевидно, что граф невзвешенный. Однако, на контесте первая мысль была почему-то другой. Сразу думалось в сторону inverse-SSSP. Надо было лучше читать условие. С другой стороны, если все так очевидно, то зачем была рассылка?
Рассылка была "на всякий случай". Видите, оказалось, что помогло кому-то. =)
Really nice problemset!
But some statements in English were a bit hard to understand for me.
Unfortunately I spent 35 minutes debugging my code for problem B and replacing cout with printf made my code pass the pretests!
I can't believe why printf is faster than cout this way! Although I used
ios_base::sync_with_stdio(false);and I thought it makes cout work as fast as printf. Also printf and cout both used the same time to print in my system.Can anyone explain this diffrence to me?
i'm not an expert on which prints faster and how to optimize I/O, but u can have a look at these if it helps.
my AC solution 6071440 using
printf(in contest).my AC solution 6081037 using
cout(just now, in practice).EDIT: as expected, the second solution has a much higher runtime than the first! even using
ios_base::sync_with_stdio(0)(6081967) does not improve time as much as i expected.there were some relevant discussions that you may refer to,hope you'll find it useful
http://codeforces.com/blog/entry/5217 some tests on various input ways;
http://codeforces.com/blog/entry/6251 A discussion link
Why didn't they update the problem statement of 404C - Восстановите граф when there was an announcement?
so sad failed at final system test, at problem c, just because didnt check the number of edges at vertex 1 :(
And I failed because I didnt use long to check for (k-1)freq[i] <= freq[i — 1]. :(
warm_hug sigh, currently i rarely got 1 shot ac :(
hope do well next contest :D
A lot of people failed test 29 on C. Is there any way to see the entire case? There seem to be ellipses at the end of the description.
Or does anyone have an explanation?
Any help would be appreciated :)
Незнаю, что не так сделал — B (тест 8) — 6080228
le:=i*d;Похоже, переполнение longint-а.
А как правельно? Как непереполнить?
нуу можно использовать двоичное умножение по модулю, но намного проще вместо LongInt'a написать Int64
Int64 < 9*(10^18)
LongInt < 2*(10^9)
Ничего непоменяло. (6095118)
Значит у тебя не переполнение, наверное, ошибка в решении.
UPD. Попробуй заменить floor на trunc.
Заменил — AC (6095226)
It's time to change my nickname to FakeRalor
I know that feeling bro :D :D, I couldn't solve A, B and my solution for C failed because of a stupid bug!
I'm ready to try it once more. Just to test rating system)
UPD this is the post for those who like computing probabilities
I don't really understand the complaints; I thought problems were pretty clear and well-written, though I do agree problem statement of C should have been changed following the announcement. Seems to me that people are quick to blame the language when problems are hard(er than usual).
я знаю, что не так сделал.. в качестве IDE выбрал VS вместо GNU один и тот де код дал AC и WA17
Igor_Kudryashov,Gerald
Congratulations, very nice problems. :)
Объясните почему ВА? Ведь с каждой вершины выходит не более k вершин. Вот решение — 6080015
раз четверка встречается 4 раза в ответе, значит и степень у нее 4 (k=3). Хотя чекер почему то сказал что это у третьей.
Но выходит-то 3 вершины, а не 4. "из каждой его вершины исходило не более k ребер"
Может чекер не переводил в 1-индексацию
Did anyone else get WA for test 29 in Problem C? The test case is too long (and hence truncated) which is why I can't test it locally.
UPD: Try this test case: "000??1?1"
Isn't that a test case for Problem D? Could you provide one for Problem C too?
The WA was because of integer overflow when multiplying (k-1) and the number of vertices in the previous layer (i.e. when checking the condition (n(l)<=n(l-1)*(k-1)), where n(l) represents the number of vertices in the layer l). Casting into long long before performing the multiplication resolved the error.
Hi,Igor_Kudryashov!First,thank you for preparing this contest! But I have a question with the judgement of 404B - Марафон I don't think that there is any trueness error in my solution ,and I think the answer has.(I used __int64 to avoid it.because the date of a and d are given with precision till 4 decimal digits after the decimal point ,we can use a * 100000000 to transform double to __int64 to avoid the precision problem).But I just cannot make it. Could you please take a look at my code? Thank you very much!!!
6082317
I'm sorry. It's my own fault.
i have noticed this for the last 5-6 contests. system testing finishes very fast, but rating takes a lot of time to be updated. why is this so?
EDIT: ratings updated! :)
Thank You Igor_Kudryashov and Gerald for this round..
Off-topic: Sometimes after ending the contest i feel like i am an big donkey. The masters solves all problem in 1.5 hours.. And I can not solve more than one in two hours. It feels likes i am low brain animal.. This one is one of them..
Will have to learn many things still. Hope to learn somethings from the tutorial.
:)
There is no good trainer or participant with rating 1600-1700+ in your university, there is an answer. Sometimes it's a question of 5-10 seconds to learn something important from those who knows more.
Yeap.. Brother. I know. But unfortunately not every one have the chance....
Could somebody please explain on why this answer is accepted but this one is not for problem B.
Because int(975910353.9999999) is not equal to 975910354. Do not forget to round before converting to int: replace int(float(...)) by int(round(float(...))
Thanks! But the problem says
a and d (1 ≤ a, d ≤ 100000), given with precision till 4 decimal digits after the decimal point.So it should only contains 975910353.9999 but no 975910353.9999999?UPD You're right. I finally understand after reading this. Thanks a lot!
Congrats ! It was a nice set of problems and the tutorial came very fast. I particularly liked problem C due to the fact you had to think how to implement it in a simple way. I also liked E because it was quite original from my point of view.
i think that this is the first time in history of CF, where user who is placed in first position has failed A and B! :D
even so, congrats to Pkqs09! :)
For my submission 6082618, the checker comment (for test 5) seems wrong.
your 4th vertex has more than 3 edges. It should be 3 or less
UPD : okay maybe comment need some correction
i think checker comment is 0-indexed. i agree that it seems confusing, because problem asks us to output vertices in 1-indexed fashion.
but the verdict of WA is correct, because ur vertex 4 has
degree > 3, which is not allowed.Может кто подсказать? Почему у меня вторая задача на мониторе помечена, как еще не прошедшая тестирование, хотя по его итогам она прошла все тесты?
Никто не подскажет, по какой причине у меня зашедшая D отображается как "?" в мониторе?
У меня аналогично с задачей B
Wow! Some cells in Standings still show '?' and even if they are actually AC, no points are given!
Edit: Standings was fixed, and ratings were re-updated. I am relieved.
where is my D ？
вопрос снят.
fixed
This is so strange, I found out why my B submission wasn't working My idea was to convert all doubles to ints by multiplying by 10^4 (because the statement said that was the most precise they would be given in) just to be safe in case of errors.
I have
#define SC 10000as my scale factor This is my testing code to find the bug:Where dd is the distance read in as a double And d is the distance converted into an int after being scaled up
On my computer, I get this:
On codeforces, I get this:
For some reason only on the codeforces server, it's converting 28819.0 to 28818?
My erroring submission is here: http://codeforces.com/contest/404/submission/6079213
Does anyone know why this is or how it can be fixed?
This is because of round off error
the float output of 2.8819*10000.0 is like that 28818.99999
try adding small value like 0.00001 to dd*SC
Ah ok. So it was the rounding.
How come when I run this on the server
printf("%.6lf\n",2.8819*10000);my output is 28819.000000 ?Thanks for your help.
This has some sort of random behavior i think!
Round stats
There is -1 change in the ratings of the contestants since last night rating update. Last night when i logged out mine was 1588 after the update but its 1587 now. Some of my friends also have -1 rating down. Was the rating re-evaluated due to some error in rating update ? or something else ?
apparently there was some issue with system testing due to which some solutions were not tested (relevant comment).
so i guess some of these solutions got AC and resulted in a big increase in a few users' position (and, consequently, small decrease in some others'). due to this the ratings had to be re-updated.
someone explain me why this code (problem C) gets runtime eror ... 6088745
Perfect round! I love codeforces. It gives me a lot of new skills. And you?
Hey i have one question,
In Question Restore Graph Tutorials say that there would be a tree then why they have mentioned edge 3 2 in first test case? I think we do not need that edge,
Thanks :)
the
onlysimplest answer is a tree. any code which doesnt print that edge3 2(like mine 6077747) will get AC.about why it was given in the first place, i guess it was to make the contestants think a bit more, rather than just look at sample input/output and get the approach straightaway!
Got my mistake, Thank you :)