### Vovuh's blog

By Vovuh, history, 4 weeks ago, translation, ,

<copy-pasted-part>

Hello!

Codeforces Round #535 (Div. 3) will start at Jan/23/2019 17:35 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

UPD: I also would like to thank testers ismagilov.code, Nebuchadnezzar, Arpa, filippos, eddy1021 for the great help in round preparation!

UDP2: I don't sure about Iamoni so I included top-6 instead of top-5 in the table. And I'm also don't sure that some hackers aren't cheat so forgive me if my information is wrong.

UPD3: Editorial is published!

Congratulations to the winners:

 1 b31quocbao 7 358 2 GZY_AK_IOI 7 455 3(?) Iamoni 6 101 4(3?) pushkar12 6 216 5(4?) _DarkDawn_ 6 226 6(5?) Amooo 6 229

Congratulations to the best hackers:

Rank Competitor Hack Count
1 _bacali 181:-49
2 Chiakisa 55:-8
3 CNH_NHI 10:-1
4 CutieRabbit 9
5 CNH_NSIS 8
378 successful hacks and 348 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A spacewanker 0:01
B mpstxdy 0:03
C Iamoni 0:06
D arpit040199 0:06
E1 Iamoni 0:11
E2 TsingTaoDaTieWang 0:16
F Zhao-L 0:20

•
• +135
•

 » 4 weeks ago, # |   0 I hope its not like..DIV2
•  » » 4 weeks ago, # ^ |   +1 Maybe a Div3 = Div1 + Div2 ....
•  » » » 4 weeks ago, # ^ |   +11 More like Div3=Div2-Div1...
•  » » » » 4 weeks ago, # ^ |   -17 Let's Increase it's value a little Div3 = (Div2 — Div1) * 1.5; ;)
 » 4 weeks ago, # |   -27 i hope it won't have any useless and pointless math involved...also may i ask will it rate my rating?
•  » » 4 weeks ago, # ^ |   +4 The contest will be rated for you as long as you're under 1600 (now you're 1599). If you took part in today's contest and it will raise your rating — the next Div. 3 won't be rated for you. Half of your comments are complains about maths :D I don't agree with your statement that maths has nothing to do with programming. It has a lot, especially with competitive one. All of the algorithms (e.g. graph theory) come from mathematics. Try to deal with it if you want to have fun from Codeforces.
•  » » » 4 weeks ago, # ^ |   -19 what are you talking about i am expert
•  » » » » 4 weeks ago, # ^ |   +1 I wrote my comment before the contest results appeared and you was 1599. Now you're an expert, right. Congratulations!
•  » » » » » 4 weeks ago, # ^ |   -13 thanks i feel really great now
 » 4 weeks ago, # |   +5 Round by Vovuh !! Always exciting to participate!
 » 4 weeks ago, # |   0 Wish a lot of AC <3
 » 4 weeks ago, # |   +2 Div3 contest is like a gift for contestants below 1600.
 » 4 weeks ago, # |   +11 Announcement of Codeforces Round #299 (Div. 2)?
•  » » 4 weeks ago, # ^ |   0 Fixed now, I think :)
 » 4 weeks ago, # |   0 Perfect announcement doesn't exi...
 » 4 weeks ago, # |   +7 [Off Topic] I am trying to practice on my hacking skills for the next contests. Is there any good blog post about how to approach hacking effectively? Some sort of guidelines/best practices on how to hack solutions.I searched but couldn't find any
 » 4 weeks ago, # | ← Rev. 2 →   +77 Step 1 : study for examStep 2 : participate in Cf roundStep 3 : loose 100 rating points because your mind was tired from studying Step 4 : fail the exam because your mind became even more tired after trying to solve problems
•  » » 4 weeks ago, # ^ |   +13 problems are easy in Div3, today I'll be in TOP 20
 » 4 weeks ago, # |   +3 Is div3 friendly to new people?
•  » » 4 weeks ago, # ^ |   +18 Yes, it's without a doubt the best contest new people can choose. But it doesn't mean it will be easy. If you have no or little experience in competitive programming, doing 2 or 3 problems will be a quite good result. Good luck.
 » 4 weeks ago, # |   +38 Is vovuh nephew of Mike Mirzayanov? Why does he take every single Div3 Round?
 » 4 weeks ago, # |   +1 Does it mean that participants with 1600 higher rating taking part in Div.3 would not be rated ?
•  » » 4 weeks ago, # ^ |   +1 Exactly. We can take part just for fun.
•  » » » 4 weeks ago, # ^ |   +7 Oh that's amazing! Thanks a lot!
 » 4 weeks ago, # |   0 Another div 3 round, which is equal to div 2. In any case, thanks for the prepared problems. Good luck, have a fun. Take care of your feet
•  » » 4 weeks ago, # ^ |   0 You also take care <3
 » 4 weeks ago, # |   -19 Yet again disappointed by weak pretests >:(
•  » » 4 weeks ago, # ^ |   +49 Sorry, I tried to make strong tests in almost all problems and just forgot about you! The only tests among your solutions are in the problem B with answers 69 and 42 :(
•  » » » 4 weeks ago, # ^ |   0 Bro just do it like a normal CF Round... please drop that 12-hour open hack feature.
•  » » 4 weeks ago, # ^ |   0 All of your solutions are hacked.Because "if(n==69)return 0;".
•  » » 4 weeks ago, # ^ |   0 Why are you putting if(n==69) return 0; Your all solution are hacked @problem_destroyer420
 » 4 weeks ago, # |   +5 swap(C, D)
 » 4 weeks ago, # | ← Rev. 2 →   0 C && D giving TLE in java wow in-spite being O(N) =_=
•  » » 4 weeks ago, # ^ |   0 Changing the string to char array gives AC WOW! okay -
•  » » » 4 weeks ago, # ^ |   +7 String objects are immutable, which means ans+='B' requires creating a brand new String object and copy all characters, then append 'B' to it.
 » 4 weeks ago, # |   0 how to solve E2
•  » » 4 weeks ago, # ^ |   +3 i think this solution is right though i couldn't find an apropriate implementation that fit in time and memory limit for it...first you have to prove that the answer is when you choose the segments that doesnt intersect whith the maximum element.now you can fix the element that shoud be the maximum and apply all the segments that doesn't intersect with this element and get the minimum,this can be done using segment tree
•  » » » 4 weeks ago, # ^ |   0 I did that in E1 , assumed that each element is a maximum and chose the segments that don't affect that number However I don't know how to do it in E2 time limit how can it be done using segment tree ?
•  » » » » 4 weeks ago, # ^ |   0 you have to use minimum segment tree.but for the precise implementation,i couldn't get the accept for the problem,i fix the time limit problem by just a little spitting on my code,but that one agian couldn't fit in memory
•  » » » » » 4 weeks ago, # ^ |   +1 My implementation with segment tree : 48837273
•  » » » » » » 4 weeks ago, # ^ |   0 yes,you used the sweep line trick that i didn't and because of that i couldn't get the accepted
•  » » » » » » » 4 weeks ago, # ^ |   0 Segment Tree is to slow to fit tle
•  » » » » 4 weeks ago, # ^ |   +5 We do not need a segment tree here, check it out for my solution: https://codeforces.com/contest/1108/submission/48881765 HintLet min is the index of minimum in the array b, and in a we try to minimize a[i] as much as possible. So where to choose the maximum index: max ?First thing we observe is that we should not decrease the max index in the array a. Proof : if we choose the range that contains both max and min then it makes sense not to choose it, else if we choose the range that contains only max, not min then it is wiser not to choose them.So if we choose a set(possibly empty) of given ranges that cover the min, we shold choose the max from the left of the array a: either from the prefix [1..l] or the suffix [r+1...n] since the set of ranges we choose all have at least one point in common, which means they form a big, continuous range [l..r]. Consider that the maximum choose from the suffix. Assume that ranges are sorted according to the end bound.So for each min = 1..n, we choose the set of ranges in the way that expand to the end of the array. Suppose the set we are considering has X ranges and cover to the r-th element of a, then we take the maximum of our current answer and:maxright[r+1] — (a[min] — X).Same kindof process for choosing max from the prefix. Remember to check the corner case of empty set.
 » 4 weeks ago, # |   +5 Testcase 26 Problem F?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +4 4 41 3 11 4 1001 2 1002 3 1In my opinion answer should be 0Even i did not manage to find how to solve
•  » » » 4 weeks ago, # ^ |   +4 You can see my submission. You can understand easily from the code itself. What I have done is processed the edges after sorting by weight and did a simple DSU.
•  » » » » 4 weeks ago, # ^ |   0 I was trying to see the components in a single iteration. Thanks for the reply :)
•  » » » 4 weeks ago, # ^ |   0 https://codeforces.com/contest/1108/submission/48833560 i got WA on test 26 any help or test case
•  » » » » 4 weeks ago, # ^ |   0 Try this6 71 2 92 3 91 3 93 4 14 6 24 5 25 6 9answer would be 1 i thinkyou are getting 0
 » 4 weeks ago, # | ← Rev. 2 →   -6 Need help on C. I don't know what I did wrong.https://codeforces.com/contest/1108/submission/48833951BTW any recommendation for E1,E2 and F???//swap(D,C). and maybe even swap (D,B). I lost 50 mins on C and just read D and like "Uh what???"
•  » » 4 weeks ago, # ^ |   0 Same feelings, bro :(
•  » » » 4 weeks ago, # ^ |   -18 You know how can I solve C afterward?Brute force the solution got AC bro lol
•  » » 4 weeks ago, # ^ |   0 Simply try "RGBRGB..." "RBG" "BRG" "BGR" "GRB" "GBR" and find the minimum among these choices.
•  » » » 4 weeks ago, # ^ |   -16 That's what I did after I got WA hahaHonestly speaking, as a C, it sucks though. I mean, brute force get AC but "proper thinking" solution got WA????I think if the problem setter change the distance and amount of number to 5, it will be better
 » 4 weeks ago, # | ← Rev. 2 →   0 So it's my first time to see a problem which has two types in Codeforces.(And I haven't solved it/them.:D It should be an easy problem though..)
 » 4 weeks ago, # |   +6 I don't know about you guys but 12-hour phase of open hacks is certanily the only thing I don't like about this Div.3 contest, why don't you leave that feature for Educational Rounds only ??? You can downvote me, I don't care about that, but I have to say it... is painful.
•  » » 4 weeks ago, # ^ |   0 But this is really helpful to improve your skills.I think that Codeforces is a site to help you improve your skills, ratings is not the only thing right?
•  » » » 4 weeks ago, # ^ |   0 Ok, but regular CF rounds allow you to hack as well, my opinion is that it would be better to leave the 12-hour phase of open hacks for Educational Rounds only and let this div. 3 rounds more like the regular div. 2 / div. 1 rounds. Again is just my opinion. Happy codings to all :P
 » 4 weeks ago, # |   0 Can somebody tell me what's wrong with this code on problem E2?My submission
 » 4 weeks ago, # |   0 https://codeforces.com/contest/1108/submission/48801874 i find new thing one of the guy is submitting right solution expect for case n == 69 and he is hacking with another account . please report this user and please dont allow this to happen in future the user is @problem_destroyer420
 » 4 weeks ago, # |   0 I did try to solve the problem E1 using DP. but I did not solve the number of segment T^T...
 » 4 weeks ago, # |   +5 Am I the only one who felt today's Div3 first 3 problems are more difficult than yesterdays Div2 first 3 problems?
•  » » 4 weeks ago, # ^ |   0 I would say that the diffucult is about the same.
 » 4 weeks ago, # |   +3 How to solve E2?
•  » » 4 weeks ago, # ^ |   0 For every index of the array assume that it is not affected by any of the M updates. Apply all the other updates which don't affect that index and calculate the answer i.e. max — min.
•  » » » 4 weeks ago, # ^ |   +3 how to do that in E2 time limit
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +9 Apply all the queries to the given array initially. Now you can do a sweepline on the updates based on which index they appear and which index they disappear. Submission
•  » » » » » 4 weeks ago, # ^ |   0 Apptica what u mean by sweep line , how u used it . can u provide me its tutorial
•  » » » » 4 weeks ago, # ^ |   +6 You can use sweep line technique. Iterate i from 1 to n, for each i subtract all segments [i, j], then calculate. After calculating, add all segment [j, i] so that next i won't use old segments.
•  » » » » 4 weeks ago, # ^ |   +7 Check all indices in increasing order. For each index, check all the segments and find if the index is the start of the segment. If it is, then subtract 1 from all elements in the segment, and re-calculate min and max and update the answer. Check all the segments again and see if the index is the end of the segment. If it is, then add 1 to all elements in the segment.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 3 →   +1 Can you explain in some detail why it works? Is it because you are trying to depress the value of the ith element as much as possible, and the highest element e such that e-a[i] gives the max answer can either be a part of that segment or not, if it is not a part you gain one, if it is you dont lose anything since both get devalued by 1? Please correct me if I am thinking of something wrong
•  » » » » » » 4 weeks ago, # ^ |   +5 Basic principle is to make each element as small as possible. So for each element, you're going to subtract 1 from all segments including that element.If you check indices in increasing order, the only segments you need to check are the ones you enter or leave. This guarantees that when check an index, all segments including that element has already subtracted while others are not.
•  » » » » » » 4 weeks ago, # ^ |   0 Yes, exactly.
•  » » » 4 weeks ago, # ^ |   0 Yeah, I solved E1 with that observation. But that gets TL for E2.
•  » » » » 4 weeks ago, # ^ |   0 no you didn't, stop lying!
 » 4 weeks ago, # |   -34 contest was so easy :D
 » 4 weeks ago, # |   0 Anyone tell me what happened with my solution. I just change string color = "GRB" code (WA on test 4) to color ="BGR" code and got AC?
•  » » 4 weeks ago, # ^ |   +1 next_permutation needs your passed array to be in sorted order, RGB is not sorted, but BGR is
•  » » » 4 weeks ago, # ^ |   0 That's not true next_permutation prints all the remaining permutation till RGB but as GRB comes after BGR in permutation so it skips it, so if you are thinking that next_permutation won't work if your string/array isn't sorted then you are wrong!Happy coding!!
 » 4 weeks ago, # |   0 what's the dp solution for probD?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 State: dp(index, prev_letter) Transition: if(prev_letter != cur_letter): dp(index, prev_letter) = dp(index+1, cur_letter); else iterate i over ['R', 'G' and 'B'] and i != prev_letter: dp(index, prev_letter) = minimum_of ( 1 + dp(index+1, i) ) ; Please check my solution for more clearity.
 » 4 weeks ago, # |   0 can anyone tell why my code https://codeforces.com/contest/1108/submission/48851718 for problem https://codeforces.com/contest/1108/problem/E1 shows wrong answer on online ide while it give correct answer in sublime text??
•  » » 4 weeks ago, # ^ |   +4 Your int x in line 63 is uninitialized in those min/max functions.
•  » » » 4 weeks ago, # ^ |   0 OK Thanks
 » 4 weeks ago, # | ← Rev. 4 →   0 What is the intended sol in E2? Segment tree with lazy prop didn't pass for me. (tle #15)UPD — AC. Missed to apply sweep line on updates.
 » 4 weeks ago, # |   0 Someone can explain me why my position in standings changes after refreshing the page? Which of these is the official one?
 » 4 weeks ago, # |   +3 Hello guys :) cheaters: same code https://codeforces.com/contest/1108/submission/48814895 -> https://codeforces.com/contest/1108/submission/48841216
•  » » 4 weeks ago, # ^ |   +2 One code was sent after the end of contest.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Is notice helpful? because two of my friends are always cheating. Would anyone ban them or something?sorry for bad English.
•  » » » 4 weeks ago, # ^ |   0
 » 4 weeks ago, # |   0 Can anybody tell me what is wrong with my E?I tried greedy + segtree.Like if you want to have ai as the maximum after applying the subset of intervals applying intervals that contained ai would not help and applying intervals that do not contain ai would not damage, so I just iterated over i and do the updates :P
•  » » 4 weeks ago, # ^ |   0 Your idea is right. I think there're some mistakes in you code.
•  » » » 4 weeks ago, # ^ |   0 Can you please help me find what is wrong ?
•  » » » » 4 weeks ago, # ^ |   0 I'll send you a private letter.
 » 4 weeks ago, # |   0 Can anyone explain problem F a little , I mean the sample test case 1.
•  » » 4 weeks ago, # ^ |   0 Initially, two kinds of MST are possible. Both uses edges (3,7), (4,8), (1,2), (1,4), (2,3), (3,5). One possible MST uses edge (1,6) while the other uses edge (3,6).If you increase the weight of edge (1,6), then the only MST possible now is the one that uses (3,6). Same for increasing the weight of edge (3,6) where only the MST using edge (1,6) remains.If you're not familiar with MST, you'd better search for it first.
•  » » » 4 weeks ago, # ^ |   0 Thanks, now I understood the question :)
 » 4 weeks ago, # |   +1 in B, can answer to test case4 9973 1 9973 1be 9973 9973 ?nowhere it is mentioned x!=y. this solution satisfies all conditions in question.
•  » » 4 weeks ago, # ^ |   0 Yes, it can be.
 » 4 weeks ago, # | ← Rev. 2 →   +26 Thanks Vovuh for this nice contest. Questions were well constructed and difficulty was also gradual :)
•  » » 4 weeks ago, # ^ |   0 *Questions were
•  » » » 4 weeks ago, # ^ |   0 Thanks for POINTING THAT OUT :(
 » 4 weeks ago, # |   0 Hi guys, i work in c++ gnu g++14. I have a problem with task B. All my solutions when tested by me output correct answers but when i submit them, program always output "0 0". Any idea why is this happening ?
•  » » 4 weeks ago, # ^ |   0 You should only use one I/O library (C or C++) after using ios_base::sync_with_stdio(false);. i.e. using only cin or using only scanf.
•  » » » 4 weeks ago, # ^ |   0 Thank you, i"ll read more about it on internet.
 » 4 weeks ago, # |   +4 copying alert : The submissions of the a/c LightningFrenemy213 and arpan_dg are identical.
 » 4 weeks ago, # |   0 How to solve E1 ?
•  » » 4 weeks ago, # ^ |   0 For every index in the array, apply every query that doesn't include that index, to the original array and calculate the difference (max-min).
•  » » » 4 weeks ago, # ^ |   0 smart ty :D
•  » » » 4 weeks ago, # ^ |   +1 How ? Any reason for this approach
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 What you're doing with this approach is just checking the final states of the array when that particular index is not included in any query that you've applied. There will always be a case when the difference between max — that index element and min — calculated after applying the queries, will be maximum.This is one approach, there might be other approaches to solving this problem.
 » 4 weeks ago, # | ← Rev. 2 →   0 why this solution got accepted. https://codeforces.com/contest/1108/submission/48843911
•  » » 4 weeks ago, # ^ |   0 Thats a greddy approach..I did same thing
 » 4 weeks ago, # |   0 Why my rating don't update?
•  » » 4 weeks ago, # ^ |   +5 cuz there is 12 hours open hacks
 » 4 weeks ago, # | ← Rev. 4 →   +5 O(nmlogn) algorithm of E2 48867037I use some method to decrease the constant, and it exits when time is up.
 » 4 weeks ago, # |   0 I can't blieve D is much easier than C,But it's TRUTH :P
 » 4 weeks ago, # |   0 nice problems :D
 » 4 weeks ago, # |   0 Someone please update Ratings.
 » 4 weeks ago, # | ← Rev. 2 →   -11 Weak systests, my solutions passed
 » 4 weeks ago, # |   +4 This round was quicker than the previous Educational round !!
 » 4 weeks ago, # | ← Rev. 4 →   +28 User Iamoni coded with friends.Problem A(48801772)Problem C(48805698)Problem E1(48808903)Problem E2(48822818)Different templates, different coding styles.
•  » » 4 weeks ago, # ^ |   +5 Good catch there. Also the submission times are highly suspicious. Hopefully they will look into it.
 » 4 weeks ago, # | ← Rev. 2 →   0 can anybody help why my O(n^3) solution for B is wrong https://codeforces.com/contest/1108/submission/48890311
•  » » 4 weeks ago, # ^ |   0 How did you get this approach?_
•  » » » 4 weeks ago, # ^ |   0 I tried to make all the pair of x and y from the given array and then checking for every pair whether it satisfy the given constraint for x and y , if yes then print x and y ( I still don't know what is wrong in my approach).
•  » » » » 4 weeks ago, # ^ |   0 try tests,where x — is 1 and y — composite num
•  » » » » » 4 weeks ago, # ^ |   0 It is working , you can test yourself , I have given link to my submission
 » 4 weeks ago, # |   0 Vovuh, will you publish the editorial?
•  » » 4 weeks ago, # ^ |   +2 In a few minutes, bro, please wait a bit :)
•  » » » 4 weeks ago, # ^ |   0 In a few minutes,108 minutes ago XD
•  » » » » 4 weeks ago, # ^ |   0 It is published now XD But it isn't work XD I don't know why XD
 » 4 weeks ago, # |   0 How to solve E by segment tree? (PS: When will the Tutorial be published?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 A key observation is that there is always an optimal solution that selecting all segments covering a specific index (let us call it x). To look for x, we can use a sweep line to handle with the segments and use a segment tree to update the answer.You can see my code for more information.(UPD) It seems that someone has answered the same approach before :(
•  » » » 4 weeks ago, # ^ |   0 thx
 » 4 weeks ago, # |   0 Problem E1 someone help me, what's wrong in this approach. https://codeforces.com/contest/1108/submission/48893961
 » 4 weeks ago, # |   +3 Editorial Page is not working for me! does someone else has this issue too?
 » 4 weeks ago, # |   0 48837239 — what is the issue with this?
 » 4 weeks ago, # |   0 Why are you not sure about [user:lamoni]?
•  » » 4 weeks ago, # ^ |   0 Take a look on this
•  » » » 4 weeks ago, # ^ |   0 ok thanks.