fcspartakm's blog

Codeforces Round #386 (Div. 2)
By fcspartakm, history, 8 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?
»
8 years ago, # |
  Vote: I like it -35 Vote: I do not like it

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

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

    Wow, the first time I see blog about the contest late like this.

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

Sunday**

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

Hope the translation will be good!

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

Excited! My color will be changing today.

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

Wow, seven problems！

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

Hope to see some data structures

→ Reply
»
8 years ago, # |
  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
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

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

    Maybe it's too easy for div1 users.

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

      Then a combined round could do the trick ..

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

Mikhail Piklyaev awoo 's graph is so awesome :O

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

    seriously awesome and motivating graph :)

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

    Hard work pays off,sooner or later.

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

    Looks like awoo have had the experience of all the ranks. From falling to grey and then rising again. Really motivating.

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

      If only ranks up to candidate master were all of them :( It's still a really long way to grandmaster.

      → Reply
»
8 years ago, # |
  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
»
8 years ago, # |
  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
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I hope I can understand the statement:D

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

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

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

Is it rated?

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

Very Unusual time :(

→ Reply
»
8 years ago, # |
  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
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I am confused! Is it rated or not?

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

    Regular round always rated.

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

      see the.......... usual Div. 1 participants can join out of competition. That means it will be rated on.y for Div. 2

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

Can the answer in Div2C only be integer?

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

what could be the test 9 on problem D?

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

Why there are some Experts participating as out of competition?

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

    Probably because they missed the registration, which ended 5 minutes before start of contest

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

      dude I registered yesterday ...

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

      Add to that my submission for A was at min 3 which means I didn't register with extra registration

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

    train can go uptil 0 and s But the input constraints say current position is from 1 to s-1 So input position cannot be s

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

    I was facing the same problem until I put endlines as they have done in the input. Also your constraints are wrong.

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

    It was mentioned in the constraints that 1<=p<=s-1. Although the train can still go to point 0 and s, you cannot have those values as your initial position.

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

    Oh right, I didn't see the constraint. Thanks everyone for clarifying

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

Editorials?

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

    1. there are 4 odds (5, 7, 9, 1) but only 2 evens(6, 4).

    2. it seems that it's valid.

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

    Number of odd number cards should equal to number of even number cards

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

    Well, you can upload directly from the problem's page.

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

WTH????!!!!

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

    he gained the rating as well :)

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

    It can backfire too

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

    Same with me :(

    → Reply
  • »
    »
    8 years ago, # ^ |
      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://codeforces.net/contest/746/submission/23108354

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

WA problem C test 23 )= someone else?

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

    WA too tc 19 ):

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

    WA on 23 :'(

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

    Noo!! it's the case when they start in the same position! I am so stupid!

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

    I also had troubles here. Test case 23 starts with the train and the person at the same square, so that you can board the train instantly.

    So I would guess that you (like me) have a "> 0" in your code somewhere that should be ">= 0"

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

    Haha, similar thing happened to me. A,B,C passed and D,E failed.

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

The difficulty is not sorted alphabetically.

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

    do you mean for F and G or the whole contest?

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

      I believe G was even easier than E... My personal opinion...

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

Amazing Contest...

Good doable questions...

Thank you Writers :D

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

Can someone explain why did my code fail?

23085756

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

    I had the exact same doubt.

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

    Unsigned integer underflow 

    i = str.sz - 2 ;

    When str.size() = 1, then this value goes to a very large value.

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

so I failed 2 contest in 3 hours ...

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

Access denied to editorial :(

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

Would this contest be scored?

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

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

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

I wish we had more time, like 3 hours.

→ Reply
»
8 years ago, # |
  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
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Thank you for a really awesome contest!

→ Reply
»
8 years ago, # |
  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://codeforces.net/contest/746/submission/23106759

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

that moment when increased rating on div2 contest being div1

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

Can't access editorial

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

access denied on clicking editorial ?

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

sorry

→ Reply