GlebsHP's blog

By GlebsHP, history, 7 years ago,

Hello, community!

Tomorrow Codeforces Round #342 is going to take place. It will share the problemset with Moscow Olympiads in Informatics for students of grades from 6 to 9. Though, grades from 6 to 9 in Russia usually match the ages from 12 to 15, I guarantee that everyone (even Div. 1 participants) will find some interesting problems to solve. Problems were selected for you by the Moscow jury team: Zlobober, meshanya, romanandreev, Helena Andreeva and me; and prepared by members of our scientific committee: wilwell, Sender, iskhakovt, thefacetakt and feldsherov.

Scoring distribution will be quite unusual: 750-750-1000-2000-3000.

UPD System testing is over. Here are the top 10:

Congratulation! Also, problems seemed to be too tough, we should have probably made Div. 1 round. Anyway, thanks for participating, I hope you enjoyed it and learned something new!

Thanks to romanandreev for nice analysis.

• +314

| Write comment?
 » 7 years ago, # |   +11 I am not able to register unofficially for the contest. Please fix this.
•  » » 7 years ago, # ^ |   +23 Fixed, try again.
•  » » » 7 years ago, # ^ |   +8 Working now, Thanks.
 » 7 years ago, # |   -16 Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).
 » 7 years ago, # |   +3 In the same time as Open Cup 10 stage. It's a pity.
 » 7 years ago, # |   0 Is this contest going to start at the same time of the official contest? Because otherwise it should be unrated, right?
•  » » 7 years ago, # ^ |   +23 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).
 » 7 years ago, # |   -54
 » 7 years ago, # |   +98 GlebsHP you forgot to thank yourself :)
•  » » 7 years ago, # ^ |   +54 A sentence like this ??: I thank myself for my great helps to myself in preparing this round.. :D
 » 7 years ago, # |   0 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?
•  » » 7 years ago, # ^ |   0 Click on the user profiles, and go to Problemsetting tab.
•  » » 7 years ago, # ^ |   -22 How would previous contests help ? o.O
•  » » » 7 years ago, # ^ |   0 Quoted, "It'll give a good idea as to what to expect in the contest!".
 » 7 years ago, # |   +80 Wish Codeforces a happy Chinese New Year!
•  » » 7 years ago, # ^ |   +1 I hope the Chinese New Year will bring good luck.
•  » » » 7 years ago, # ^ |   0 Of course!
 » 7 years ago, # |   +21 Nice and short announcement . Kudos to GlebsHPI guess problem statements will also be short and nice.
 » 7 years ago, # |   +3 @ 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.
•  » » 7 years ago, # ^ |   +9 Of course not. You better learn Russian. Who would think of a language switcher?!
 » 7 years ago, # |   0 Is it national level competition?
•  » » 7 years ago, # ^ |   +1 Seems to be city level.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 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 ...
 » 7 years ago, # | ← Rev. 2 →   0 why A and B has the same points ?
 » 7 years ago, # |   0 Why not a combined division contest?Great authors and of course great problems!
 » 7 years ago, # | ← Rev. 2 →   -36 A contest by new( GlebsHP ) and old( Zlobober ) coordinator.Hello Zlobober again!
•  » » 7 years ago, # ^ |   0 Why so many — votes? :)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -19 I don't know! but this contest was good for me after about 30 bad contests.(I took place 18 ;) )
•  » » » » 7 years ago, # ^ |   +7 took
•  » » » » » 7 years ago, # ^ |   -17 thanks; edited (English is my default language!)
 » 7 years ago, # |   -17 Zlobober is backed :))
 » 7 years ago, # |   +27 Great contest and perfect timing, do contest before dinner, then watching firework at mid night, happy lunar-new year.
•  » » 7 years ago, # ^ |   0 I agree with you.
 » 7 years ago, # |   +10 Its Sunday morning in my country. Is it bad if I miss church for contest ? I like contest!!!
•  » » 7 years ago, # ^ |   +499 Bless you to take part in the contest, my son.
 » 7 years ago, # |   +37 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~
 » 7 years ago, # |   +11 i will have fun before the Chinese Spring Festival dinner.
 » 7 years ago, # |   0 Luckily I won't miss the Spring Festival Gala at 20:00.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 But I think the Spring Festival Gala is becoming more and more boring
•  » » » 7 years ago, # ^ |   0 go to watch Pay New Year's call offering of bilibili at 18:00(UTC8)?..
 » 7 years ago, # |   +11 hope it will be my last div2 :D
•  » » 7 years ago, # ^ |   +10 We will miss you :) congratulations.
•  » » » 7 years ago, # ^ |   0 thanks xD
 » 7 years ago, # |   +9 happy chinese new year！！！
 » 7 years ago, # |   +1 Happy Chinese New Year(the Spring Festival) to everybody and wish Codeforces will become better and better !
 » 7 years ago, # |   +1 Happy Chinese New Year~
 » 7 years ago, # | ← Rev. 6 →   -17
 » 7 years ago, # |   +3 What is the hacking test for problem B?
•  » » 7 years ago, # ^ |   0 If the solution searches the whole string from the beginning after each time it finds the pattern.
•  » » 7 years ago, # ^ |   +3 aaabb aabb Some participants were finding string matches in O(n) but ridiculously wrong ways.
•  » » » 7 years ago, # ^ |   0 can i solve the problem B use kmp algorithm???if not ,can anyone give some advice? by the way ,happy chinese new year!
•  » » » » 7 years ago, # ^ |   0 I've solved it with KMP :)Submission
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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://codeforces.com/contest/625/submission/15858375
•  » » » » » 7 years ago, # ^ |   0 You really replace some characters with '#'! I just imagined to replace. 15874296 Although it's after the contest.
 » 7 years ago, # |   +28 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.
•  » » 7 years ago, # ^ |   -8 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.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 7 years ago, # ^ |   +3 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.
•  » » » » 7 years ago, # ^ |   +3 tnx god i am not the only one who used binary search
•  » » » » » 7 years ago, # ^ |   +1 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 :(
•  » » » » 7 years ago, # ^ |   +1
•  » » 7 years ago, # ^ |   0 You don't need to use a binary search — the answer can be found in O(1) with division. http://codeforces.com/contest/625/submission/15857590
 » 7 years ago, # |   +6 how to solve D ?
 » 7 years ago, # |   +6 Who is the author of the Problem A? >.< And tester also >_< ?? No mercy, No mercy >_< :'( :'(
 » 7 years ago, # |   -7 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.
 » 7 years ago, # | ← Rev. 2 →   0 why this work on test100000 symbols aafor 0,2 sec
•  » » 7 years ago, # ^ |   0 I tried hacking a solution like this and also failed.
•  » » 7 years ago, # ^ |   0 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?
•  » » » 7 years ago, # ^ |   0 i try to change first symbol to 'b', and it's work fast too
 » 7 years ago, # | ← Rev. 3 →   +7 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!
•  » » 7 years ago, # ^ | ← Rev. 3 →   +4 See this test baaacd aa Answer = 1. 
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +3 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
 » 7 years ago, # |   +10 I wonder how many A solutions will remain after systests :O. What was hack test for A btw
•  » » 7 years ago, # ^ |   +10 I was using this:10000000000000000001000000000000000000500000000000000000499999999999999999
•  » » » 7 years ago, # ^ |   0 Is answer 500000000000000001?
•  » » » » 7 years ago, # ^ |   +5 Yes, it is)
•  » » 7 years ago, # ^ |   0 mine was 45 30 98 89
•  » » 7 years ago, # ^ |   0 1000000000000000000 500000000000000000 100000000000000000 99999999999999999
•  » » 7 years ago, # ^ |   0 1000000000000000000 1000000000000000000 1000000000 999999999
 » 7 years ago, # |   +9 Very interesting problems. I got a lot of fun. Thanks to authors!
 » 7 years ago, # |   +4 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).
 » 7 years ago, # |   +19 too weak pretests these days :(
•  » » 7 years ago, # ^ |   0 With strong prtests, we can't enjoy hacking :(
•  » » 7 years ago, # ^ |   +21 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 :)
 » 7 years ago, # |   +3 Is System Test gonna take long like in the past school contests? (until the closing ceremony)
•  » » 7 years ago, # ^ |   +16 No
 » 7 years ago, # | ← Rev. 3 →   0 hack test for problem one is : 2 100 100 50
•  » » 7 years ago, # ^ |   0 Omg, and here I failed with "-1". :D Hacked some other guy with 10^18 inputs.
 » 7 years ago, # |   0 terrible! I fixed some bugs on problem D and failed to sumbit in last several seconds.
 » 7 years ago, # |   +4 Still can't go to sleep because I'm terrified of the system tests for A and B :(
•  » » 7 years ago, # ^ |   +4 Still can't go to LUNCH because I'm terrified of the system tests for A and B :(
 » 7 years ago, # |   -7  String gog = in.next(); String tel = in.next(); int ans = 0; int k = 0; while (k + tel.length() <= gog.length()){ String s = gog.substring(k, k + tel.length()); if (s.equals(tel)){ ans++; k = k + tel.length(); } else { k++; } } out.println(ans); Its B. Will it pass sys tests?
•  » » 7 years ago, # ^ |   0 Yes, I guess.
 » 7 years ago, # |   +16 everyone who solved 6-th COCI task of yesterday contest must solve the 4-th problem of today easily :D
•  » » 7 years ago, # ^ |   0 Yeah. I should've read that editorial.
 » 7 years ago, # | ← Rev. 2 →   0 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?
•  » » 7 years ago, # ^ |   0 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).
•  » » » 7 years ago, # ^ |   0 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.
•  » » » » 7 years ago, # ^ |   0 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
•  » » » » » 7 years ago, # ^ |   0 Nevermind, it was an arithmetic error in my manual solution.
•  » » » » » 7 years ago, # ^ |   0 BTW, your solution seems to get TL later on. You already got 1 second on N=12500. And it could be 100000.
•  » » » » » » 7 years ago, # ^ |   0 I expected much as I don't really make any clever observations in it. Was more expecting a TLE instead of a WA though.
•  » » 7 years ago, # ^ |   +9 It looks like the correct approach. Analysis will be published in the nearest 2-3 hours.
•  » » » 7 years ago, # ^ |   +2 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.
 » 7 years ago, # | ← Rev. 3 →   +6 Wow very fast system testing. My rank jumped from 1000 to 500's before/after system testing xD Problem A is the cause :p
•  » » 7 years ago, # ^ |   +4 And mine fall down from somewhere top80 to 366 :)
•  » » » 7 years ago, # ^ |   0 I fell down from 80 to 1500 :(
•  » » 7 years ago, # ^ |   0 I jumped about 400 positions too
 » 7 years ago, # | ← Rev. 2 →   -25 bad contest :-(
 » 7 years ago, # |   +2 Putting "Guest From the Past" as an A problem was a wicked move.I wish I didn't waste time on it :'(
 » 7 years ago, # |   0 just 699 who can solve a in the contest XD
 » 7 years ago, # |   +73
•  » » 7 years ago, # ^ |   +2 Yea, very tricky A and obviously_correct_solution in C :)
•  » » 7 years ago, # ^ | ← Rev. 2 →   +4 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).
•  » » 7 years ago, # ^ |   0 The eyes... Oh my god, THE EYES!!!
 » 7 years ago, # |   0 What was the solution to D? I thought of some messy solutions but could not find a clean one.
 » 7 years ago, # |   0 Realy A problem is tricky with Time limit and Wrong answer.
 » 7 years ago, # |   -21
•  » » 7 years ago, # ^ | ← Rev. 2 →   +2 Y again in the same blog
 » 7 years ago, # |   0 Could someone just tell me how to solve A? It seemed that A wasn't the easiest problem :(
•  » » 7 years ago, # ^ |   +1 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://codeforces.com/contest/625/submission/15870223
•  » » » 7 years ago, # ^ | ← Rev. 4 →   +1 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.
•  » » » » 7 years ago, # ^ |   0 Is's possible to resubmit an AC problem? :O
•  » » » » » 7 years ago, # ^ |   +3 yes it is, but you lose 50 points because of resubmission.
•  » » » » » 7 years ago, # ^ |   0 yeah! previous submit gets Skipped, and new one will judge in system testing.
•  » » » 7 years ago, # ^ |   0 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?
 » 7 years ago, # |   0 574 — "A" = 1228 :(
 » 7 years ago, # |   +10 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.
•  » » 7 years ago, # ^ |   0 Yea, its pretty usual thing for hackerfests.
•  » » 7 years ago, # ^ |   +10 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
 » 7 years ago, # |   +7 The task are ok, but very bad for the div 2 contest.Only the second task was on the level which it should be.
 » 7 years ago, # |   0 Thanks for timing!! Happy Tet Holiday!! <3 <3
 » 7 years ago, # |   0 Why i got WA on b??? this is my code, any help please?? http://www.codeforces.com/contest/625/submission/15862688
•  » » 7 years ago, # ^ |   +7 ababc abc
•  » » 7 years ago, # ^ |   +7 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.
•  » » » 7 years ago, # ^ |   0 yes, you're right, didn't see that comingthanks lot...
 » 7 years ago, # |   0 A->C, C->A
 » 7 years ago, # |   +92
 » 7 years ago, # |   +16 I am very interested, whether someone got full score in official, on-site contest ?
 » 7 years ago, # | ← Rev. 2 →   0 .
 » 7 years ago, # |   0 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.
 » 7 years ago, # |   0
•  » » 7 years ago, # ^ |   +5
 » 7 years ago, # |   +8 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.
 » 7 years ago, # |   +1 Wow, outstanding performance: http://codeforces.com/contests/with/latisel
•  » » 7 years ago, # ^ | ← Rev. 2 →   +9 Cool, i was checking his past contest history I expect him to do 100+ unsuccessful hacks in next round :P
•  » » » 7 years ago, # ^ |   +5 Well my friend you haven't seen this:codeforces.com/profile/bus
•  » » » » 7 years ago, # ^ |   +13 I think Bus Lost His Break :P
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 If he wanted to he could Run Over the competition
•  » » » 7 years ago, # ^ |   0 " Ops! I have a successful hack! :| " latisel says.
•  » » 7 years ago, # ^ |   0 I guess he want to stay at Div2
 » 7 years ago, # |   0 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
•  » » 7 years ago, # ^ |   +5 Array char is needing one extra cell for null character after end. Sorry if my English is bad, I try hard learning it.
 » 7 years ago, # | ← Rev. 2 →   +3 please, don't say anything before the contest.Problem set would be too easy. or Problem set would be too hard.
 » 7 years ago, # |   +6 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
 » 7 years ago, # |   0 DO we have editorials for this one ?
•  » » 7 years ago, # ^ |   +1
 » 7 years ago, # |   +8 Can someone help me find the problem with my O(n) B?http://codeforces.com/contest/625/submission/15877046I feel like it's the correct strategy implemented right... but I'm getting off by 1 on test 26.thanks!
•  » » 7 years ago, # ^ |   +12 aaab aabAns should be 1. Yours gives zero
•  » » » 7 years ago, # ^ |   0 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.
•  » » 7 years ago, # ^ |   +15 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.
 » 7 years ago, # |   0 Can someone give an idea how to solve 4th one ??
•  » » 7 years ago, # ^ |   +18 Editorial is already uploaded =)http://codeforces.com/blog/entry/23342
 » 7 years ago, # |   0 Three WA on Question 1 give me the way to hack 5 solutions :)
 » 7 years ago, # |   0 Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).
 » 7 years ago, # |   0 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?
•  » » 7 years ago, # ^ |   0 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://codeforces.com/contest/625/submission/15870223
•  » » » 7 years ago, # ^ |   0 My question is why n should minus b?My first use n,but I know I am wrong.Can you help me?
•  » » » » 7 years ago, # ^ |   0 If you don't have enough money(like n
 » 7 years ago, # |   0 Somebody help me! What the problem with that solution? Problem B.
•  » » 7 years ago, # ^ |   0 Consider this case: aab ab
•  » » » 7 years ago, # ^ |   0 Thanks!
 » 7 years ago, # |   0 Where is the editorial?
•  » » 7 years ago, # ^ |   0
 » 7 years ago, # |   -9 Author of B sucks: 15924760