fcspartakm's blog

Codeforces Round #386 (Div. 2)
By fcspartakm, history, 9 years ago, translation, In English

Hello, Codeforces!

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

This round is held on the tasks of the municipal stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. They were prepared by Olympiad center of programmers of Saratov SU.

Great thanks to Nikolay Kalinin (KAN) for helping me preparing the contest, to Tatiana Semenova (Tatiana_S) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform and to Vladimir Petrov (vovuh), Alexey Ripinen (Perforator), Mikhail Levshunov (Levshunovma), Mikhail Piklyaev (awoo), Aleksey Slutskiy (pyloolex), Ivan Androsov (BledDest), Oleg Smirnov (Oleg_Smirnov) and Roman Kireev (RoKi) for writing solutions and editorials.

It will be a little unusual round — you will be given seven problems and two and half hours to solve them. The scoring distribution will be 500-1000-1500-2000-2500-3000-3000. Good luck everyone!

UPD Editorial

UPD2 Congratulations to the winners!

  1. IHaveShort

  2. tqyaaaaaaaang

  3. UmaThurman

  4. Moiezen

  5. FIKS_samurai

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

Comments Comments (115)
| Write comment?
»
9 years ago, hide # |
 
Vote: I like it -35 Vote: I do not like it

Time of contest is clashing with https://atcoder.jp/. Please reschedule..

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

Wow, the first time I see the score distribution early like this. Hope this with be a good contest.

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

Sunday**

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

Hope the translation will be good!

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

Excited! My color will be changing today.

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

Wow, seven problems！

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

Hope to see some data structures

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

Why so strange hours? And, as someone mentioned earlier, clashes with atcoder :c.

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

7 problems?!! Couldn't there be a division 1instead? :3

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

Mikhail Piklyaev awoo 's graph is so awesome :O

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

Luckily I didn't fall to div2 today, so I can just solve some problems and then participate ARC066 :D

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

Hope that Tatiana does good job or we will have problems as #385's Div2B.

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

I hope I can understand the statement:D

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

I hope no one here asking "that" usual question..

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

Is it rated?

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

Very Unusual time :(

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

Wow, Seven problems. Hope it will be an exciting contest and my color will change(from green to grey or cyan).

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

I am confused! Is it rated or not?

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

Can the answer in Div2C only be integer?

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

Hacking didn't work for me this contest, I kept getting "Submit already challenged", and hack would not go through. :(

Also for A somehow I guess I double clicked submission button and so it submitted same code twice, with the first one counting for the resubmit penalty, does this always happen? Typically I think it prevents from submitting same code twice, but sometimes it allows?

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

    Seriously though does anybody know what it means when "Submit already challenged", but it has clearly not been challenged by anybody else.

    I was trying to hack skorpioas the whole time and it would not let me :( I tried both Chrome and Safari :(

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

what could be the test 9 on problem D?

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

Why there are some Experts participating as out of competition?

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

I tried to hack problem C with the following input 5 4 0 1 2 5 -1

And it says Invalid input with the following message = "Validator 'val.exe' returns exit code 3 [FAIL Integer parameter [name=p] equals to 5, violates the range 1, 4]"

Isn't this input supposed to be valid? Does this mean the train can only go up until point s-1?

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

Editorials?

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

Task were much more tehnical than hard...

I was so near to solve G :(

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

Why this outputs are wrong for E problem ?

INPUT

6 2

5 6 7 9 4 5

OUTPUT

1

5 6 7 9 4 1

INPUT2

8 6

7 7 7 7 8 8 8 8

OUTPUT2

6

7 3 1 2 8 4 5 6

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

Why I have to choose task number every time when I submit? Because of that I sent my solution to wrong problem. So sad :(

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

WTH????!!!!

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

    I'm guessing its a glitch.
    There were some reports yesterday about people who dropped below 1900 after the contest but still retained their colour.

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

    Yesterday I got to green but my rating was still in grey. Some kind of bug I guess.

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

    he gained the rating as well :)

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

    It can backfire too

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

    Sorry about that. I've registered as usual. I wrote to Mike. Hope he will fix it and there will be no rating changes for me. Also I didn't try to hack and no one hacked me.

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

      The same happened to me (although i lost rating) and i've wrote to mike too. I hope it will be solved or that it didn't affect others rating too negatively.

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

I always get too slow while implementing problems like C. Hope the editorial explains clear thoughts on how to solve such problems correctly and faster.

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

    Yeah simulating the situation is pretty tough to implement but I'm not sure the intended solution is through simulation. I just used a bunch of if statements to solve it.

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

      Your solution is really well analysed. My code missed AC just bcoz of single line. I forgot to check that the tram can be at x1 in the beginning. ;_;

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

    Exactly, It seems like more of math and less of logic , but yes i too want too learn how to solve such problems. I was thinking keeping this problem As Fast As Possible in mind but solution was a bit different.

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

      Todays problem reminded me also of the problem you mentioned. I guess implementation is still a challenging task to work upon in CP.

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

    I believe the idea is an event queue. When the tram passes by x1 or x2, we track that event.
    So, we could have 2 event queues: 

    vector<int> event_time_x1;
vector<int> event_time_x2;

    We are interested in events of second type event_time_x2, when tram passes by our target location. We just need to simulate tram's movement until we collect 2 events in the event queue event_time_x2.

    After that we compare the times contained in the queue event_time_x2 with the Igor's time when he is just walking to the target. If event_time_x2[0] ≥ walking_time, then there is no point in taking tram at all. If event_time_x2[0] < walking_time, then we need to track whether it was possible for Igor to get on the tram before tram has reached the target at event_time_x2[0]. To check that — we need to find the time, when the tram crossed Igor's location x1. If there was no event of crossing x1 location before the event event_time_x2[0], then it was not possible for Igor to reach target location x2 at the time the tram reached it event_time_x2[0]. After that, we check the second event.

    I failed on test 18, but I believe that my idea is correct. Probably I had to collect 3 events instead of 2.

    UPD: Yes, we need to store 3 passes of the tram: 23107366

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

    Same with me :(

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

    in C turns out you only need to consider 2 cases:

    1. walk all the way

    2. wait in x1 untill tram comes, then ride the tram

    here is my ac code

    http://mirror.codeforces.com/contest/746/submission/23108354

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

WA problem C test 23 )= someone else?

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

That feeling when your solutions failed on system testing on problems C,D but submission on problem E got AC. And you went from 374 place to 1135. My ass is burning!!!

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

The difficulty is not sorted alphabetically.

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

Amazing Contest...

Good doable questions...

Thank you Writers :D

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

The problem statement doesn't mention anywhere that the result will be an integer right? 23102907

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

I think problem E has weak testcases.

Example:

4 20
1 5 4 5

The answer should be something like:

1
1 2 4 5

My program outputs:

2
2 3 4 5
→ Reply
»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone explain why did my code fail?

23085756

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

so I failed 2 contest in 3 hours ...

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

Access denied to editorial :(

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

Would this contest be scored?

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

Is the Editorial accessible? I am receiving "Access Denied".

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

I wish we had more time, like 3 hours.

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

What happens when "Bad Luck" is your best friend??? Compare these submissions- 23086486 and 23105642

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

Thank you for a really awesome contest!

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

I am getting WA in pretest 9. Can you please provide a smaller but equivalent test case? My submission: http://mirror.codeforces.com/contest/746/submission/23106759

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

that moment when increased rating on div2 contest being div1

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

Can't access editorial

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

Limits of problem C are too small ,So some solutions passed by simulation.

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

access denied on clicking editorial ?

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

sorry

→ Reply