Привет!
Завтра, 23 января в 18:35 MSK состоится Codeforces Round #340 (Div. 2). Это мой первый раунд, надеюсь, вам понравятся задачи.
Спасибо GlebsHP за помощь при подготовке задач, Delinur за перевод условий и MikeMirzayanov за Codeforces и Polygon.
Всем удачи!
UPD Разбалловка 500-1000-1250-1750-2750
UPD Разбор
UPD Поздравляем победителей!
Div. 2
Div. 1
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | maroonrk | 133 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
I hope problem statements will be also short like this announcement.GL & HF.
Let's also hope for clear and understandable problem statements.
I hope problem statements will have good translation like the announcement!!
What's wrong with them? I think they are quite clear to understand.
So,I hope that problems will be clear and the translating of problems will be easy,Because my only translate Helper is "GooGle Translate" ;) Sorry bad English... GL & HF.
Something about your avatar reminds me of a red coder :p
Best. Announcement. Ever.
I hope you'll get a lot of points in the contest as your comment got up votes :)
u got one from now :P
Cool. Shortest announcement ever!
Краткость — сестра таланта.
Труд — брат таланта!
At this rate the next round's announcement will literally be
:)
Experince shows:
Short blog means long problem statements!
hope experince be wrong.
Nice short announcement.
Думаю, длинна приветствия как-то зависит от количества человек, участвовавших в подготовке. Корреляция кажется очевидной, но это лишь на первый взгляд, мне стоит всё проверить.
komendart, надеюсь, первый раунд последним не будет :)
It's always a great experience to read short announcement and solve short statement problems too. kudos to GlebsHP :-)
Note that round starts at the unusual time!
{joke} As usual, at the unusual time {/joke}, yeah.
Coolest announcement ever! Hope problems will as cool as the announcement :)
Am I the only one who likes long announcements? And statements longer than one sentence?
I remember that, a while ago, a guy (I don't remember his name nor his CF account), decided to tell his experiences in programming competitions in the announcement of his CF round. I think that is a good idea, is very motivating =)
marat.snowbear? Yup, it was the best announcement I've even seen.
We don't mind a multiple line statement. Its the useless backdrop and cover story that is annoying, because it takes up time to read, and some people might think there's useful information hidden in all that story, so they read it slowly and carefully, and maybe they read it over and over again. Talking from div2 perspective only :)
Nice announcement=w= BTW,do you feel the cold wave...Here in China I'm almost can't move anymore...
Время раунда пересекается с ИОИП-ом. Печалька :(
Bref...
Div. 2 only contest, which means loads of fake accounts from Div. 1 users. God I hate this :(
Who else is joining both this round and FB Hacker Cup Round 2?
I am in a dilemma here. Well, I know my limits and I know its impossible for me to advance to round 3. Yet somehow, I can't stop dreaming. I will be having a good fight with my brain I guess.
Doing both will do no good for me. I already have exams and my brain can only take so much :/
Hmm...if I was advancing to round 2, I would definitely compete in hacker cup, no dilemma there. Hacker cup comes once in a year. The problems will be tough, obviously. But what will you regret more? Not solving an intentional easy problem(if any, because so many people are advancing to round 2 this time) in hackercup because you were here, or not getting a rating rise today because you were in round 2? Remember, these rounds(are great!) but they come once in a week usually.
Even if all of hacker cup's problems are difficult, it is still more satisfying to know you did your best in an annual thing. Trust me, if you miss hackercup, you will regret simply because it won't come again until next year.
Extra motivation : this a div 2 only round. YKWIM :)
Well I'm staying up and doing both. :)
I don't know what you would have done if you had final exams in 2 days. But thumbs up for your determination :)
I didn't check the contest time for FHC, but I guess the contests' duration don't clash massively then. All the best :)
In my timezone, this is 11:35pm — 1:35am, FHC is 2am — 5am.
Now I am a little confused why this person had a dilemma in the first place. He should've been well rested prepared and relaxed today. Besides, chances are, being cyan coder, he'll max out after 1-1.5 hour, so he'll have at least one hour to rest in between. You gotta optimize these things to work in your favor :)
well, I am already being underestimated because I am cyan , eh? :v Well I may not do that well in these contests. But for your info, I don't give up until the end. If you see my previous contests, I have submitted many problems late in the contest. Its because I think of a way until the end. And do u know how I got into round 2 of FBH? I thought and coded for problem C for 12 HOURS straight. And I submitted just 2 minutes before the round ended. (Yes , I know many people would laught at this because it seemed like an easy problem to them. But I am not talented, I try to cover it with my hard work. So saying I will give up after 1-1.5 hour seems a little bit insulting. Sorry if I sound rude)
Whatever floats your boat :)
If I were you, I would literally stop after A,B,C. This is not because I gave up but simply because it is good strategy in my opinion. If I get 3 right, I'll have a good enough rating rise. If I solve 3, I will read D, and if I can see the solution within 5 minutes, I'll code, else, I'll just drop it. No point messing another contest because I was too stubborn with a problem outside my reach.
But you know, do whatever you want :)
Honestly I_love_Captain_America's strategy isn't really that good. There have been many contests where the difficulty distribution isn't even or where the order is just plain wrong. Even today, at least for me, D was about on par with, if not easier than C. Another good example is round 338, where many coders considered D, and even E to be easier than C.
And besides, I don't think you can really improve if you don't try to solve the hard problems.
It is good for me. I'll tell you why, so read on only if you're really interested.
I have a short attention span, and I get easily distracted. I have realized that resting before a serious contest improves my attention , compared to keeping my mind occupied with questions before contest. Basically, clearing my head helps me focus when it really matters. That's all.
Yeah, I have already decided I would do hacker cup.
(well, people obviously like to downvote for apparently no reason)
I'm joining both. It's like a 5-hour ACM contest with 9 problems, but with a short 25-minute break, lol
And you gotta attempt first 5 before the last 4 get unlocked. lol
Auto comment: topic has been updated by komendart (previous revision, new revision, compare).
Прикольный раунд, столько взломов
What kind of contest is it?!!!!
Why div2 only contests are too easy these days? they were not that easy in the past
in my opinion it should become harder after 2nd color revolution, since poeple with rating between 1700 and 1899 became div2
Am I the only one who thinks this contest is not easy?
Yes, you are.
The 4th question was way too easy. In comparison to that, the 5th one was like a Div 1 E.
It was barely a Div1 C :)
So, it was corrcetly placed. How to solve it?
I agree. Even div2 B of contests 4 yeras back used to be harder than some of div 2 C now a days.
cf lagging please extend contest a little
Izi contest, izi life :)
The system tests, I guess, will be deadly :(
In the last 7 minutes, I could not able to hack.
Same here
I think hacking attempts should be blocked in the last 5 minutes. Hackees should get a chance to defend.
If you are hacked, it is hardly ever bad for you. You'd fail final testing anyway.
If someone hacks me with 30 minutes on the clock, I'd be grateful. But if someone hacks me with 30 seconds on the clock, I'll be sad.
I've survived hacks because I had time to think and include corner cases. Why will I fail systests always? lol. If I don't include the corner case, and then fail systests, then its bad for me. So, to conclude, hacks are good in general for the hackee unless done very late with no time to correct the mistake.
Yes, and they are neutral for the hackee otherwise. I still don't see why they should be blocked.
So that if you are planning to hack, you'll do it by 1hr 55 mins. Then you won't. So now the hackee has a chance to correct their mistake. Geddit now? You think neutral is something they'd like after solving a problem, for maybe more than one hour(somewhat incorrectly though) ?
I got it now, but I'm not planning hacks by the end of the contest for depriving the hackee of a chance to correct solution. It's just unprofitable because someone else can hack the same solution before you. Also I don't think 5 minutes will change a lot in hackers' plans: "Solve as much as you can and then hack till the end."
Many people choose to swoop in and hack with seconds on the clock too. See for your yourself. The parent commentor in this thread was going to hack with 7 minutes on the clock. Although 7 minutes isn't the worst, but such late hacks are enough to cause a panic to the hackee, especially if they're onto some other problem, and are rushing to submit it. Besides, when do most people hack? When they don't think they can solve any more problems. So that tends to happen towards the end.
Besides, I am not a big fan of passing pretest in div2A and then making a 100 successful hack attempts, even though your own solution gets hacked or fails systests, and still get a better standing than hard working guys, who diligently solve problems. Points from hacking should be the least of our concerns, and by giving hackees a chance to defend, that might be helped.
if u were hacked in the last 5 minutes you will be sad
so if hacks were blocked and u got Failed system test u will be happy ?
what's the deference ?
No, the point is that if we block hacks in the last 5 minutes, hackers will start hacking earlier, and so an incorrect solution will also be reconized earlier. Actually there is a difference, but it looks so tiny for me that I don't think it deserves a new rule.
Doesn't need a new rule. Its already happening with everybody rushing in to submit in last 5 minutes or make last minute hacks . Server goes down :D
:)) However, I hacked one solution successfully on the last minute of this contest.
such contradiction much wow :D
No contradiction here. If there was the 5-minute rule, I just wouldn't hack this solution and it would fail final testing. My results would change, but not my plans.
A task takes as much time as it is given to be done :)
You will speed up with the solving phase. So to say, if you are stuck on a problem, and you plan on thinking till 1hr 55 mins, and then hack for last 5 mintes, you'll change to think for 1hr 50 mins, hack for 5 mins, then (maybe/maybe not)think again for 5 minutes, because this scheme is more profitable under new rule.
I thought you contradicted yourself, but now I see that your statement had ambiguity, so yup, no contradiction there.
That's very unfortunate. I was about to hack a solution for D and the site went down. The hack page didn't load even for almost 3 minutes try. :/
For anyone curious on the hack cases for D, there were two of them:
or
I'm sad that Codeforces lagged out in the last three minutes... So many missed hacks ):
EDIT: I just realized that, for C, I accidentally used an
int. I guess those hacks were for nothing.and the answer suppose to be ?
2for the first test case,3for the second.Maybe I misunderstood the problem properly :(
what the answer for those tests?
2for the first test case,3for the second.They have to be both (2) !
Sorry, but you're wrong. The second case is
3because you can't get the line segments to meet at corners.is the answer for 0 0 0 2 1 4
2
and
0 0 0 2 1 1
this one 3 ?
Yes.
What was the faulty strategy for your first test case?
Many programs went like this:
The test cases in the problem statement specifically included an example where a point was not a corner of the polyline.
That feeling when you was cracked on problem D three times.
Codeforces after system testing
Я счастлив! Это был первый раунд, на котором я взломал кого-то и первый раунд, на котором у меня прошли претесты на четырех задачах. Ни разу даже три задачи не доходили до системного тестирования. Спасибо всем, кто брал участие в организации. Получил массу удовольствия! UPD: И это первый раунд, на котором я решил три задачи. Все с чего-то начинают...)
I was just going to submit for D. Clearly knew there were like 25 seconds left when i hit submit button but it failed to even respond. So high load :\ Damnnnn Even the sites so slow to even open this blog.
Maybe a little extension would have helped.
I should have started sooner with writing hacks. In the last 10 minutes I looked at three different problem D solutions and was able to hack all three.
I guess there will be many failed submissions for D after system testing. :D
First time I hack in codeforces... +13:-1
much polyline so hack
much wow! -
whats the hack?
For answer = 1 there is only one possibility. Tricky part is answer = 2 there will be 8 cases else the answer will be 3.
Eight cases? I found only 6: x1==x2, x1==x3, x2==x3, y1==y2, y1==y3, y2==y3. In each of them additional check determinate if answer will be 2 or 3. What am I missing?
Answer will be two only when line joining any two of the points is parallel to x or y axis.
So first lets consider there are two points such that line joining them is horizontal. Then third point has to be bottom left, bottom right, up left or up right in respect to both the points. Same goes for vertical line.
Whats the solution for E?
I imagine something related to partial sums, but 2D one won't fit in memory and I failed to made it based on couple of 1Ds (like pair of "started from" and "ended in" ones).
MO's algorithm
I almost did it :( . Feels so sad wasn't able to make it..!
Found that I need to resize my integers to unsigned or long long in problem B when contest actually ended, there is no God in this damned world. =C
What is the 7 test case?
Shouldn't number of ways in which I can't break it be still 1 . I mean shouldn't number of ways doing nothing be 1.
According to the statement, each part must contain a nut. Therefore, in this case the number of valid ways is 0.
Hacking Party!
Can someone tell me why are people allowed to resubmit after their solution is hacked? They can find out the bug by seeing other correct solution. Isn't it bit unfair or am I missing something here?
If you lock your solution, you can't resubmit it. If you don't lock your solution, you can't see others' solutions.
i see, thank you :). Was not sure how it worked.
They can see others solutions only if they locked their own one. And if they locked — they can't resubmit, even if got hacked.
they can't see other solutions unless blocked. And they can't resubmit a problem if they blocked it.
You cannot resubmit your solution if your solution is locked. If your solution is not locked you can't view other's solutions.
They haven't locked that problem, so they cannot see the solution of other people. Once they lock the problem, they cannot re-submit anymore.
So many replies. I will add one more :P. You must have locked your problem so you can't submit again.
If you decide to hack it, you need to lock your solution and you can then see other people's solutions. If your solution now gets hacked, you cannot resubmit, since you have locked it.
If someone's solution gets hacked, they can resubmit. They can't see other's solutions till they lock their solution.
Кто часто участвует, подскажите, взломы всегда так тормозят? Или это только сейчас? Или это, вообще, только у меня? Спасибо
Мне кажется это из-за огромного числа взломов. Хотя, опять же, мне кажется что сайт тормозил еще до начала контеста.
I'm rather angry at this codeforces round. First, although I got A in 00:00, B took me very long, due to the fact that codeforces repeatedly gave me website exceptions while submitting. Furthermore, I received rather strange verdicts. 15518610 [submission:15519407][submission:15520501][submission:15521050] 15521416
Next, I encountered significant lag on D, and I submitted the same program twice during the round.
In 15518610, you allocate
vector<int> abefore youcin >> N, that means you possibly allocate an empty vector.Problem B also had a nice hack (for integer overflow). The answer is something like 2^50.
You mean problem B?
I guess you meant B?
What was the solution for C?
For each point, set that point as the farthest point from fountain 1 (so r1 is the distance between them). Loop through all other points to calulate r2. For all r1, the answer will be the minimum of r1^2 + r2^2. Runtime: O(N^2)
Am I the only one who hates this hackerfest? :)
What is bothering me is that 20 hacks gives like the same points as hardest task. And it seems that skills required to solve hard task and skills required to find 20 solutions failed on the same one test case is not really on the same level.
You should also apologize for this kind of english :p
such meme. much 2013
so followers, very amaze
wow
In problem C, many people forgot test cases that r1 = 0
Ex: 1 0 0 2 2 3 3
Ans: 2
Same here :(
What happens for B if all are 0?
ans is 0 then
Any chance that was the test case 7? :?
Yes, this is exctly test #7
This is what happens when you arrive to contest with 20 minutes left :// :(
It was in problem statement. Answer will be 0.
Really? I don't see it in the statement?
Well, I consider this line covers this case:
"Please note, that if Bob doesn't make any breaks, all the bar will form one piece and it still has to have exactly one nut."
поменять бы местами C и D...
D вообще можно вторым поставить =/
В решило в 3-4 раза больше людей, чем D. Так что, все как раз-таки расставлено правильно.
Вообще это не совсем показатель — большая часть людей не читает сразу все задачи в поисках легких, а решают по порядку. Так что вполне вероятно, что большое количество участников банально не прочитало D.
Я бы ну как минимум с C ее поменял местами, возможно что и с B тоже.
Вообще вся сложность D — это найти в чем же ее сложность :D Банально добавить один тестовый пример — и ее бы все решили за 5 минут.
А с B и C такой финт не пройдет — там хоть какой-то, да надо алгоритм придумывать.
Вы частично правы, но когда разница в четыре раза — тут уже не в том дело, что условие не читали. Отношение решивших к попытавшимся у В в два раза выше, чем у D.
А это я готов объяснить слабостью претестов в D :)
К тому же, возвращаясь к моему предыдущему посту — задачку B большая часть участников начала решать почти сразу (через 1? 5? 10? минут после начала), в то время как до D они с большой вероятностью добрались только к концу соревнования.
Слабость претестов — это часть сложности. Требуется умение проверять свой алгоритм на корректность, а это, во-первых, часто не проще, чем решить задачу, во-вторых, это разумное требование к программисту, ибо в жизни всё предусматривающие тесты никто заранее не напишет. Тем не менее, между C и D дисбаланс очков заметен, это правда.
After system tests, solvers of C reduced to half and even D suffered 40% loss.
Only 1 unrated in Top-20 :o
bad contest :|
strange contest !!!
C and D are good problems for the HACKers
That moment when you find out, that in one task you are reffering to a1 instead of a2 variable, and in second task you are reffering to a instead of b...
В проблеме D. Тест 9:
дает 2 или 3?
Вроде 3 должен давать, ибо за 2 без самопересечений никак.
Your contest f**ked me :-(
Everytime you think the contest is easy , and next minute your solutions gets hacked
All problems are very excellent and interesting. Thanks to komendart!
maybe Chinese are more familiar with Mo's algorithm...the problem can be solved off-line.
My solution for C:
http://codeforces.me/contest/617/submission/15530019
Nice solution (Y) , were you sure it wouldn't TL ?
I solved it the same way and was sure it won't TL. A bit additional note: In step 2 we skip points that is already covered.
Important thing here is the optimization he mentioned. Because of it recursion will stop on depth 2 in every possible case.
O(2^n)? Wow
It's O(2^n) without the optimization. I think it's O(n log n) with optimization, but I'm not sure.
Yes it is O(n log n) with optimization. And this complexity is for sorting. After that, its O(n) (instead of O(2^n)) to find a solution.
Автокомментарий: текст был обновлен пользователем komendart (предыдущая версия, новая версия, сравнить).
Пропало с главной
Вернулось
Я случайно сохранил как черновик.
Не могли бы вы ответить на 2 вопроса? Этот раунд не рейтинговый? И ещё, написано что раунд див 2, а в нём также участвовали те у кого рейтинг за 1900?
holy s**t :o !!! 1416 successful hacks on D! should've done better
when is the update of rating expected?
Hope this not the part where I find out I completely misunderstood problem D. What's the answer for the following input? -931665727 768789996 234859675 808326671 -931665727 879145023
Shouldn't it be 2? 1 segment between points 1 and 3 and another segment connecting 2 to the first one. Right?
The answer is 3. Any segment must connect 2 points, not a point and another segment.
This doesn't work because the x-value for point 2 is in between points 1 and 3. After we connect points 1 and 3, we need to go up and to the right from point 1 to reach point 2. This results in 3 segments.
In that case, wouldn't the answer for the third example be 4 segments? right and down + down and left.
I assumed a segment can be any length and it doesn't have to start or end with a particular point. Thus, for the 3rd example you have a vertical line passing point 3 and one horizontal line for each of the other two points.
Points are like this
Answer
If you said " No response, Read the problem statement" I would take in consideration both cases, but when you reply with this I become sure that no way there is a case with no nuts -_-
Спасибо что уделили время и ответили на мой вопрос.
I was so happy because i solved D first time. But i did a little mistake and that mistake went unnoticed after system test.
My submission fails for this test case.
1 1
2 2
3 3
MikeMirzayanov Please look into this.
Div2 C
http://pastebin.com/QyUVUnwt
I am unable to find the bug in my procedure :( Please help
I think you have to also consider the case where r1 = 0.
the contest had 4 unusual easy problems and very weak pretests :| almost it didn't have judge during the contest..
Ага. Их можно отключить
wow such a beautiful winner :) I wonder how many girls have won any competition here at codeforces ))
Look at her and subscriber's codes, and you will see he doesn't respect himself.He is an asshole, he participates at div2 rounds with fake profile, subscriber is stupid, don't be like him
It was kinda rude , but you are right. Their codes are very similar.
And he got C wrong.
I finished at 7th position in Div 2 in this contest. Will i get any codeforces tshirt or something ?