### fcspartakm's blog

By fcspartakm, history, 23 months ago, translation, ,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #451 (Div. 2). It'll be held on Saturday, December 16 at 14:35 MSK and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!

The round is rated.

This round is held on the tasks of the municipal stage All-Russian Olympiad of Informatics 2017/2018 year in city Saratov. They were prepared by Olympiad center of programmers of Saratov SU. A convincing request to the participants of the municipal stage in Saratov to do not participate in this contest.

Great thanks to Grigory Reznikov (gritukan) and Nikolay Kalinin (KAN) for helping me preparing the contest, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform and to Alexey Ripinen (Perforator) and Roman Glazov (Arc) for writing solutions.

You will be given six problems and two hours to solve them. The scoring distribution 500-750-1500-1750-2000-2500. Good luck everyone!

UPD Editorial

UPD2 Congratulations to the winners!

• +201

 » 23 months ago, # |   +47 A friendly round for Chinese! :)But, I registered for it and it doesn't show that I'm out of competition. Why?
•  » » 23 months ago, # ^ |   +40 Fixed, thank you for the notice!
•  » » » 23 months ago, # ^ |   0 eselppa is my classmate,I dont know why he is unrated,and he cant login now?
•  » » 23 months ago, # ^ | ← Rev. 2 →   +21 Not so friendly to uni students as ICPC EC Finals will take place on 16~17/12. I guess real ACM dalaos can clear this round in 30 minutes anyways. Edit: You must be dalao http://codeforces.com/profile/eselppa
•  » » » 23 months ago, # ^ |   0 No, It's not me. It's my friend.
 » 23 months ago, # |   +65 I really think that CF had a difficult time, but at least last 3 contest had a decent queue and nice problems. I think CF is going in a right direction, mentioning the number of contests.
 » 23 months ago, # |   +14 Last week, I saw that c.f. Round 451 would be held at 18:35 MSK. Why it comes to 14:35?
 » 23 months ago, # |   +31 MikeMirzayanov , there is a clash between tomorrow's atcoder match and this , can something be done? , I dont want to miss either one of these! fcspartakm
•  » » 23 months ago, # ^ |   +36 Unfortunately, we can not move the round because of the onsite high-school olympiad and Russian AI Cup Final Round. Usually we avoid such clashes but this time we can't choose start time.
 » 23 months ago, # |   +16 Similar contests of last year:
 » 23 months ago, # | ← Rev. 3 →   -58 Nothing is mentioned related to rating.
 » 23 months ago, # |   -17 Is it -rated?
•  » » 23 months ago, # ^ |   0 It's 0.15(90)-rated one
 » 23 months ago, # |   -23 MEOWWWWWWWWWW~
 » 23 months ago, # |   +13 May as well be a nice warm-up before ECL Final :)
 » 23 months ago, # | ← Rev. 2 →   0 Will it be Sunday tomorrow in Moscow or it is just typo ?
•  » » 23 months ago, # ^ |   0 it is just typo, saturday will be in moscow tomorrow
•  » » 23 months ago, # ^ |   +15 Thank you, fixed.
 » 23 months ago, # |   -16 GOOD LUCK !!!
 » 23 months ago, # |   -29 Is this contest rated? lol
•  » » 23 months ago, # ^ |   -15 writing "lol" won't protect you from down votes
 » 23 months ago, # |   -19 Not cool it overlaps with arc tomorrow. Why so early?
 » 23 months ago, # |   -26 is it rated hahahahhahaha
•  » » 23 months ago, # ^ |   -15 lol
 » 23 months ago, # |   -24 Just curious, is that a rated contest?
•  » » 23 months ago, # ^ |   +5 Certainly
 » 23 months ago, # | ← Rev. 2 →   -36 CAn yUU please, SiR, stop deleting my "is it rated?" comments/censor me ? We live in democracy which means I can freely act like a retard , not in communism where i would be put in some gulag.
•  » » 23 months ago, # ^ |   +1 No
•  » » 23 months ago, # ^ |   +18 You have the freedom to post senseless comments, and everyone else has the freedom to vote it down into oblivion. This results in you being hidden for negative feedback.
 » 23 months ago, # |   +1 please make sure the time limit is enough
 » 23 months ago, # |   0 This is my frist contests after cet-4 , best wish for my cet-4 , besides i want to rise my points!
•  » » 23 months ago, # ^ |   0 Best wishes for us.....
 » 23 months ago, # |   +1 Hope for short statements <3
 » 23 months ago, # |   +3 When you open Codeforces for no reason and you see a contest is about to begin in 30 mins :P. I always get an email for contests saying "Attention! Unusual start time" but this time when the timing was really unusual I didn't get any email. Not cool Codeforces :(. Anyways, it's nice to see so many upcoming contests lined up before New Year."The scoring distribution will be announced later." When?!
 » 23 months ago, # |   +1 Scoring distribution please?
 » 23 months ago, # |   0 Nice time start point for me:)
 » 23 months ago, # |   -14 The round was the best for me
 » 23 months ago, # |   +1 Very nice difficulty distribution of problems.
 » 23 months ago, # |   +30 Liked the fact that there were no long queues. Keep it up.
 » 23 months ago, # |   +1 is D some directed graph problem
•  » » 23 months ago, # ^ |   +17 I think that greedy will work fine here. Remove the last alarm clock while there is at least k alarm clocks in segment.
•  » » » 23 months ago, # ^ |   0 Did you use binary search in your solution?
•  » » » » 23 months ago, # ^ |   +3 No binary search is needed. Since times are <= 10^6, you can create a vector of bools from [1, 10^6] and iterate over windows of size m to simplify implementation.
•  » » 23 months ago, # ^ |   0 D was DP+ segtree After sorting.. when u see that u are at a time ti such that there are >=k alarms within time ti-m+1, just turn of the ith alarm. maintain the sum using segtree
•  » » » 23 months ago, # ^ |   +20 If you use a sliding window, you don't need a segtree.
•  » » » 23 months ago, # ^ |   +1 I've solved D with FFT and made some optimizations to pass the TL.
•  » » » » 23 months ago, # ^ | ← Rev. 3 →   0 How did you do it with FFT?
•  » » 23 months ago, # ^ |   +3 Greedy on time and sliding window may help you.
•  » » 23 months ago, # ^ |   0 I did not have time to solve but I think we need to slide the duration of span from the starting of the alarm to ending alarm and if anytime we have at most k alarms, then we need to cleverly turn them off. I am not sure could be a DP problem.
•  » » 23 months ago, # ^ | ← Rev. 3 →   +5 I think problem D is two pointers + data structures
 » 23 months ago, # |   +4 How to solve F?
•  » » 23 months ago, # ^ | ← Rev. 3 →   +6 If the length of c is n, the maximum length of a and b is n or n - 1. With each possible length of c, we only need to check for 2 cases.To calculate a, b, c in each case, we can use Hash. The hash value of a + b is the sum of hash value of a and the hash value of b.And remember to check if there is some 0 at the beginning of a, b, c when the length of a, b, c is greater than 1.
•  » » » 23 months ago, # ^ |   +8 Can you please explain, how are you using hashing? I am not aware about the concept of hashing. Also, how can you say the hash value of (a + b) is the sum of the hash value of a and the hash value of b? Thanks.
 » 23 months ago, # | ← Rev. 2 →   +1 How to solve problem D?I thought of segment tree solution but was unable to get it accepted. :(Edit - My basic idea was to assign 1 (in the array) to the minutes when alarm clock rings and in each iteration, find the sum from i to i + m minutes, say it p.If it is less than k, then no problem. Otherwise update the array from range L to i + m and make each element in it 0. It can be done by lazy propagation and about finding that value L (from where we have to update the range) , it can be done by simple binary search.Can anyone tell me, what I was missing or was I wrong with my logic?
•  » » 23 months ago, # ^ |   0 I solved it using BIT tree. Just maintain at each index how many clocks are there and while checking for any time i just see the number of clocks present between i and i+m time interval and if it is greater than or equal to k just update index i+m with negative value equal to abs(val[i+m]-(k-1)).
•  » » » 23 months ago, # ^ |   0 django28..I believe I have done exactly the same but just used segment tree instead of BIT like you.
•  » » » 23 months ago, # ^ |   0 Can you have a look at my code and tell me what I did wrong?
•  » » 23 months ago, # ^ |   0 I think it's somewhat greedy but not sure about that!What i did was that first make an array of alarm point(as there are only 1e6 alarms and all distinct!) and then take a window of size m and if it contains more than k then i start removing from last on alarm(as removing this makes sense and help to optimize our answer for the next step). Finally slide the window and calculate the number of alarms thus removed.
•  » » 23 months ago, # ^ |   0 you can check this out!
 » 23 months ago, # | ← Rev. 2 →   0 Hints for D? I was thinking binary search but am not sure and couldn't get it to pass
•  » » 23 months ago, # ^ |   0 binary search + BIT maybe
•  » » 23 months ago, # ^ |   +6 A sliding window algorithm. And remember the greedy strategy, its always the best to turn off the last alarm clock.
•  » » » 23 months ago, # ^ |   0 Ohh allright thanks!
•  » » 23 months ago, # ^ |   0 sliding window
•  » » 23 months ago, # ^ |   0 I was also thinking about it for a while, but I don't know how can we check in O(n) that we can choose alarm clocks so that they don't intersect too much.
 » 23 months ago, # |   -6 How did people manage to solve D in 5 minutes? =)Is it some kind of a standart problem?
•  » » 23 months ago, # ^ | ← Rev. 2 →   +7 A sliding window algorithm did it for me. Hope it passes the systests.UPD: It did. XD
•  » » » 23 months ago, # ^ |   0 I know what sliding window is, but I don't know how to solve this problem.
•  » » » » 23 months ago, # ^ |   +1 use greedy technique for that. Delete last alarm clock.
•  » » » » » 23 months ago, # ^ |   0 Why is it correct to delete the last one?
•  » » » » » » 23 months ago, # ^ |   0 Because if another alarm clock intersects with the previous ones, it's better to remove an alarm ending at an earlier time instance compared to one ending later.
•  » » » » » » 23 months ago, # ^ |   +7 Cause, that will help the most. The first alarm clock will be the first one to leave the span of m minutes. So, there may be a case that there exists exactly k-2 alarms in the range starting from last alarm clock.
•  » » » » » » 23 months ago, # ^ |   +7 Cause that clock will be part of more up coming window.
•  » » » » » 23 months ago, # ^ | ← Rev. 2 →   0 EDIT: Fixed
 » 23 months ago, # |   0 I really liked tasks of this contest, interesting and intriguing
 » 23 months ago, # |   +36 This round is true Div.2 round: when most of the problems are solvable for Div.2 participants.
 » 23 months ago, # |   +8 Why change the statement and not send a annoucement???? consequence -> consecutive Consequence ??? How can i know this...
 » 23 months ago, # | ← Rev. 3 →   +2 Hey, this submission(33299805) says runtime error...while checking with Diagnosis in custom test, its says, p71.cpp:57:24: runtime error: member access within misaligned address 0xbebebebe for type 'trieNode', which requires 4 byte alignment 0xbebebebe: note: pointer points here
 » 23 months ago, # |   +3 Lol, can someone(MAYBE CF ADMINISTRATION) explain me why I cant hack one submition twice?I hacked once and got an "Invalid input" because of the EOL in the end. After I corrected my test CF says "Submit already challenged". LOL, REALLY??? So then I must know if the EOL is needed there before hacking???? Due to this issue I didn't get 200 points on hacks. THX, CF.
•  » » 23 months ago, # ^ |   0 So then I must know if the EOL is needed there before hacking???? Yes.
•  » » » 23 months ago, # ^ |   +3 So why it is not mentioned on the hacking page, hah?
 » 23 months ago, # |   +3 What is testcase 7 in F ???
•  » » 23 months ago, # ^ |   0 Did you check for 0s at the beginning of a, b, c if their lengths are greater than 1?
•  » » » 23 months ago, # ^ |   0 Yes
 » 23 months ago, # | ← Rev. 2 →   +1 EDITEDIn Problem-E, my first submission got WA in pretest 9. But, then I relocated my long long ans = 0 variable at the top of main function and got pretest passed after submitting. Why did that happen? I was looking for the bug for such a long time, maybe like 30 minutes. Then I just gave up and then did the above thing on a whim and got accepted. but why?
•  » » 23 months ago, # ^ |   0 declaring long long ans in main might have garbage value. oustide main is 0
•  » » » 23 months ago, # ^ |   +2 I wrote long long ans = 0;
•  » » 23 months ago, # ^ |   0 maybe you did ans += something; before there is any value on ans, the value of ans before declared, inside main is random, CMIIW
•  » » 23 months ago, # ^ |   0 You also changed your comparator function.
•  » » » 23 months ago, # ^ |   +1 The change in comparator function looks insignificant to me. Either way, the sorting will be the same
•  » » 23 months ago, # ^ |   0 i missed it and declare ans to int. got wrong ans on testcase 9 and didnt even bother to check it.
 » 23 months ago, # |   0 Is greedy work for problem E?
•  » » 23 months ago, # ^ |   +9 Yep. It is greedy.
 » 23 months ago, # |   -30 It is rated?
•  » » 23 months ago, # ^ |   +35 Near perfect conduction of an announced rated round. Why even bother asking?
•  » » 23 months ago, # ^ |   0 hmm people are saying that
 » 23 months ago, # |   0 I am getting Wrong answer on pretest 8 for 2nd problem (B) My submissionCan someone please help? I used the Extended Euclid algorithm to solve it.
•  » » 23 months ago, # ^ | ← Rev. 5 →   0 There is another "NO" case.Suppose "X" is non-negative and "Y" is negative.You obviously want to make "Y" non-negative by subtracting numbers from "X", right? Here, there is a possibility of making "X" negative even though you manage to make "Y" non-negative. In short, "X" and "Y" cannot be both non-negative in this case.
•  » » » 23 months ago, # ^ |   0 I solve that case looking for minimal non-negative "Y" in O(1) and thus checking non-negativity of "X"
 » 23 months ago, # |   +11 Speed up this system testing, I can't wait to see how many problems will fail from the 6 : |
•  » » 23 months ago, # ^ |   +7 Speed up this rating updates, I can't wait to get my new COLOR xD
 » 23 months ago, # |   +36 Very Good Contest! Great thanks to the author!
•  » » 23 months ago, # ^ |   0 hmm refreshing
 » 23 months ago, # |   +3 I got some issues hacking. From the second hack, it always navigates to the hack summary page without the hack popup where I can enter my hack case. So I am not able to hack others in the same browser. I have to switch to a different browser or use a different computer. Did it happen to others?
•  » » 23 months ago, # ^ |   0 Same Issue. Annoyed me a lot !! -_-
 » 23 months ago, # |   0 My solution (33309422) for problem C gets wrong answer on pretest 1. Whats wrong here ?
•  » » 23 months ago, # ^ |   +15 You have to print how mnay lines of output you have
•  » » » 23 months ago, # ^ |   0 Thanks. I feel so terrible for such a silly mistake...
•  » » » » 23 months ago, # ^ |   0 It happens to all of us at some point; if you ever see a problem with a VERY early pretest (like 1, 2, or 3), you can use the fact that CF will judge the example test cases as the first pretests (at least in my experience they always have). So if you fail test 1, you can diff check with the sample output and find out that you have a formatting error.
•  » » » 23 months ago, # ^ |   0 Yep, I too didn't do that in my first attempt! Got a WA. :/
•  » » » » 23 months ago, # ^ |   0 I too got a WA in C for that!
 » 23 months ago, # |   0 can someone please look into my code why it is giving RE on sample test(3).
•  » » 23 months ago, # ^ |   +32 One doesn't simply code trie when the string lengths are  ≤ 10.
•  » » » 23 months ago, # ^ | ← Rev. 3 →   0 yeah but i have wasted a lot of time in it! please help.btw i didn't think that trie is making problem it's only when we have a string of length 1. if i remove all those then it runs fine. And when there are string of length 1 then builder is not working correctly. please help!
 » 23 months ago, # | ← Rev. 4 →   -20 UPD: I have changed my MIND.. if you want to downvote me then you are welcome :)
•  » » 23 months ago, # ^ |   +2 Wow, how did you find that?
•  » » » 23 months ago, # ^ |   0 May be I was lucky :D
•  » » » » 23 months ago, # ^ |   +7 Damn, you must be really lucky and skilled to find those 2 submissions!
•  » » 23 months ago, # ^ | ← Rev. 2 →   +17 Lol. They're the same submissions. Think for a moment before slinging mud on others.
•  » » » 23 months ago, # ^ | ← Rev. 2 →   0 submission link is updated.
•  » » » » 23 months ago, # ^ |   0 I still don't find them similar.
•  » » 23 months ago, # ^ | ← Rev. 3 →   +14 lol. Didn't even bother to change submission idEdit: codeforces saves all revisions you know :PEdit2: looks sufficiently different to me
•  » » 23 months ago, # ^ |   0 submission link is updated.
•  » » » 23 months ago, # ^ |   0 those submissions aren't similar at all.
 » 23 months ago, # |   0 IS O(sqrt(ai)*n) sufficient to pass the tests in problem E ??
•  » » 23 months ago, # ^ |   +3 sqrt(ai) ~= 3.16*10**4 (max)n = 2*10^5 (max)no of steps ~= 6.3*10**9extremely low chance of passing, unless the constant factor is really low
•  » » » 23 months ago, # ^ |   0 Because I've seen many solutions pass the tests even though they used O(sqrt(ai)*n) solutions !!..
•  » » » » 23 months ago, # ^ |   0 link please?
 » 23 months ago, # | ← Rev. 2 →   +28 I think the diagnosis process makes the system test so slow. But I am pretty sure that many of the contestants do not or less care the diagnosis result. So this is just my small suggestion, what about running the diagnosis only when the contestant wants? For instance, by clicking run diagnosis button on submitted code. This may reduce the server load a lot, making system test faster, and contestants can know their ratings earlier, which most of the contestants care about. Can I share your opinion?
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 Are you sure the diagnosis is even running? I could not see diagnostics after WA (on pretests and when submitting now)
•  » » » 23 months ago, # ^ |   0 33314427Maybe WA does not run the diagnosis.
•  » » » » 23 months ago, # ^ |   0 originally the blog said, it would run for WA and RTE, but seems so
 » 23 months ago, # |   +75 My first Div.3 contest!
 » 23 months ago, # |   0 shitty round
 » 23 months ago, # |   +12 Good contest, comprehensible statements, short systest pending time.Many thanks, although I lost my perfect chance to solve the last problem for the first time, just because I forgot checking the leading zeroes :<
 » 23 months ago, # |   +1 the E task should be D or even C
 » 23 months ago, # |   +89
 » 23 months ago, # |   0 Can anyone plz point out my mistake in E, I wrote a pretty easy solution- http://codeforces.com/contest/898/submission/33306957Thanks
 » 23 months ago, # |   0 My solution for D gives runtime error on testcase 3 but runs fine on my system http://codeforces.com/contest/898/submission/33302108 Help please!!!
•  » » 23 months ago, # ^ |   0 changed int to long long as suggested by someone... still it gives runtime error :(
•  » » 23 months ago, # ^ |   0 Hi, I think your problem is that you're doing ss.erase(it1) and then using it. "Iterators, pointers and references referring to elements removed by the function are invalidated." I didn't test it but I think that is the problem, hope it helps!
•  » » » 23 months ago, # ^ |   0 yes, you are right. auto it2=it1; it2--; ss.erase(it1); it1=it2;` worked fine.
 » 23 months ago, # | ← Rev. 2 →   0 For problem C I think my output for the first test case is correct ,can anyone tell me why my first test case output is wrong.
 » 23 months ago, # |   -16 I really don't think this round is good. The rates of algorithms used in the contest are not in equilibrium. 3 problems(ABC) don't need any skill or algorithms, and C is just grand-grand-great simulation. And 2 problems(DE)are just greedy, which doesn't need advanced algorithms. Even DP and graph theory don't exist in problems. And the quality of the problems aren't high as well, here "quality" means the well-situated difficulty for Div. 2. (Because I can only AC around 2 problems before, but this time I can do 4 if I have a little more time)
•  » » 23 months ago, # ^ |   +28 I'm beginner and I'm glad to see such problems like A or B. No one in the entire world started walk right after birth. Those problems actually makes me think that I can solve more then just 1 or 2 problems in the next contest. And yeah, it keeps me motivated, and don't give up from CP. If the contest was too easy for you, move to div1 and try to beat tourist:)
•  » » » 23 months ago, # ^ | ← Rev. 3 →   +3 Actually I don't think the round is too easy for me. As what I said, I can do 4 if I have enough time. I am still far from AK(solving all). But I just think it's much easier than most of the div2 contest before:) Maybe the round still has an advantage that it gives us encouragement. Maybe what I said in the last discussion is not fit, so I pay apologize about it. But if all of the div2 contests on codeforces are "encouraging rounds", what will it be like?
 » 23 months ago, # |   +1 Can someone discuss their F solution ?
•  » » 23 months ago, # ^ |   +1 Editorial is already published
 » 23 months ago, # |   0 Good work! Very interesting tasks.
 » 23 months ago, # |   +1 %zu printf specifier is not recognized... this cost me an accept in C :(
 » 23 months ago, # |   +1 For Question B, if we do brute force according to editorial, we will get TLE on test 49 for Python...
•  » » 23 months ago, # ^ |   +1 Did you try PyPy?
•  » » » 23 months ago, # ^ |   +1 oh yes now it passes!! Thanks so much!! So next time I want to submit Python code I should use PyPy as it runs much faster?
•  » » » » 23 months ago, # ^ | ← Rev. 3 →   +1 Yes. But there is some difference in Python and PyPy.So read the docs.
 » 23 months ago, # |   +1 Hey guys, I didn't do well yesterday because I was stuck on Problem C for a long time. I used std::set to store the telephone number, and I iterated the set to check if they were suffix to each other, and I delete the elements while iterating and I got runtime error. Can anyone please tell me how the set works while erasing the elements. Thanks a lot.
•  » » 23 months ago, # ^ |   +7 I was getting the same error . So instead of deleting unrequired elements just store answers in some ans vector and output them later . For the error see thishttps://stackoverflow.com/questions/2874441/deleting-elements-from-stl-set-while-iterating
•  » » » 23 months ago, # ^ |   0 Thanks for the website, it really helps. I used a vector to store the elements should be erased and delete them later to pass the problem during the test, it's another solution.
 » 23 months ago, # |   0 For Problem F,I use unsigned long long without modulo (let the hash overflow naturally) and Rabin-Karp Algorithm to check whether the answer is ok,the verdict shows TLE on test 77.However,if I add a modulo which is only 23333 (only about 2e4) and use the same way to check,it got accepted in only 78ms.So can I assume that you intend all the hashing algorithm without modulo to fail?I don't think it's good for a hashing problem,especially when I use Rabin-Karp to check and it still can't pass.:D
•  » » 23 months ago, # ^ |   0 I think, during the contest someone passed pretests with overflow hash and someone just hacked this solution, as a result a counter-test for overflow hash was added in the final test set.