Edvard's blog

Educational Codeforces Round 10
By Edvard, history, 9 years ago, translation, In English

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.

  • Vote: I like it
  • +192
  • Vote: I do not like it

Comments Comments (102)
| Write comment?
»
9 years ago, # |
  Vote: I like it +26 Vote: I do not like it

The time in this announcement may be wrong

In this announcement In Contest section

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      I see, so the queue is really long.

      → Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it +35 Vote: I do not like it

This guy is using the chair wrong >.<

→ Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

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

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    I don't think that .

    I found it clear and I started with it :D

    → Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Was the open hacking phase started?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please, use correct words in problem statements!

Intervals instead of segments in C confused me a bit.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I cant submit problems nor register for practice in this contest, is that disabled?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Please try to make good problem statements. A and C lacked too much clearity. Many people lost their points because of that. :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is no points in this round)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

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

      → Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Unable to submit code.

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

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

              → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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.

            → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 2   Vote: I like it +2 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              You destroy edges when you cross them, not vertices.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                  Vote: I like it +10 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 years ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  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.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

                  → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

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

          → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 6   Vote: I like it +19 Vote: I do not like it

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?
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like 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 :/

      → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

please help.

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            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)

            → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

            → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there any tutorial for this round?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    here is the editorial

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Hello,

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

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

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

There is unexpected verdict for hack 222111 (not mine). Any updates on it?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The second solution to that problem worked wrong on that test. It was fixed and hack is rejudged.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        The solution of dreamoon_love_AA 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
        → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    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 end

    Complexity O(Nlog(N))

    → Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone give me some problems like this E, please?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply