Блог пользователя fcspartakm

Автор fcspartakm, история, 8 лет назад, По-русски

Привет, Codeforces!

18 декабря 2016 года в 13:35 MSK состоится очередной раунд Codeforces #386 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса. Обратите внимание на необычное время начала раунда!

Этот раунд проводится по задачам муниципального этапа Всероссийской олимпиады школьников по информатике 2016/2017 года г. Саратова. Задачи были подготовлены силами Центра олимпиадной подготовки программистов Саратовского ГУ.

Хотелось бы сказать большое спасибо Николаю Калинину (KAN) за помощь в подготовке задач, Татьяне Семеновой (Tatiana_S) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а также Владимиру Петрову (vovuh), Алексею Рипинену (Perforator), Михаилу Левшунову (Levshunovma), Михаилу Пикляеву (awoo), Алексею Слуцкому (pyloolex), Ивану Андросову (BledDest), Олегу Смирнову (Oleg_Smirnov) И Роману Кирееву (RoKi) за прорешивание задач и написание разборов.

Участникам будет предложено семь задач и два с половиной часа на их решение. Разбалловка 500-1000-1500-2000-2500-3000-3000.

UPD Разбор

UPD2 Поздравляем победителей!

  1. IHaveShort

  2. tqyaaaaaaaang

  3. UmaThurman

  4. Moiezen

  5. FIKS_samurai

  • Проголосовать: нравится
  • +179
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится -35 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sunday**

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sunday**

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Hope the translation will be good!

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Excited! My color will be changing today.

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Wow, seven problems!

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Hope to see some data structures

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Mikhail Piklyaev awoo 's graph is so awesome :O

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    seriously awesome and motivating graph :)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Hard work pays off,sooner or later.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I hope I can understand the statement:D

»
8 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

Is it rated?

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Very Unusual time :(

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I am confused! Is it rated or not?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can the answer in Div2C only be integer?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can the answer in Div2C only be integer?

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

what could be the test 9 on problem D?

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Why there are some Experts participating as out of competition?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

  • »
    »
    8 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Editorials?

»
8 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Task were much more tehnical than hard...

I was so near to solve G :(

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

WTH????!!!!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    he gained the rating as well :)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

     It can backfire too

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Что за 9-ый тест в задаче D?

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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. ;_;

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится -7 Проголосовать: не нравится

    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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Same with me :(

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

WA problem C test 23 )= someone else?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    WA too tc 19 ):

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    WA on 23 :'(

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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"

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Даёшь разбор!)

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

The difficulty is not sorted alphabetically.

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Amazing Contest...

Good doable questions...

Thank you Writers :D

»
8 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain why did my code fail?

23085756

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain why did my code fail?

23085756

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

so I failed 2 contest in 3 hours ...

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Access denied to editorial :(

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Would this contest be scored?

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Would this contest be scored?

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I wish we had more time, like 3 hours.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Thank you for a really awesome contest!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В таблицу результатов попал участник из первого дивизиона (ник — Maxim): Интересно, как такое случилось? Более того, у него уже обновился рейтинг:

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Я просто зарегистрировался на контест как обычно. Написал Майку, надеюсь, пофиксят и рейтинг вернут. Никого не взламывал и никто не взломал меня во время контеста.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Регистрация на контест началась, до зачисления рейтинга. Возможно, ты зарегался, когда был еще див2)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Как раз-таки я зарегался за полчаса до контеста :). Но КФ показывал всем некорректные рейтинги.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

that moment when increased rating on div2 contest being div1

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can't access editorial

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

access denied on clicking editorial ?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Щедрый CodeForces :)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

sorry