Приветствую сообщество Codeforces.
1 декабря 2014 года в 19:30 MSK состоится очередной раунд Codeforces #280 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.
Это мой первый Codeforces раунд. Надеюсь, он вам понравится.
Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.
Участникам будет предложено пять задач и два часа на их решение.
UPD: Разбалловка стандартная — 500-1000-1500-2000-2500.
UPD: Спасибо всем, кто принимал участие в раунде!
Поздравляю победителей:
1.alex_y
3.Eric94
4.Zpw987
UPD: Разбор задач здесь.
thanks MikeMirzayanov and Zlobober and Wild_Hamster for this contest :)
Fixed :D
Thanks, fixed.
I had a lot of school's exams in this week and I didn't practice for coding...
But i like to join the contests...
God please help me...
Well I have a philosophy test tomorrow but it seems like I don't have much any time to prepare =P
Same I many exam today. I study right now. English is bad subject,i fail exam
Indeed
I very hurt from comments you have.
not worry, yourself be, to you luck of best !!
If I am correct, this is the first time a wild hamster has prepared a codeforces round.
I bet, "It is my first round on Codeforces."
Что, 1 декабря?!!
What about the scoring system, dynamic or regular/normal... ?
I bet, "Scoring will be announced just before the round starts."
"UPD: Scoring will be announced just before the round starts."
What a prediction.
Is Down vote became a tradition in CF, just asked a simple question and got so many Down votes... Really Unexpected... :(
UPD: Scoring will be announced just before the round starts.
This line was added to announcement after my post, and some so called smart didn't get that while pressing down vote.
You may be so smart but Don't think some one that much stupid!!!
The question about the scoring system appears every time the new round announced. Obviously, the community is quite bored with that tradition.
In my opinion, announcing scoring system is not important, as it will be clear when the contest begins. Knowing problems' score before contest starts doesn't help you solve problems much. An announcing contest blog should introduce something about problem setters so that everybody will know them :D
P/s: A lot of comments in this blog got downvotes, but I hope your guys will upvote my comment. Please. don't downvote, please :(
Heh, just want to mention that i know few guys saying "i have some other things to do in the evening... I'll find time to participate in CF, but only if there will be no dynamic scoring" (as you may guess, they don't like dynamic scoring for some reason). And maybe someone else have some other strange preferences:) But announcing of problem values for a normal scoring does not helps a lot — because it is often completely meaningless and does not describe relative problem difficulty — like in round 275, when both B and C had 1500, but B was solved by ~10 times more users than C.
For me it seems meaningless to update blog in last minutes before contest — one may just enter contest few minutes later and he'll see values there:) But i don't know why scoring distribution isn't published a long time before contest — they just don't want to, or it is really decided just a few minutes before the start.
P.S. It is risky to ask about upvotes:) Well, i'll upvote you, as you wish, pushing one button takes much less time than even typing of this message and it is an easy way to make a kind gesture:) But why do you care about upvotes? I can't understand point behind it. Contribution score is even more useless than rating, isn't it?
Yes. I agree! Contribution is not as important as rating on Codeforces. It was made only for fun, and to make the forum more active, I think. But it will be a bit unhappy if my blogs, comments got downvote. Why? It means that people seems to hate me :( The last sentences on my above comment is quite simple: There's a fact that a lot of other comments got downvotes, and I don't want my comment to get dislikes.
Sometimes, I try to find the answer of the question: "Which type of blogs, comments have most upvotes?" This question is not for coders, but it's an interesting and non-easy question. :D
Ok. Asking about upvotes is risky, I won't do it anymore :D
Вокруг города автора прикольные названия населенных пунктов. В России они обычно попроще, а тут прямо воображение просыпается)
Слободка. А че, хорошее название!
Старый угринов. Ну че так невежливо? Ладно, Средний угринов.
Стебник. Хочу туда, там весело.
Кто мне может нарисовать, что за звери - Пшеничники ? А курить их можно?
Ivano-Frankivsk wooohooo :-)))) best wishes, hope for great round.
all right, maybe I've gave too much emotions to that post, sorry ;(
Are you talking by yourself?
hopefully no..
In fact, it'd be strange if he couldn't talk by himself, but needed someone else's help even with talking :D
1 December 1918 – Transylvania unites with the Kingdom of Romania, following the incorporation of Bessarabia (March 27) and Bukovina (November 28), thus concluding the Great Union
It`s wrong to be proud of your country?! Because i received so many downvotes.
Not wrong, it's just not the proper place to do that.
it's not wrong to be proud of your country , you just posted this in wrong place.
Автор тролль.
не просто так спрашивал походу ) видимо в контесте будет задача на максимальную подматрицу, состоящую из единиц
Скорей наоборот. А вы, наивные, думайте, что будет такая задача )
в таком случае Konstantin.Zakharov правильно охарактеризовал автора)
Мда! Несколько дней назад решал эту задачу из архива, она из Div2 то ли C, то ли D
I have a general question. Hope you can answer: Why is always the scoring announced just before the round starts? Is there a specific reason?
It was asked before or here, but always without the answer...
I can answer this question. I was an author for several rounds, and every time the complexity of the problems was not precisely clear. But since there is always a lot of more important work to do right until the contest, we usually agreed to the score distribution shortly before the start, after other work was done.
небольшой вопросик: когда будет раунд для див1?
В первый же день, в который я 100% не смогу зайти.
А вообще — до НГ один будет точно (goodbye-round уже традиция). Хотя мне кажется что будет минимум два.
The surprise is not only this contest but also we have another one after just 2 days :)
Three consecutive div2 only rounds
3 till now :D
the problem is dreamoon_love_AA is waiting for div1 to back again to div2 so he has to wait a lot :D
I'm afraid it won't be rated. Servers are slow for me for about one and half hour and the contest didn't start yet :-(
It seems to be better, for last half an hour, we will see...
I'm afraid it will be delayed for 10 minutes :)
that's not a problem comparing to be unrated
Brace yourselves, clone accounts invasion incoming.
Контест очень хороший для див-2, сложность идеальна! Нет вот этих задач Е с 5 решившими, которыми часто грешили в последние годы.
Нехорошо править задачу Е без клара, хоть и правка была вполне очевидна.
А в чем правка состояла?
в том, что можно вывести любую точку пути. изначально вообще было не понятно, какую именно нужно выводить...
I think there will be a lot of fails on C while system testing! Good Luck!
What's the meaning of problem D? @.@
How was E supposed to be solved?
Notice that answers for a[i] and a[i]%(x+y) are same. After it we can find answer in the range of 0..1 second with help binary search. I mean we find exact time, when happened last hit. And we will determine who is made it. Sorry for my English.
Hey I wanted help with E actually. I edited my initial comment, typo.
Vanya's character shoots every 1/X seconds and Vova's every 1/Y seconds. Let's make time pass more slowly by a factor of X*Y. Now Vanya's character shoots every Y seconds and Vova's every X seconds. Using binary search you than calculate when a monster dies, and checking if what characters shoot at that time is trivial.
for problem D I didn't use binary search, instead I tried to see what can happen in one second? Well, in one second we can have as many as x + y hits in the worst case. So you can have an array of size x + y where in position i you store who actually makes the ith move. For simplicity my array was 2 dimensional of size [x + y][2] because it's possible that both players can make a hit on the ith move. After one second, the same things happen so you don't need any additional information about for example the fourth second because it's the same as the information in the first second. Now to answer the queries you just take the query move ai and then output myArray[ai%sizeOfmyArray]
complexity is O(x + y) to create the array
and O(n) to answer the queries
WTH ??!!! first you ask about D ... people answer your question and you change D to E???
i gave Sherbina_Evgeniy -1 ... :|
My bad! Sorry.
poor Sherbina_Evgeniy, i´m giving him +1 to compensate... :) (apart from the fact that his answer is correct)
Sorry for failure in last minutes, I'll investigate it. It seems it works good almost all the contest, but failed the end. Sorry again.
Good evening!
I've sent 2 solutions for C just in case. I thought that it's logical, that the second try will be ignored. Why the first try is ignored? It has passed the tests and would've given more points. Is this normal behaviour? I've missed it...
01:28:17 Попытка игнорирована [претесты] → 8919160 01:53:40 Полное решение [финальные тесты] → 8921562
Suppose that you've submitted a problem, and it passes pretests. Later you find bug in your solution, fix it and resubmit. It still passes pretests. Would you be happy if the second solution is skipped?
It should not be skipped, probably both solutions should be tested, and the best one should be chosen...
Ok, maybe this is done to avoid overloading of system testing with a lot of submitions which pass the pretests.
This is not the first time to fail in last seconds by the way.
So, will it be rated?
What was pretest 3 in D :\
Test:
Answer:
May be answer in your program:
You are right. I counted both together shooting as 1 shot instead of 2. How stupid of me! -.-
Me too :/
Last 20 minutes, unable to hack. Anyone else on this boat? :-)
Yup , also got the test file generated and couldn't hack in final 5 minutes.
Задачи слишком простые. Я не решил Е только потому, что сначала правильно прочитал условие (включая gcd( n, dx ) = 1 и gcd( n, dy ) = 1 ), придумал решение, потом придумал тесты, на которых это решение валится, но эти тесты слегка не удовлетворяли gcd, о чем я вспомнил только за 5 минут до конца.
UPD: Решение по Е, которое я придумал на 60 минуте от начала контеста — зашло. P.S. Впервые выдался такой шанс за контест решить все 5 задач, впервые решить Е во время контеста, и я его упустил =(
Слишком простые? Думаю, что нет... По-моему, таблица результатов во втором дивизионе достаточно сбалансирована +как заметил dalex, сложность задачи Е была такой, что и халявой не назовешь, и решило не 5 человек за контест, что, как мне кажется, большой плюс для контеста.
Total this contest = problem B,test 3
Codeforces is temporary unavailable (last few minutes before the end) is that fair ?
what about the case of one solved problem correctly and didn't get the chance to submit it before the end of contest by 1 minute
what about the case of hacking someone solution and the system down before hack ?
Worse yet, unable to read other people's code in an attempt to hack them. Yup, same boat.
It is fair, since it is unavailable for everyone.
Not if someone else started hacking before the system failed to deliver. Then it is unfair since only people who planned to hack earlier got the privilege to do so.
think before write something. everyone has different strategies in contest time. how come a red coder says its fair? just cant blv my eyes
some people read all the problems first then sit to solve, some do it one by one. its completely non-sense to say it was fair.
Please don't misunderstand me. I think the only reason to ask "Is it fair?" that makes sense is to question the fairness of the organisers of the contest. I personally believe that the staff of Codeforces is dedicated to prevent any mishaps. But if it is accidental, of course it is not fair in that sense that different participants are affected unequally. It just doesn't make sense to me that the organisers' actions are to blame in such situations.
And please, don't color-discriminate people. I was only expressing my thoughts.
i solved the problem D in time, but could not submit it in time. It might be fair for div1 coder like you, but don't mock at tiny coder like us, at list my thought goes this way.
It is "fair" in that the circumstances are the same for everyone, but it isn't "fair" in that different people are affected differently.
I think the definition of "fair" should involve "follows the initial premise". Simple example: if, an hour into the contest, an announcement was posted that in order to speed up the testing, all submission results will be random (with some distribution), it would not be fair (by common sense, it's just fucking around, "fair" has no meaning), even though it affects everyone equally. In that sense, unexpected fails can't be considered fair.
That's not to say I disagree — it actually was fair, since the fails aren't exactly unexpected anymore... and anyone who jumps into contests without checking what they involve takes the risk on himself.
Still, the question to ask here is not about fairness. It is fair, and it sucks. And contests should be fair and fun.
dreamoon_love_AA is first place in div2 but unofficial :)
dreamoon_love_AA is first place in div2 but unofficial :)
I guess dreamoon won't be first place when he gets into div2.
If I view someones code for Hacking, but if I don't click on Hack It! then does CF deduct any score?
NO
No! you will only lose score if you unsuccessfully hack a correct code.
Even if we unsuccessfully hack an incorrect code. :)
How the user rank 201 in official standing solve two problems at same time ? :D
may be he solves earlier but submitted at same time because of network problem
two problems solved in 13 minutes second and third problem how although he solved the first problem in 4 min it mean that he solved the second and third problem in 9 minutes only ? :D sure he is magician :D
it is pretty much possible
see rank 137
Thanks Wild_Hamster for this nice problem :)
Как решать C?
UPD — прочитал решение, понял что там сыграл фактор кривых рук...
Hi,
I think there might be something wrong with app context for executing C# code. In problem B, my numbers were printed with "," comma separator, while answers were expected to be printed with "." separator. I wasn't using any formatting, i was using just: Console.WriteLine(decimal);
In Russia ',' is usually used instead of '.', but anyway, it's incorrect servers' setting.
P.S. I've just checked, for java submissions, dot is used.
Could anyone help me understand why 8922945 and 8922927 with identical code but different compilers give different answers on the test #1 in C?
What Every Computer Scientist Should Know About Floating-Point Arithmetic
http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
So it's because of the optimization of GNU compiler. Thanks a lot.
Codeforces compiler for c++0x has some issues with float point. I've also got wrong answer with gnu c++0x (aka c++11) and the same code got accepted with gnu c++4.7.
i too had the same issue with mine .
For the question B, I was getting wrong answer on pretest1. I changed long double to double in my code . And it got accepted!! Can anybody explain me how did it work ? My Code for the same
Sorry, this is not an answer to your question. I also have an issue with double. It returns the correct answer on my local machine but apparently on CF it seems to return nan.
My solution: http://codeforces.com/contest/492/submission/8917850
My solution for D is the following http://codeforces.com/contest/492/submission/8923198 It gives Memory Limit Exceeded for test 17.
If I do not store the elements in an array I passes all the tests (http://codeforces.com/contest/492/submission/8923768), but based on the input size the array should be max 400 KB. When reviewing test 17 with this modification I get a smaller memory usage with 100 MB.
I think this is not caused entirely by the array but because of the flushing of PrintWriter in Java. Do you guys have any suggestions/recommendations?
EDIT: I just checked and the output buffer and input buffer should be 8 MB each. I have absolutely no idea what the problem could be :|
Rating is too Late.........?
When will rating be updated?
Everybody(div2) waiting for rating.
Was it an unrated contest?
Hi, I'm wondering what the best way is to test an algorithm that I couldn't quite finish after the contest is over. I entered a virtual contest, but that doesn't indicate what was wrong with a submission either. Any way to just play with the problems for training purpose?
Also: Is this the best place for questions like this?
Best, Esuhi
Just go to contests tab and click on "enter" instead of "virtual participation" and you can submit all the problems in practice mode. (Though you may have to wait until the virtual contest is over before you can do that :p )
Try the "register for practice" button on the contest dashboard. If you don't see it, you're already able to submit (and see tests).
Edit : Looks like I replied few seconds late. :)
Yes, you may have to wait for some more time for that. Usually the contest problems are added as "Practice" problems in the problem set archive, tagged by contest id etc. Currently I see that submissions for practice problems are blocked temporarily by admin. Once its unlocked by admin, you can submit/test your solution there and test cases (system tests) will be run against your solution for the verdict. Hope this answers your question. :)
Why is problemset page blocked by the admin?
Ratings are updated! :) Cheers!
Was I the only one that "misread" problem D and thought the swing timer doesn't reset every time they kill a monster? There is nothing in the problem statement that says otherwise, until you run it on the first test.
Well, you are right. At first sight, I also was in a dilemma.
That was my first understanding as well. But I saw that it would not work for the provided input. BTW, How can one ask for clarification? Is that possible on Codeforces?
Yes, you can ask for clarification on the problems list page.
this is exactly where I got stuck
It was a lucky contest for me....
And the best contest in codeforces so far.... :D
Hi. Can someone explain to me why at the C problem , I get runtime error if I use the compare function
bool cmp( const pair<long long ,long long> &x, const pair<long long ,long long> &y) { return (x.b<=y.b); }
but accepted when I use < instead of <= .
I think your compare function must be transitive.
Compare must not be true for both (a,b) and (b,a) at the same time — most STL operations involving comparison functions check this with an assertion, which explains the RE.
Thanks
http://codeforces.com/contest/492/submission/8914525 Can someone explain where am I wrong , can't figure out from the failed system test case for problem C
You multiply
long longbyintwhich makes the result of multiplication lower than intended, therefore the answer is less than it's supposed to be.EDIT: But I'm right! You just have to switch all
ints tolong longs and your solution will pass! I just tested it: 8928368. This is absolutely same as your submission except I changed allints tolong longsEDIT2: Ok, this is not even funny, why am I getting downvoted for trying to help? And people wonder why I have trust issues.
Its not that line.
hereis a longlong so the result of the multiplication is still a longlong. I'm going to guess the culprit iscmp = avg*n*1LL— since multiplication is left-associative, it multipliesavgbynbefore converting the result to longlong.Waiting for editorial. Can anyone please explain how to solve E?
No need to wait, just look in Recent Actions. /blog/entry/14957
Deleted
Can anyone explain why this submission for problem C is giving RTE on test case #11, and why is this code getting accepted? All i have changed is in the comp function: "<=" comparison to "<" ?
Sorry if this isn't the right place to ask clarifications.
For Problem C) I checked the editorial and my java solution appears to be correct. All I am doing is a sort and then a O(n) linear calculation, but my code is timing out in 1000 sec for the worst case test. (10000 items). Test for 1000 items is 92 ms, so it appears 10000 is probably > 920 ms but my code looks right. 8920114
Can anyone clarify? This is really puzzling. I don't know if I should switch to C++ because of this.
You use LinkedList, which has not random access, so you sort in O(n2). Try using ArrayList, instead of LinkedList
Java Scanner class is really slow. For example, see submission 8953230, class FastReader.
I saw somewhere that it is possible to improve performance of Scanner by upto 7 times by using the next() method and doing a type.parse (like Integer.parse) than to do a nextInt() as it takes out regex processing. So it looks like the FastReader is using this idea as a wrapper.
I suggest you reading source code. It doesn't use Scanner, it uses BufferedReader