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

Автор MikeMirzayanov, 7 лет назад, По-русски

Привет!

Codeforces Round 481 (Div. 3) начнётся в 13.05.2018 12:05 (Московское время).

Это будет второй в истории Codeforces раунд для третьего дивизиона. В этом раунде будет 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи для вас подготовили я и fcspartakm. От души спасибо тестерам AGrigorii, BigBag, nhho и Sert!

Удачи!

UPD 1: Спасибо за участие. Опубликован разбор задач.

UPD 2: Поздравляем победителей! Топ-5 (официальные результаты):

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

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

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

I hope less "dfs and similar" and "dp" and more "implementation" . thanks :D

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

Are contests of div 3 always same educational rounds?

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

Are contests of div 3 always same educational?

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

will it be possible to do the problems after the contest has ended?

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

Hope it won't be Readforces round! :D

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

Why the unusual time? Finally on a weekend, but in the middle of the night :( :(

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

The time is too bad !!

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

What about Educational Round ? Will that round continue or Div3 is the replacement ?

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

Last weekend was also a div3 contest. That would be great if we could alternate between div3 and div2 contests on the weekends!

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

Why do you guys each time override the rules and create ambiguity, by saying "it's only for trusted participants", then, "regardless of whether you're trusted or not, if your rating < 1600, it'll be rated for you". Why do you even bother to mention "trusted users" or that it's to combat unsporting behaviour? In fact, it's not!

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

    ???????? Trusted participants are in the official standings table and it's rated for everyone currently under 1600

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

    "Why do you guys each time override the rules"
    They don't. last (and first) time was absolutely the same rule.

    "Why do you even bother to mention "trusted users" "
    Because it's about being included in the official standings table.

    "In fact, it's not!"
    In fact, it is, lol.

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

      You have no idea of what I'm saying! Read the first sentence once again till the end.

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

        "Read the problem statement more carefully"

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

          Can you tell me where is the “official standing” which only includes trusted users? I see everyone gets rated including unrated ones and the ranking takes them into account.

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

            Official standings table dosen't mean people who gets rated. Official standings table is a public table, which shows standings of the contestants who took part in the round. And from this table, because of new rules, they remove untrusted users. So they become invisible for public and there is no point in participating for the high places, like most does.

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

              Can you share the "official standing" link for the last div3 contest? I can see everyone in "common standings", and in the rating changes, I see "those" unrated ones included. So where is that "official standing" which has only the trusted users? Please share it for the round #480

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

                You're welcome (use right click — "open picture in the new tab").

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

                  Am I the only one who can still see some unrated accounts in the official standings??

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

                  Well, for some reason I now see them too. But, "Milhous", who actually won contest, still not here, which means for some reason this two guys suddenly become visible. Maybe bug, maybe intentional.

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

                  Yeah I think it makes some sense to be like this since hacking is still going on. Remove them from the standings table after hacking finishes; otherwise, their solutions are less likely to get hacked.

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

                  We are talking about round 479, which ended a long time ago, so.

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

                  Oh whoops you're right, my bad. Yeah, they shouldn't appear,

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

        I got your point exactly. Why don't you reread me instead?

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

          I can’t “reread” you sorry )))

          Just to say that by saying overriding rules I didn’t mean the rules are different from the previous div3 contest, but I meant that he first says that it’s rated only for trusted users (excludes unrated users), and then says that if you are < 1600, then you will be included. This is my question.

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

            "but I meant that he first says that it’s rated only for trusted users (excludes unrated users)"

            Where? I think you are the one who needs to reread...

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

              a. Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

              • take part in at least two rated rounds (and solve at least one problem in each of them),
              • do not have a point of 1900 or higher in the rating.

              b. Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.


              doesn't b. override a. condition? Either I'm missing very basic info, or it's confusing..

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

                a. portion does not say anything about rated status of the contest.

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

                  Share that "official standings" for round #480 which considers only trusted users. I can see all the unrated participants show up in the standing.

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

                  Shared it higher. But why are you asking round 480 btw? This rule works only for div3 round, not div2.

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

                  Yeah I noticed, thanks for that. Seems like I never realised "show unofficial" checkbox and it was left checked=true so I wasn't able to get what the statement above was saying. But I finally got it and can sleep comfortably :) Thanks for your time!

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

Не иметь в рейтинге точку 1900 или выше значит, что если у участника когда-либо было 1900 или выше, то он недостоверный участник?

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

Although I rarely miss a CF round , I guess I will miss tomorrow's contest because I have to attend a national contest at that time :-(
Last one was Round #466

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

ops .. i can not join you . .

we will have our university acm

albaath contest

so ... i am very sad ..

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

How can I be 'trusted participants'.
I meant: I already take part in more than two rated rounds and I also have rating less than 1900.
But when I register, it alert like I'm not rated in this round.

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

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

Я не понял: в чем смысл достоверного участия, если рейтинг для недостоверных участников все равно пересчитывается?

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

    Достоверные участники отображены в официальной таблице результатов

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

      И что, это типа круто?

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

        Ну по мнению организаторов, самого Майка ну или непонятно кого еще — видимо да. Считается, что люди с высоким рейтингом создают новые аккаунты и участвуют в соревнованих для более слабеньких, чтобы выиграть их(ну и поднять свое чсв, наверное). И собственно, Майк и ко. считают, что если таких людей не будут показывать в таблице достоверных участников, то и действовать они так не будут.

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

          С другой стороны понижается чсв топа1. Открываем его профиль и видим на графике 3-е место.

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

Oh!! Div-3 saved my coding career!!

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

Too Hard... 42mins to solve all problems...

»
7 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Сколько даётся за успешный взлом и сколько снимается за неуспешный?

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

    В соответствии с правилами образовательных раундов, успешные и неуспешные взломы напрямую не влияют на результат.

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

      Тогда почему рейтинги меняются? Я был 56м, а теперь 45й? Разве это не из-за того что людей повзламывали?

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

        Именно, это из-за того, что кого-то взломали (или убрали из рейтинговой таблицы). А не из-за того, что кто-то взломал удачно, либо неудачно.

        То есть взлом никак не влияет на результат взломщика, но влияет на результат цели в случае успешного взлома (взломанная задача считается нерешённой).

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

I feel that the difficulty of the contest should be a little more than it currently is

Pre-system testing, 250+ trusted participants solved all the questions, which is around 10% of all the trusted participants. This never happens in Div2 or Div1, so I feel that even for Div3 standards, the whole problemset might be on the easier side. (Maybe the last 2 questions should be harder?)

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

    Agreed. Although having speed be part of the contest is inherently part of competitive programming, somebody who is very good at solving problems but codes slower should still be able to achieve a fairly high score on the leaderboard.

    Having the problems be too easy also introduces a lot of variance on the leaderboard.

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

I solved E F G each in about 10 minutes but in the last 30 minutes I couldn't still solve D... I think D is harder than the last 3 problems

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

I'm not able to attempt hacking any problems. It says on the right that I am doing the contest as practice, although I participated in the round and am under 1600. Can someone help?

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

When the editorial will be added?

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

Test case 7 for E anyone? Is it legit to ask for test cases now?

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

А почему чужой код нельзя посмотреть во время фазы взломов? Или это пока временно?

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

    Дай участникам повзламывать самим себя :)

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

    Я посмотрю в чём дело чуть позже, сейчас идет награждение победителей внутренней олимпиады Саратовского университета. Исправил!

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

hi everyone . I am a new codeforces user. I don't have any information about hacking. Can someone give me information about hacking

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

    Click the user's solution twitch time to open his/her solution.

    Then click the hack option. And figure out such a case that case will

    Give an output that output does not match with correct output.

    If don't match with correct answer hack will be successful otherwise hacked will be

    unsuccessful.

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

Solved all problems in both of the Div.3 contest. I think it should be a little bit harder :D

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

    At the same time, Div 3 isn't meant for you though, since it isn't even rated for you.

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

      At the same time, old div2 was not meant for candidate masters but they struggle to solve all the 5 problems.

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

    I did it for like 2.5 hours. Problems are very easy there. It's more like div4.

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

can anybody tell me why this is wrong on pretest 3 in problem G it seems correct to me . 2 2 2 1 1 3 4 0 4 4

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

    Exam 3 starts later so you can't prepare for exam 3 earlier...

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

    You can't study for an exam until the questions get released.

    In this case, the questions for Exam 3 get released on day 8, and you're trying to study for them on day 6.

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

    You can't start preparing for the test before s_i, which is in this case 8.

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

open hacking phase is running

But I can't open others codes why?

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

I can only hack my code. Can anyone tell me what's happening?

UPD: It's fixed now!

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

I have participated in more than 2 rated contest and my rating is less than 1600 but still I am not able to view other's solution and try to hack them.Why is this happening.

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

Почему нельзя взломать кроме самого себя? Я из див2. регистрировал вне конкурса.

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

Мне кажется задача D была сложнее нежели E, F. Не знаю пройдет ли системное тестирование, но я попытался решить задачу другим способом. Вот мое решение. http://codeforces.me/contest/978/submission/38182546

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

В задаче D при попытках взлома получаются "неизвестные вердикты".

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

can someone explain the 4 th test case of E 2 10 -1 2 what should be the output??

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

Can someone look at these 2 solutions of C: 38161183 38162269.

The first has complexity O(k*k) the second O(k*logk) and yet the second takes 1.5 s more?? What am I missing?

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

    38161183 is not O(k^2), it looks more like O(m) to me (m being the number of letters): p is not reset after the inner loop, it just catches up, at worst in n inner iterations per outer iteration, but in constant time on average per inner iteration (n/m inner/outer iterations).

    Edit: please ignore the last brainfart. It is how Photon_ says :)

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

    Complexities are actually O(n+m) and O(m*lgn).

    On solution #1 it uses 2 pointers, so in worst case, you will traverse whole array a over all m queries hence the running time is O(n+m)

    On solution #2 it uses Binary Search over whole array. In worst case all queries will be in the start of array a so this solution will take O(logn) for each binary search hence the total running time will be O(m*logn)

    You can improve second solution to binary search not in [start, end] but in [last_pos, end]

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

please explain the 4th case of E please please please

2 10 -1 2

why us the output 9?

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

    There can be [1, 9] people on the bus before the first stop; if there were 10, after the second stop there are 11, and there has to be at least one before first stop.

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

    it could be 1 to 9. it can't be zero because after the first bus stop -1 remains. it can't be 10 because after the second bus stop there are 11 person in the bus and its more than limit (w).

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

I think this guy (__123456__) is cheating he used special conditions to hack his codes

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

I think it could've been more interesting or challenging if the duration were 2 hours (not 2.5 hr).

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

Why ProblemC need binary search? b_j is in increasing order.

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

Got "unexpected verdict" in hack 448105, 448122 and 448145.

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

Can any one help me in Problem C ? I think my code is correct but can't understand why it fails.
LINK : http://codeforces.me/contest/978/submission/38163975

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

Interestingly, my penalty in both (all :)) of the div.3 contests is 413.

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

It's weird, my Java code passed if I use int, and it failed at test case 5 if I use Boolean and Integer :|

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

The testcases are wrong. The test 21 on problem E is the first one that is wrong. The answer should be 1000000000, not 1000000001.

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

The testcases are wrong. The test 21 on problem E is the first one that is wrong. The answer should be 1000000000, not 1000000001.

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

I wonder if the ranking will be updated?

Just curious :D

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

I am not able to understand my rating change. I solved 2 out of 3 problems correctly (A went wrong due to a silly mistake and B, C were correct), but the rating still went down instead of going up?

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

    Your rating is dependent on how better or worse you did compared to other participants. Losing rating means you were expected(in relation with other participants) to get a better rank than what you got.

    You might be comparing your results with the earlier div 2 rounds where in general you would have gained rating on solving 2 questions, but this was an easier round than the previous div 2 rounds and contestants with lesser rating than you did better which caused you to lose rating.

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

It seems that my hacks on problem F (with n = 76297, ID 448348 and two others) weren't added to the final tests. Very nice.

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

Where's rating changes? Any announcement about it?

UPD: Fixed!

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

The rating I gained in this contest is now gone.What happened?

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

Where did my rating go after this contest? UPD. Rating returned

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

Soemthing strange is with ratings of participants..

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

ZаVтра раZбор будет?