Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### Edvard's blog

By Edvard, history, 4 years ago, translation, ,

Hello, Codeforces!

[Note the unusual (for the educational round) start time!]

Educational Codeforces Round 10 will take place after a long delay on 25 march 2016 at 16:00 MSK for the first and the second divisions. The long delay is caused by the high frequency of contests and championships on Codeforces. You can read about educational rounds here and here.

<The same as before>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks.

</The same as before>

From now traditionally the problemset was totally suggested by Codeforces users. The problem А for the third time was suggested by user unprost (no hope for the short problem statement :-)). The problem B was suggested by user aminra. The problem C is another problem from the set sent by Bayram Berdiyev Bayram, Allanur Shiriyev Allanur-98 and Bekmyrat Atayev Bekmyrat-Atayev. Alexey Dergunov dalex suggested the problems D and E. The problem F was suggested by Lewin Gan lewin.

Thanks a lot to them and all others who are sending the problems or just ideas of the problems!

The problems D and E was prepared by Alexey Dergunov dalex. Other problems was prepared by me (Edvard Davtyan). I want to note the generator for the problem E its difficulty comparable with the solution to the problem F. Thanks to Maria Belova Delinur for checking the English statements. The problems was tested by users: unprost, aminra, Aleksa Plavsic allllekssssa, Alexey Dergunov dalex and Lewin Gan lewin. Thanks a lot to all of them!

I hope you will enjoy the problems!

P.S.: I really like the problem F and hope to see Accepted-s for it.

Good luck and have fun!

UPD: The contest is finished. The editorial is ready.

• +192

 » 4 years ago, # |   +26 The time in this announcement may be wrongIn this announcement In Contest section
•  » » 4 years ago, # ^ |   +28 Oh sorry. Fixed now.
•  » » » 4 years ago, # ^ |   0 Sorry i am newbie in programming that i didnt even pass the A-class question.However when i got a accepted answer from the internet.I find it actually wrong in logic. Take this set of data as example: h1=1 h2=26 a=3 b=5 actually in the first day cant get the apple and in the night down to groud.But you also can see he can actually get the h2 height during the second day. Which my copy of the Acceptted Answer tell it cant reach.
 » 4 years ago, # | ← Rev. 2 →   -23 On a completely unrelated note : Will my problems ever get considered, since it's been >3 weeks.
•  » » 4 years ago, # ^ |   +53 Hey. You send me problems after ER9. It's the first round after that. You can be sure that I'll check your problems and try to take them.P.S.: Note the problems C, D, E, F was sent to me in January and February.
•  » » » 4 years ago, # ^ |   +15 I see, so the queue is really long.
 » 4 years ago, # |   +14 Finally an educational round! Also When will we be having round #346? It has been a while now
 » 4 years ago, # |   +23 Thanks a lot Edvard for all your efforts . Just make the editorials a little detailed for problems D, E and F .
•  » » 4 years ago, # ^ |   +32 I'll try to make editorials more detailed, but unfortunately you should wait until tomorrow. The programming camp in MIPT will start tomorrow and I'll go to Moscow right after the round.
 » 4 years ago, # |   +35 This guy is using the chair wrong >.<
 » 4 years ago, # |   +9 Did anyone else find the problem C really hard to understand? You didn't specify that (x, y) is a pair of indices. All the time I was thinking that it's a segment of numbers.
•  » » 4 years ago, # ^ |   -9 Same here. It took me more than one hour to understand the statement. Unfortunately i didn't have time to code after i understood it. In my opinion D was way easier.
•  » » » 4 years ago, # ^ |   -20 No it's very easy, and much easier than D. It's just harder to understand.
•  » » 4 years ago, # ^ |   +7 No I wasn't confused, but what in heaven in test case 4!!!
•  » » 4 years ago, # ^ |   -7 Yes! Also A confused me a bit which made me start with D :)
•  » » 4 years ago, # ^ |   +7 I don't think that .I found it clear and I started with it :D
 » 4 years ago, # |   +10 Was the open hacking phase started?
•  » » 4 years ago, # ^ |   +5 Yeah, "open hacking phase is running: 23:48:14", we simply can't use it :(
•  » » 4 years ago, # ^ |   0
•  » » » 4 years ago, # ^ |   +3 Lol, I can't open anyone's code.
•  » » » » 4 years ago, # ^ |   +3 except youself..
•  » » 4 years ago, # ^ |   +5 I dont understand what going on here.Only Code owner hacking their solution.Lol
 » 4 years ago, # |   0 Please, use correct words in problem statements! Intervals instead of segments in C confused me a bit.
 » 4 years ago, # |   0 I cant submit problems nor register for practice in this contest, is that disabled?
 » 4 years ago, # | ← Rev. 2 →   +4 Not able to submit solutions after the contest has ended. Clicking on "Register for practice" is not working.UPD: Registering for a virtual contest is working.
 » 4 years ago, # |   +8 Please try to make good problem statements. A and C lacked too much clearity. Many people lost their points because of that. :)
•  » » 4 years ago, # ^ |   0 There is no points in this round)
•  » » » 4 years ago, # ^ |   +9 Points in the sense, their position in this round. I know this is not a rated round, but performance does matter.
 » 4 years ago, # |   +6 Hacking phase has started, but not able to view others' solutions. Please fix it .
 » 4 years ago, # |   0 Unable to submit code.
 » 4 years ago, # |   +5 how to solve E? it seems less harder than D(how to solve D by the way)
•  » » 4 years ago, # ^ |   +10 For D,we can sort the intervals by end points.Then for the ith interval to count how many intervals lie completely within it we just need to count how many starting points for the intervals from the 1st to i-1th interval are greater than the starting point of the ith interval. This can be done using a Fenwick tree.
•  » » 4 years ago, # ^ |   +16 Find all bridges and biconnected components of our graph. The answer is "YES" if there is a "good" edge inside some biconnected component on the unique path from biconnected component containing start, to biconnected component containing end.
•  » » » 4 years ago, # ^ |   +14 It's also yes if a good edge connects 2 components lying on that unique path.
•  » » » » 4 years ago, # ^ |   0 what is biconnected components of our graph? Is it same as Strongly Connected Components? I think SCCs are only defined for Directed Graphs otherwise the definition won't make any sense!When is the editorial coming up?
•  » » » » » 4 years ago, # ^ |   0 An edge is a "bridge" if removing it disconnects our graph. Two vertices are in the same biconnected component if there is a path between them that doesn't use any bridges.
•  » » » » » » 4 years ago, # ^ |   0 Oh Okay I get it thanks ! I know about bridges but I hadn't heard about Biconnected components! All I need to figure out now is an algorithm to find out BCC.!
•  » » » » » » » 4 years ago, # ^ |   +3 you can modify Tarjan algorithm (which find SCC) to find BCC
•  » » » » » » 4 years ago, # ^ |   +3 As far as I know the most widely used definition of biconnected component is that it is an articulation-point-free subgraph (eg see here). Wikipedia calls the components relevant to this problem 2-edge-connected components.
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +2 Two vertices are in the same biconnected component if there is a path between them that doesn't use any bridges. Are you sure about that? In a non-simple cycle, we have no bridges, but we have articulation point. I think you meant articulation point.
•  » » » » » » » 4 years ago, # ^ |   0 You destroy edges when you cross them, not vertices.
•  » » » » » » » » 4 years ago, # ^ |   +10 I thought you were speaking in general about biconnected components, not just relevant to the problem :) Even if we destroy edges, a biconnected component will still have no articulation point, and bridges will form a separate block. I have just started learning about biconnectivity, so please excuse my mistakes.
•  » » » » » » » » » 4 years ago, # ^ |   +1 Oh, I see the misunderstanding. Yes, I think I was using the wrong terminology here, but we seem to all be on the same page about the actual algorithm. Apologies.
•  » » » » » » » » » 4 years ago, # ^ |   0 Hi, could you suggest some good readings about biconnected components? I searched but could not find any.
•  » » » » » 4 years ago, # ^ |   +5
•  » » » 4 years ago, # ^ |   0 Or if a bridge itself in this path is a "good" edge.
 » 4 years ago, # |   +3 I Can't Open Any One's Code, (Except Mine).Is This Happening To Me Only? :O
•  » » 4 years ago, # ^ |   0 No, It's happening to everyone .
•  » » » 4 years ago, # ^ |   0 Thanks.Now I Just Saw The Announcement :) ..
 » 4 years ago, # | ← Rev. 6 →   +19 I have no idea about the russian version but the english version of nearly all problem statements had a lot of grammatical errors. Problem A: doesn't make it clear whether we have to reach the exact height h2 at the time of observation or just reach that height before observation once(but this was kinda clear due to "apple" terminology) Problem D: Use of the word line segment could have made it slightly less confusing on first read Problem E: ...bridges are too old and destroying right after passing... Destroying the character? Or wut? xD Problem F: ...circle of length m... radius? Diameter? Circumference?
•  » » 4 years ago, # ^ |   0 I solved B,C,D and couldn't get A because I understood that I have to reach the exact height h2 .I sent a question and they didn't response to it .
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 Similar thing happened with me. I wasted like 15-20 minutes on A, then did B, C, D, and later came back to A, asked them for explanation of a sample case, but they simply said "Reread statement", so I tried to think up something and did submit, but got hacked later :/
 » 4 years ago, # |   +3 Hacking is going on, but i can't see others code !!! any explanation ???
•  » » 4 years ago, # ^ |   0 It's Not Working. They"ll Fix It Soon..
 » 4 years ago, # |   0 I desperately want to submit a solution but I am unable to do so.should I have to wait another 23 hours??please help.
 » 4 years ago, # |   +10 Hacking phase was reconfigured. Now it works as expected. Happy hacking!
 » 4 years ago, # |   0 very strange thing happened with D, 5*200000 sized array failed for segment tree (WA on test 16) while 6*200000 gets AC. I always thought 4 times the size is enough :(
•  » » 4 years ago, # ^ |   +8 The maximum number of distinct points is 2 * 2e5 not 2e5.
•  » » » 4 years ago, # ^ |   0 oh yeah my bad!
 » 4 years ago, # |   0 I try to use my test generator but I get "Validator 'val.exe' returns exit code 3 [FAIL Expected EOLN (stdin)]" (I wrote "cout<
•  » » 4 years ago, # ^ |   +8 I think that you print an unnecessary space at the end of your input array.
•  » » » 4 years ago, # ^ |   +5 Thanks, works!
 » 4 years ago, # |   +1 I feel I'm the only Idiot who thought there will be a case where I should print "Impossible" in B ..
 » 4 years ago, # |   0 what would be the answer of A if input is: 500 555 6 1? If answer is 1, how?
•  » » 4 years ago, # ^ |   0 Hello man! :) Well first day it climbs from 500 → 548 (6*8) ... in the night, it slips back by 12 (so to 536) third day, it can climb up to 72 (6*12) which is enough :)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 that means answer is 0 as it will reach the apple before 2 pm next day ?
•  » » » » 4 years ago, # ^ |   0 exactly! .> "0" is, if it reaches apple during first 8 hours :) [2pm → 10pm]
•  » » » » » 4 years ago, # ^ |   0 but in sample test case it gives wrong on "0".
•  » » » » » » 4 years ago, # ^ |   +6 Sorry, not sure what you meant — so I'll try to comment all samples:A) 10 → 36 (+8*2) → 24 (-12*1) → 48 (+12*2) (== day 1)B) 10 → 18 (+8*1) (== day 2)C) a < b && it can't do it during first day (== -1)D) 1 → 41 (+5*8) → -7 (-12*4) → 53 (+12*5) (== day 1)
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +5 okay. Got it!! Thank you for your reply. I did a silly mistake on understanding the question.
 » 4 years ago, # |   0 Lol in A I assumed boy returns to look exactly at 2pm on any day.
•  » » 4 years ago, # ^ |   0 i assumed the day end at 2pm and got +6
•  » » » 4 years ago, # ^ |   +11 I am sorry what do you mean by +6 ? I solved A by taking the snail 4 hours back in time, and so I didn't have to add extra condition for 1st day
•  » » » » 4 years ago, # ^ |   +6 Six unsuccessful submissions as I can see :)
•  » » » » » 4 years ago, # ^ |   +1 ok got it :) Statements were badly written.
•  » » » 4 years ago, # ^ |   +1 I got +5 because of that ! Poor problem statement :)
 » 4 years ago, # |   +1 Is there any tutorial for this round?
 » 4 years ago, # |   0 I am sure I have solved a similar problem to D somewhere before.
 » 4 years ago, # |   0 In hacking with generator, what does the text field for generator parameter do? Is it just taking in some constants which we can easily specify within the code itself?
 » 4 years ago, # |   0 Problem A was very hard to understand for a poor english readers like me.
 » 4 years ago, # |   0 problem B:for test case : 5 1 3 2 2 5my output was 2 2 5 3 1whats wrong in this? i think 2 conditions already satisfied in this .. please help me
•  » » 4 years ago, # ^ |   +1 i dont think you understood the question properly the indexing should start from 1. so here 5 at an odd place is greater than 2 which is at an even place which is violating second condition
 » 4 years ago, # | ← Rev. 2 →   0 Post editorial, please or tell me how to solve problem C!
•  » » 4 years ago, # ^ |   +1 here is the editorial
•  » » » 4 years ago, # ^ |   0 still not able to realize the solution of problem C after reading the editorial, lol, can anyone help me
•  » » » » 4 years ago, # ^ |   0 Imagine you have intervals i..n for i = 1..n. Also nearest foe pair for this interval is ([j], [k]), were j and k are positions of numbers of the pair in the permutation — this means all intervals inside i..k-1 interval would be the good ones, and all inside k..n would be the bad ones, and you need the good ones to answerYes, the statement was quite messy, and I've also spent some time to understand it
 » 4 years ago, # | ← Rev. 3 →   0 In E, I am struggling with proving why we must consider biconnected components, that is, why can't we use more relaxed constraints. Can anyone help me? I mean, we only need to make sure that there is a path between boy and dealer which doesn't use any edge twice, and the artifact edge is also in the path.
•  » » 4 years ago, # ^ |   0 By creating a graph that have biconnected components, we have a unique path between the source and the sink. If there were multiple paths to follow, how would you try them all?
•  » » » 4 years ago, # ^ |   0 Thanks I got it :)
 » 4 years ago, # |   0 Can anyone explain why does a programmer need a headphone as shown in the pic ?
•  » » 4 years ago, # ^ |   +11 Hello,A) Not do disturb neighbor, while listening to loud musicB) Not to by disturbed by neighbor, who is listening to loud music
 » 4 years ago, # |   +3 There is unexpected verdict for hack 222111 (not mine). Any updates on it?
•  » » 4 years ago, # ^ |   0 The second solution to that problem worked wrong on that test. It was fixed and hack is rejudged.
•  » » » 4 years ago, # ^ |   0 It says "ignored" now instead of success or failure.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 The solution of doreamon works correct on it. Anyway we add that test to the testset. The test is: 4 8 6 6 R 5 L 1 R 8 R 
 » 4 years ago, # | ← Rev. 3 →   0 can anyone tell me in the first case of C, why (3,4) is not counted? I think I had great trouble understanding the problem.
•  » » 4 years ago, # ^ |   0 Because foes [3,2] are within this interval
 » 4 years ago, # |   -10 I am not able to understand problem C even after reading editorial. Can any one explain in detail?
•  » » 4 years ago, # ^ |   +3 Good day to you man!Not sure, whether you missed statement or solution, so:Statement says, that there is permutation of N numbers and there are pairs of "pointers" to the array. Now the question is "how many sequences are there, which do not include any pair (meaning both pointers of the pair)?".My solution: A) I read all pairs [begin,end] and "sorted" them (I used heap) by their ends (minimal first). Begin and end are mapped to array.B) Now for each beginning of sequence (==index in array), there are as many sequences as number of possible ends of the sequences. The question is, how co count number of possible ends? Well as you have sorted pairs → you end the sequence at any index, which is closer to beginning sequence, than the end of nearest pair, for which it is true, that it begins not sooner, than the beginning of the sequence.Hmm slightly confusing, isn't it — I'll try to do it once again, so you can choose better explanation (if any of them will be enough)a) Map permutation to indexesb) Map pairs to indexesc) Make pairs as [begin,end]d) Sort pairs by end firste) Iterate through every index of array I) Exclude all pairs, which begins sooner, than actual index II) Number of sequences, which begin from current index is equal to distance between index and next pair's endComplexity O(Nlog(N))
 » 4 years ago, # |   +4 Can someone give me some problems like this E, please?
 » 4 years ago, # |   0 Doing some reading on biconnectivity, 2-connectivity, 2-edge-connectivity (quite confusing) for problem E, when I came across this line on wikipedia it may also be possible for a non-bridge edge to have two articulation vertices as endpoints Is it true for directed graphs only, or also for undirected graphs as well. I can't find a case where this can be true for undirected graph. Please help :)
•  » » 4 years ago, # ^ | ← Rev. 4 →   +15 This graph contains such an edge: Image
•  » » » 4 years ago, # ^ |   0 Ah yes! Thank you :)
 » 4 years ago, # |   0 Can anybody help me ?? What's the constructive algorithms ???