Привет, Codeforces!
27 января 2015 года в 19:30 MSK состоится очередной раунд Codeforces #288 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.
Это мой первый, но, уверяю вас, не последний Codeforces раунд. Надеюсь, что все пройдет хорошо, и он вам понравится.
Хотелось бы сказать большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon и за идеи некоторых задач, а также моим дорогим однокомандникам Артуру Свечникову (ikar) и Илье Лось (IlyaLos) за прорешивание задач. Илья, не обижайся, в следующем моем раунде обязательно будет задача про тебя.
Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.
UPD Разбалловка стандартная 500-1000-1500-2000-2500. Всем удачи!
UPD2 Соревнование завершено! Всем спасибо!
UPD3 Разбор вы можете найти здесь.
UPD4 Поздравляем победителей!
Preparing for the battle..
Preparing for the battle...
Good Luck to everyone :). I request all Div-1 Participants to participate Out of Competition. Hope I become Div-1 Coder after this Round :).
加油~
We were roommates today :)
Unfortunately you got your C faild :( else you would be there :( Next time :)
Congratulations to you for both 1st position in the Room as well as for jumping into Div 1 :).
Two consecutive Div — 2 contest. It's really frustrating for Div — 1 participants.
Actually 3, next round is also a Div — 2.. :(
I'm curious, how do you know that?
http://mirror.codeforces.com/contests :
Codeforces Round #289 (Div. 2, ACM ICPC Rules) — Jan/31/2015 15:00
I remember that I saw Round 288 div.1 && div.2 about 5 days ago. But now there exist only div.2...Could I ask the reason why the div.1 is cancelled? Is it because the problems for div.1 are not prepared?
Here there are some others informations.
Div.1 users dont create new accounts please.
I think that problem is separate rooms for div 1 users.Many of them want fun,hacking,and best place in their rooms. If that changes,contests would be more regular.
gl & hf )) PS: Good luck and have fun) PSS: I have 4 houres before CF. It's about 5 games in Dota 2. GG :D
Just try not to break your pc before the contest :D
Just try to have good team.
It's for valve to decide :)
I have a lot of friends, who really can play well)
Although it's a Div.2 only contest, but still it will be a good start for me! I'm sure I'll enjoy the contest!
I hope this won't be dynamic scoring in this contest :|
cheaters don't cheat!!!!
and you assume that cheaters will do what you say ? :D
if they cheat i find them :)))
Have you found yourself yet...
Myself or yourself?
Update about the scoring system well before contest.. That's unusual.. but nice .. Gl & Hf
let the game begin :)
5300+ participants. That's amazing)
UPD: 5400+ :D
It's a cruel battle. Good luck:)
700+ unrated participants. Funny, isn't it?
What Does standarT in last line Mean Exactly?
Try to come up with it :)
It's a typo. It should be standard which means 500-1000-1500-2000-2500
means that problem setter is from Russia. ;)
It means the score distribution is a work of art
not to prepare contest is much better than have a contest with many mistakes;
Doublepost, please delete, codeforces comment system is a bit hard for me.
triplepost, please delete, codeforces comment system is a bit hard for me.
Suspicious?
dreamoon_love_AA just might reach his dream of first place in a codeforces round !
But he is now 2nd...
how to solve E
Как решать D?
Рассмотрим граф, в котором вершины — это пары допустимых символов. Тогда каждая тройка — это дуга между вершинами. Ответ — эйлеров путь в таком графе.
Я написал поиск Эйлерова пути по графу, у которого вершины — пары символов, а ребра из вершины "ab" в "bc" идут тогда, когда в инпуте есть "abc".
Каждые соседние две буквы искомого слова — вершины графа, а каждая данная тройка — ребра. Нужно найти либо эйлеров цикл, либо эйлеров путь.
omg im turnin greeeeeeen!!!!! ;(
How to solve
D?I have an idea that "ABC" is actually an edge between "AB" and "BC". What we need to do is to find an Eulerian trail of the induced directed graph.
(Yeah, I failed in the second part)
Looks correct. Why I didn't come up with this idea at the first place?!
Let's look on the graph in which each vertex is a pair of symbols. Then for example abc = ab -> bc. The answer is the euler path in such graph.
Imagine a graph with 52 * 52 nodes.
Each node represents a string like this "ab".
Then each sub string means edge in this graph. Find Euler path.
even more digits are also allowed .. I have not noticed this thing and start coding and later realised that this solution is of no use now ..
I did not noticed digits. It would be nice if they were bold :(.
Thank you, for pointing out my bug during contest.
62 * 62 nodes...
Довольно забавно, минут 20 пытаться взломать задачу, когда она была взломана раньше, но при этом ни в попытках участника, которого взломали, ни в таблице ничего не отображалось!
Can someone tell me what's wrong with my solution here? for problem E? I used an O(n^2) method, but I still get TLE .-.
I think, it's not O(n^2). Try test: 1 10000 1 10000 1 10000 ... 1 10000 2 10000
Wait; I was talking about problem E. That isn't a valid test.
Sorry. I mean:
600
1 1199
1 1199
... many time 1 1199
1 1199
2 1199
how to solve D and E ..
B is gonna have so many System Testing wrong answers :3
Пожалуй, самый простой контест на моей памяти. Несмотря на это, задачи отличные!
Проще, чем предыдущий?
В предыдущем у меня было несколько неверных идей по D. Сейчас над задачами практически не думал — просто реализовывал. Долго и криво, правда — но это уже мои личные косяки >_<
Настолько простой, что D отправило всего 57 человек :)
И правда, не посмотрел! А мне D показалась легче, чем C... Субъективность, однако =)
C D, полагаю, у всех были проблемы с реализацией, а сама идея то по своей сути очень простая. Я сам 30 минут писал код, в котором сейчас уже разобраться и объяснить почему так написано — не смогу, да он и не работает.
По мне так самый простой контест вот: 280 раунд, хотя тут в задачах нужно было чуть больше подумать над идеей решения и отловить частные случаи
It was very fun contest :D
I wonder how can solve C...
Hello mhkim4886
C can be solved using this idea that the candles required at the ith second can be burnt at i-1 , i-2 ,,, and so on second .. but after burning these candles check once whether you have achieved required number of candles or not .
I don't understand why this code couldn't pass the first pretest case about problem D, I did Eulerian Cycle and I got the same output in every pretest case, but I got WA in pretest one :Ssss ><
http://ideone.com/1RfNzu
Кому нибудь удалось взломать решение по B, где прям явно свапали символы в строке и сравнивали строки? И возможно ли это вообще? Я решил сначала локально посмотреть, сколько это будет работать, и оказалось, что почему-то не тлится. Возможно, я тесты плохие делал:)
Я таких 2 на TL взломал. тест: string(1e5 — 1, 2) + "1"
Мне удалось взломать таких 3, и одного неудалось.
Был массовик-затейник, который на каждой итерации при лексации брал максимум из двух строк. Взял на ТЛ его.
I don't understand why this code couldn't pass the first pretest case about problem D, I did Eulerian Cycle and I got the same output in every pretest case, but I got WA in pretest one :Ssss >< http://ideone.com/1RfNzu
Use custom invocation in situations where your code does not pass test 1. Your code prints "NO" on CF servers.
but what is the problem with my code?? :S
When I tried my code in ideone this one prints "YES" :S....., somebody?
Looks like you do not assign the "comp" variable, which is local. Should be:
int ip = 0, comp = 0, ini;Finally I got AC, O(E) in memory instead O(V^2), my complexity is O(V + E), this was the first time i need to erase edges in O(1).I didn't use adjacency list, just arrays, but this guy did it
http://mirror.codeforces.com/contest/508/submission/9595512
I solved A but couldn't submit...
Gray has been my favorite color.....since I started here ^_Q
It was my favourite too.
D was a very interesting problem; can someone give the algorithm?
Interpret as a graph from the first two characters to the last two characters of each substring, and find an Eulerian path.
Find Eulerian path with something like Hierholzer's algorithm.
Just for fun !
What's wrong with that? Take care of your own submissions, boy.
Thanks for realy funny contest, with string problems! :) . And thanks for weak pretests! In problem B I've found some too slow submissions in my room, so need to generate maxtest for these submissions.
pending system testing 10 minutes @@
I submitted C in the last minute and didn't even get time for checking my A. After reading the editorial I found out what a foolish thing I did with A just because I thought I had to solve 3 this time.
where is the editorial? thx!
Here!
Прочитал Б 3 раза, узнал все о бурлях, но пропустил главное — что входное число точно нечетное.. Анаграмма смешная, но почему-то сильно отвлекает.
didn't ever seen a problem 0.5 second!!! time limit during any contest!!! why so strict time limit is it a problem with only one solution, and any other solution would fail?!
i believe this was done to avoid bruteforce solutions that try to compare every possible swap and output the best one. When it also can be done greedily.
didn't use anything but swap and time limit!!!!!!!????
Your solution is O(N2) because of string comparison. Calm down.
I tried the very same thing as you but I got TLE in pretest 10, so i resubmitted with a greedy approach. Trying to generate the solutions with swap on a string seems to be too slow.
i think it's luck that my solution passed pretest 10 and didn't think about the greedy one xd
It's not :) If it got wrong answer, you could think of another solution and accept the code for real this time. Of course, it's good for the hackers, though :)
of course it isn't i meant bad luck xD
The only one solution is very very fast than other ways.
Thanks for setting awesome questions . Though few were ambiguous, I enjoyed participating in this contest
Is it unrated contest??!!! I am in place 700 and still gray... hooooow!
No, it's only unrated for Div1 participants. You will be rated.
thanks so much Olaf :)
Кстати, а почему в последней задачи изменили ограничение по памяти?
http://cfa.yuldashev.net/contest/508
Humble reminder in case if you missed the post
Very strange: during the round I was hacked by kgbugy659. She solved all the problems and was on the 2nd place before the end. But now she's out of scoreboard, her submissions are not listed in the room o_O Furthermore, her last rated round (before today) is not included in the graph. Weird %)
Yeah, I saw him but he is gone now...
Dear Nuta,
:O
It may sound stupid, or rude, but I would please all the Div.2 / Div. 1+2 setters to announce the winners. I mean, especially for Div.2 contestants, who, some of them will never reach top 5 in a Div.1, it really makes them happy to see their names on the round post, and I consider it to be a nice thing. However, one will do as he wants, it was just an advice. :)
I guess that the fact that Div 2 winners have been "newcomers" most of the time likely discourages writers from putting such thing in their posts.
Hmm yes, this is a bit sad... But still, there is always at least one person in the top 5 wo isn't a newcommer.
done
Didn't expect that to happen! Thank you, sir!
What has happened to this participant? http://mirror.codeforces.com/submissions/Nuta She's sent submissions to all problems during the round, and was at top-2. But right after the end she got out of rating.
Why doesn't stoi() work on CodeForces? (C++11)
agree, as well as to_string()
Can someone explain to me what could be so special about test case #40 for problem A. I tried to hack this solution during the contest: http://mirror.codeforces.com/contest/508/submission/9582562. I expected that if I had some moves 1000 1000, it would lead to RTE (as it must throw a segmentation fault) . But, my hack was unsuccessful.
I tried this test case: 1000 1000 4 1000 1000 1000 999 999 1000 999 999
Why did it fail to produce a RTE veredict?
Array out of bound errors on C++ is undefined behaviour. It's usually impossible to know what the program will do in these cases.
Thanks, I will keep this in mind before trying to hack again :)
This hack would work:
Dang! I didn't check the time limit on problem B. My bruteforce solution got TLE :( I'd better check the time limit on each problem next time.
I am sad that my C(with set-stl),got TLE,but I am happy I became blue :D. That was my first goal,now it is division 1. I say that just because,I want grey and green users to know,that with 'correct' practise we can do everything :D