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 Smaug. The problem C is another problem from the set sent by Bayram Berdiyev bayram, Allanur Shiriyev Allanur and Bekmyrat Atayev Bekmyrat.A. 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, Smaug, 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.

The time in this announcement may be wrong

In this announcement In Contest section

Oh sorry. Fixed now.

On a completely unrelated note : Will my problems ever get considered, since it's been >3 weeks.

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.

I see, so the queue is really long.

Finally an educational round! Also When will we be having round #346? It has been a while now

Thanks a lot Edvard for all your efforts . Just make the editorials a little detailed for problems D, E and F .

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.

This guy is using the chair wrong >.<

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.

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.

No it's very easy, and much easier than D. It's just harder to understand.

No I wasn't confused, but what in heaven in test case 4!!!

Yes! Also A confused me a bit which made me start with D :)

I don't think that .

I found it clear and I started with it :D

Was the open hacking phase started?

Yeah, "open hacking phase is running: 23:48:14", we simply can't use it :(

Look here http://codeforces.com/contest/652/hacks

Lol, I can't open anyone's code.

except youself..

I dont understand what going on here.Only Code owner hacking their solution.Lol

Please, use correct words in problem statements!

Intervals instead of segments in

Cconfused me a bit.I cant submit problems nor register for practice in this contest, is that disabled?

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.Please try to make good problem statements. A and C lacked too much clearity. Many people lost their points because of that. :)

There is no points in this round)

Points in the sense, their position in this round. I know this is not a rated round, but performance does matter.

Hacking phase has started, but not able to view others' solutions. Please fix it .

Unable to submit code.

how to solve E? it seems less harder than D(how to solve D by the way)

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.

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.

It's also yes if a good edge connects 2 components lying on that unique path.

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?

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.

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.!

you can modify Tarjan algorithm (which find SCC) to find BCC

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.

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.

You destroy edges when you cross them, not vertices.

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.

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.

Hi, could you suggest some good readings about biconnected components? I searched but could not find any.

http://codeforces.com/blog/entry/43986

Or if a bridge itself in this path is a "good" edge.

I Can't Open Any One's Code, (Except Mine).Is This Happening To Me Only? :O

No, It's happening to everyone .

Thanks.Now I Just Saw The Announcement :) ..

I have no idea about the russian version but the english version of nearly all problem statements had a lot of grammatical errors.

exactheight h2 at the time of observation or just reach that height before observation once(but this was kinda clear due to "apple" terminology)line segmentcould have made it slightly less confusing on first read...bridges are too old andDestroying the character? Or wut? xDdestroyingright after passing......circle ofradius? Diameter? Circumference?lengthm...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 .

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 :/

Hacking is going on, but i can't see others code !!! any explanation ???

It's Not Working. They"ll Fix It Soon..

I desperately want to submit a solution but I am unable to do so.should I have to wait another 23 hours??

please help.

Hacking phase was reconfigured. Now it works as expected. Happy hacking!

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 :(

The maximum number of distinct points is 2 * 2e5 not 2e5.

oh yeah my bad!

I try to use my test generator but I get "Validator 'val.exe' returns exit code 3 [FAIL Expected EOLN (stdin)]" (I wrote "cout<<endl" at the end). Any ideas?

I think that you print an unnecessary space at the end of your input array.

Thanks, works!

I feel I'm the only Idiot who thought there will be a case where I should print "Impossible" in B ..

what would be the answer of A if input is: 500 555 6 1? If answer is 1, how?

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 :)

that means answer is 0 as it will reach the apple before 2 pm next day ?

exactly! .> "0" is, if it reaches apple during first 8 hours :) [2pm → 10pm]

but in sample test case it gives wrong on "0".

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)

okay. Got it!! Thank you for your reply. I did a silly mistake on understanding the question.

Lol in A I assumed boy returns to look exactly at 2pm on any day.

i assumed the day end at 2pm and got +6

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

Six unsuccessful submissions as I can see :)

ok got it :) Statements were badly written.

I got +5 because of that ! Poor problem statement :)

Is there any tutorial for this round?

I am sure I have solved a similar problem to D somewhere before.

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?

Problem A was very hard to understand for a poor english readers like me.

problem B:

for test case : 5 1 3 2 2 5

my output was 2 2 5 3 1

whats wrong in this? i think 2 conditions already satisfied in this .. please help me

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

Post editorial, please or tell me how to solve problem C!

here is the editorial

still not able to realize the solution of problem C after reading the editorial, lol, can anyone help me

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 answer

Yes, the statement was quite messy, and I've also spent some time to understand it

In E, I am struggling with proving why we

mustconsider 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.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?

Thanks I got it :)

Can anyone explain why does a programmer need a headphone as shown in the pic ?

Hello,

A) Not do disturb neighbor, while listening to loud music

B) Not to by disturbed by neighbor, who is listening to loud music

There is

`unexpected verdict`

for hack 222111 (not mine). Any updates on it?The second solution to that problem worked wrong on that test. It was fixed and hack is rejudged.

It says "ignored" now instead of success or failure.

The solution of dreamoon_love_AA works correct on it. Anyway we add that test to the testset. The test is:

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.

Because foes [3,2] are within this interval

I am not able to understand problem C even after reading editorial. Can any one explain in detail?

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 indexes

b) Map pairs to indexes

c) Make pairs as [begin,end]

d) Sort pairs by end first

e) Iterate through every index of array

Complexity

O(Nlog(N))Can someone give me some problems like this E, please?

Doing some reading on biconnectivity, 2-connectivity, 2-edge-connectivity (quite confusing) for problem E, when I came across this line on wikipedia

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 :)

This graph contains such an edge:

Image

Ah yes! Thank you :)