Добрый день, уважаемое сообщество!
Завтра мы проведём Codeforces Round #342. Раунд пройдёт на задачах Московской олимпиады для 6-9 классов, но не надо думать что из-за этого задачи будут простыми. Гарантирую, что все (в том числе участники из первого дивизиона) найдут для себя что-нибудь интересное. Задачи были отобраны для вас жюри московских олимпиад: Zlobober, meshanya, romanandreev, Еленой Владимировной Андреевой и мной; подготовили задачи члены нашего научного комитета: wilwell, Sender, iskhakovt, thefacetakt и feldsherov.
Разбалловка будет достаточно необычной: 750-750-1000-2000-3000.
UPD Системное тестирование завершено, поздравляем победителей:
Сложность задач оказалась несколько выше, чем требовалось, возможно стоило подготовить раунд для Div. 1 тоже. В любом случае, спасибо всем за участие, я надеюсь вам понравилось и вы узнали что-нибудь новое!
Спасибо romanandreev за отличный разбор задач.
I am not able to register unofficially for the contest. Please fix this.
Fixed, try again.
Working now, Thanks.
Автокомментарий: текст был переведен пользователем GlebsHP (оригинальная версия, переведенная версия, сравнить).
Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).
In the same time as Open Cup 10 stage. It's a pity.
У меня после предыдущего раунда (AIM Tech) назрел такой вопрос. Ситуация: отправляешь решение, оно проходит претесты. Потом отправляешь на эту же задачу еще одно решение, оно претесты не проходит. Попадет ли на системное тестирование первая версия кода, или нужно делать еще одну засылку? Баллы ведь все-таки снимаются.
Is this contest going to start at the same time of the official contest? Because otherwise it should be unrated, right?
It's not going to start exactly at the same time, but it will start before the statements become public and will end at the same time as the onsite contest (which actually runs for 4 hours).
GlebsHP you forgot to thank yourself :)
A sentence like this ??: I thank myself for my great helps to myself in preparing this round.. :D
Links to any previous contests by the same authors would be very helpful. It'll give a good idea as to what to expect in the contest! Any help?
Click on the user profiles, and go to Problemsetting tab.
How would previous contests help ? o.O
Quoted, "It'll give a good idea as to what to expect in the contest!".
Wish Codeforces a happy Chinese New Year!
I hope the Chinese New Year will bring good luck.
Of course!
Nice and short announcement . Kudos to GlebsHP
I guess problem statements will also be short and nice.
@ admin whenever i log in into my account(manish_nit) everthing appears in russian, i have to manually right click every time and select translate to english. this creates lot of problem during contests...is there a setting in the codeforces website to do it permanently.
Of course not. You better learn Russian. Who would think of a language switcher?!
Is it national level competition?
Seems to be city level.
Thanks! I expected the problems to be much easier for a 7th grade local competition :). I lost too much time on the first problem, then B and C were probably just about right for a Div 2 contest (750 and 1000 points). Didn't even get to D or E ...
why A and B has the same points ?
Why not a combined division contest?
Great authors and of course great problems!
A contest by new( GlebsHP ) and old( Zlobober ) coordinator.
Hello Zlobober again!
Why so many — votes? :)
I don't know! but this contest was good for me after about 30 bad contests.
(I took place 18 ;) )
took
thanks; edited (English is my default language!)
Zlobober is backed :))
Great contest and perfect timing, do contest before dinner, then watching firework at mid night, happy lunar-new year.
I agree with you.
Its Sunday morning in my country. Is it bad if I miss church for contest ? I like contest!!!
Bless you to take part in the contest, my son.
Today in China, it is Spring Festival, which is the most important festival in China, every single of Chinese will have supper with family. I hope in the New Year, Codeforces will be better and better~
i will have fun before the Chinese Spring Festival dinner.
Luckily I won't miss the Spring Festival Gala at 20:00.
But I think the Spring Festival Gala is becoming more and more boring
go to watch Pay New Year's call offering of bilibili at 18:00(UTC8)?..
hope it will be my last div2 :D
We will miss you :) congratulations.
thanks xD
happy chinese new year！！！
Happy Chinese New Year(the Spring Festival) to everybody and wish Codeforces will become better and better !
Happy Chinese New Year~
What is the hacking test for problem B?
If the solution searches the whole string from the beginning after each time it finds the pattern.
Some participants were finding string matches in O(n) but ridiculously wrong ways.
can i solve the problem B use kmp algorithm???if not ,can anyone give some advice? by the way ,happy chinese new year!
I've solved it with KMP :)
Submission
You don't need KMP. O(30*100000) is fast enough, so you can brute force the whole problem. If the pattern was longer, a linear time string searching algorithm would be suggested, but in this case (the fact that it's a Div2B should give you a hint at its difficulty) it's not necessary and has a larger chance for mistakes. This is what I did in the contest (runs in max 46ms on main tests, which is easily good enough) http://mirror.codeforces.com/contest/625/submission/15858375
You really replace some characters with '#'! I just imagined to replace. 15874296 Although it's after the contest.
C seems so easy then A and B. I think C < B < A Due to overflow with binary search, 6 wrong submissions on A :\ I hope it passes now.
Is this approach correct? Write numbers from 1 to (k-1)*n in first (k-1) columns then again start from column 1 write numbers in increasing order.
I think B and C are equally hard/easy and A easier than both of them.
Where did you used binary search? I haven't use it at all.
UPD: Well it seems that I will fail A after system testing. Actually I now think C is easier than A and B, just because its solution is obviously correct comparing to A and B.
I used binary search to find number of times one could buy glass bottles. Looking at others code now, it seems there's a direct formula, but i couldn't get it correct.
tnx god i am not the only one who used binary search
Haha, I was so desperate about failed pretests, I also used binary search. At least it worked :) Problem A was a trap, it was a good idea to rush through B and C first :(
How did http://mirror.codeforces.com/contest/625/submission/15865754 pass?
You don't need to use a binary search — the answer can be found in O(1) with division. http://mirror.codeforces.com/contest/625/submission/15857590
how to solve D ?
Who is the author of the Problem A? >.< And tester also >_< ?? No mercy, No mercy >_< :'( :'(
Now, I know why Russian coders are so good and accurate.
Nice problem-set, especially first problem.
Eagerly waiting for editorial for 4th and 5th question and hoping my solution for 1st three problems pass the system tests.
why this work on test
100000 symbols a
a
for 0,2 sec
I tried hacking a solution like this and also failed.
Find returns at the first occurence, so that takes O(1) time. erase can take up to linear, according to specification. But it is probably very optimized and the Codeforces servers are really fast (solutions with 10^9 operations can pass time limits) so it passes. Perhaps erasing the first character is faster than erasing from the middle, as well?
i try to change first symbol to 'b', and it's work fast too
This was my solution for 2nd (div2)
x = raw_input() y = raw_input() print x.count(y)It passed the pretests XD, i dont think it will pass the final tests ... will it? EDIT : It passed!
See this test
As far as I know python3 count method counts the amount of non-overlapping substring appearances, so your test is not going to hack the solution.
UPD: Not sure about python 2 tho
I wonder how many A solutions will remain after systests :O. What was hack test for A btw
I was using this:
1000000000000000000
1000000000000000000
500000000000000000
499999999999999999
Is answer 500000000000000001?
Yes, it is)
mine was 45 30 98 89
1000000000000000000 500000000000000000 100000000000000000 99999999999999999
1000000000000000000 1000000000000000000 1000000000 999999999
Very interesting problems. I got a lot of fun. Thanks to authors!
Ouch, the penalty for wrong submissions really showed through this contest because of the sudden spike in difficulty between C and D. Two wrong answers for A cost me 200 places in standing (from ~200th place to ~400th place).
too weak pretests these days :(
With strong prtests, we can't enjoy hacking :(
Actually, it surprised me, as I picked about 10-15 pretests in every problem. But still ,the number of cases seems to be much more than this.
Many solutions will fail system tests, but this time it was unintentional :)
Is System Test gonna take long like in the past school contests? (until the closing ceremony)
No
hack test for problem one is : 2 100 100 50
Omg, and here I failed with "-1". :D Hacked some other guy with 10^18 inputs.
terrible! I fixed some bugs on problem D and failed to sumbit in last several seconds.
Still can't go to sleep because I'm terrified of the system tests for A and B :(
Still can't go to LUNCH because I'm terrified of the system tests for A and B :(
Its B. Will it pass sys tests?
Yes, I guess.
everyone who solved 6-th COCI task of yesterday contest must solve the 4-th problem of today easily :D
Yeah. I should've read that editorial.
Anyone solved E?
I have that idea: using binary heap (aka priority queue) we sort all possible collisions of frogs by (time_to_collision, id). After that in cycle we pop first frog, kill what she could kill, update her step_size, time_to_collision and put her in the heap again (also doing this for her precessor).
Stop when the next frog in heap can't kill anyone.
Should be NlogN. But I stuck in some range checks and didn't finished the solution.
Is it correct approach?
I was thinking about the same solution, but moreover you have to update time_to_collision of previous frog (I mean the one, which gonna kill actual one).
Yea, I've considered that ("also doing this for her precessor").
In my implementation I simply put another copy of previous frog in the heap (instead of find-delete-putagain, for performance). It shouldn't affect the result, because its value will be strictly lesser than old one, so old one will be skipped somewhere in the future.
Do you think you could explain test case 18's answer for E? I've done it manually and get a different answer than the judger. ( This is my solution btw)
10 10 9 4 3 5 2 2 5 4 1 6 6 7 8 3 4 1 10 3 7 9 Participant's output 2 1 8 Jury's answer 1 8
Nevermind, it was an arithmetic error in my manual solution.
BTW, your solution seems to get TL later on. You already got 1 second on N=12500. And it could be 100000.
I expected much as I don't really make any clever observations in it. Was more expecting a TLE instead of a WA though.
It looks like the correct approach. Analysis will be published in the nearest 2-3 hours.
Information like this should be added in the main post as it is very hard to find this kind of information in the sea of comments.
Wow very fast system testing. My rank jumped from 1000 to 500's before/after system testing xD Problem A is the cause :p
And mine fall down from somewhere top80 to 366 :)
I fell down from 80 to 1500 :(
I jumped about 400 positions too
bad contest :-(
Putting "Guest From the Past" as an A problem was a wicked move.
I wish I didn't waste time on it :'(
just 699 who can solve a in the contest XD
Yea, very tricky A and obviously_correct_solution in C :)
I don't think this round had enough score differentiation. D and E should've been slightly easier, while A and C should've been switched (or C should've been made much harder, as it's unusual for so many people to get it). A wasn't actually hard, but it was pretty easy to make a silly mistake (a lot of people used it for hacks). The concept of C was roughly the same difficulty but the implementation was much easier (no derps).
The eyes... Oh my god, THE EYES!!!
What was the solution to D? I thought of some messy solutions but could not find a clean one.
Автокомментарий: текст был обновлен пользователем GlebsHP (предыдущая версия, новая версия, сравнить).
Realy A problem is tricky with Time limit and Wrong answer.
Y again in the same blog
Could someone just tell me how to solve A? It seemed that A wasn't the easiest problem :(
can do it in O(1):
implemented here: http://mirror.codeforces.com/contest/625/submission/15870223
I too thought that it should be O(1) but couldn't solve it, maybe because i freaked out because it took too much time to solve A. It was similar to this problem. I solved that problem by brute force but obviously here brute force won't work. :/ Next time I will try to find a better solution for every problem even if it gets AC.
Is's possible to resubmit an AC problem? :O
yes it is, but you lose 50 points because of resubmission.
yeah! previous submit gets Skipped, and new one will judge in system testing.
Is it any formula for O(1)? If the item costs b units and for returning you can get c units, then you can buy (n — b) / (b — c) + 1 items by n units?
574 — "A" = 1228 :(
Today I've seen a bunch of guys whose solutions failed systests for A but still they hacked everybody in their rooms so they got about 700-1000 points just from hacks. Turns out you don't have to actually solve a problem to get sufficient points for it.
Yea, its pretty usual thing for hackerfests.
I found my A is wrong when i have hacked 7 persons, finally my code is hacked but i still get 750 point..... btw, there is a guy write"cin>>n>>b>>a>>c", for which i got four times unsuccessful hack
The task are ok, but very bad for the div 2 contest.
Only the second task was on the level which it should be.
Thanks for timing!! Happy Tet Holiday!! <3 <3
Why i got WA on b??? this is my code, any help please?? http://www.codeforces.com/contest/625/submission/15862688
ababc abc
If current characters in S and T are different maybe you won't return to the begging of string T.
I didn't tested your solution, but I think this is hack case for your solution :
S='bbbc' T='bbc'.
Correct answer 1.
yes, you're right, didn't see that coming
thanks lot...
A->C, C->A
I am very interested, whether someone got full score in official, on-site contest ?
А как же разбор?
.
for D I came up with an DP solution where dp[i][j][a][b] represents the interval [i, j] can be written as the format required and current i position number is a and j position is b, a, b < 10, the solution will exceed memory limits but I fail to simplify my solution.
Plagiarism
it can take days for GlebsHP to write/translate the editorial (remember round 327). So, let's not wait for editorial and write our solutions ideas here.
Wow, outstanding performance: http://mirror.codeforces.com/contests/with/latisel
Cool, i was checking his past contest history
I expect him to do 100+ unsuccessful hacks in next round :P
Well my friend you haven't seen this:
codeforces.com/profile/bus
I think Bus Lost His Break :P
If he wanted to he could Run Over the competition
" Ops! I have a successful hack! :| " latisel says.
I guess he want to stay at Div2
Задания и тесты были полностью взяты из олимпиады 6-9 классов или переделывались под раунд CF?
Взяты без изменений
Hmmm what's wrong here? It failed at the aaaaaaa... case, where the answer is the number of a's, but my answered was one less.
codeforces.com/contest/625/submission/15869860
Array char is needing one extra cell for null character after end. Sorry if my English is bad, I try hard learning it.
Thanks for your answer! Your English is not bad at all!
please, don't say anything before the contest.
Problem set would be too easy. or Problem set would be too hard.
I suspect the test data of problem A is very weak, since 15867499 passed system test. But it should TLE at this case: 1000000000000000000 2 500000000000000001 500000000000000000
Разборы когда будут?
DO we have editorials for this one ?
Can someone help me find the problem with my O(n) B?
http://mirror.codeforces.com/contest/625/submission/15877046
I feel like it's the correct strategy implemented right... but I'm getting off by 1 on test 26.
thanks!
aaab aab
Ans should be 1. Yours gives zero
Thank you! I see the problem! Cheers. And as the_art_of_war says, the easier way is of course to just go the simple way so you can't run in to tricky edge cases like this.
I think the length of second string is special so small that you can solve it with O(n*m) using two cycles. If you want to make solution with O(n) you should use special algorithms with strings like Z-function or prefix-function.Maybe there is more easier way to get solution with O(n).
Sorry for my bad english.
Будет ли разбор задач?
Бедные дети <=9 класса, ни один международный гроссмейстер не сдал Е, им осталось только заглушки писать..
Победитель этой олимпиады Egor.Lifar (6 класс) набрал 455 баллов, причем в E он написал верное решение, но недодебагал и получил только 55 баллов. Так что не только заглушки у нас школьники умеют писать =)
Кажется, это следующий турист :)
Егор молодец, но судить о студентах по Короткевичу не стоит.
Can someone give an idea how to solve 4th one ??
Editorial is already uploaded =)
http://mirror.codeforces.com/blog/entry/23342
Three WA on Question 1 give me the way to hack 5 solutions :)
Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем GlebsHP (предыдущая версия, новая версия, сравнить).
Happy Chinese new year!Can someone tell me how to solve the A question?I see some answer:they all used (n-b)/(b-c),but I don't know why?
that is it!from others: can do it in O(1): if buying and selling a glass one is more expensive than buying a plastic one, only get plastics if not, buy glass bottles until you can't do so anymore, then buy plastics with the rest of the money implemented here: http://mirror.codeforces.com/contest/625/submission/15870223
My question is why n should minus b?My first use n,but I know I am wrong.Can you help me?
If you don't have enough money(like n<b),you can't buy a glass one. So you shoule use n-b not n,I hope you get it.
Somebody help me! What the problem with that solution? Problem B.
Consider this case:
aab abThanks!
Where is the editorial?
Here
Author of B sucks: 15924760