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

Автор AlexSkidanov, 11 лет назад, перевод, По-русски

Всем привет!

Второй раунд соревнования MemSQL start[c]up состоится 3-его Августа в 21:00 MSK. Одновременно будет два контеста: для тех, кто участвует онсайт, и для тех, кто участвует онлайн. Набор задач в двух контестах будет одинаковый, и за них будет начислен рейтинг на основе общего монитора.

Участники, участвующие в онсайт раунде, получат специальные призы за первые три места. Все участники онсайт раунда и топ 100 участников из онлайн раунда получат специальные футболки start[c]up.

Участники, не прошедшие во второй раунд, могут участвовать неофициально. При этом раунд будет рейтинговым для таких участников.

На соревновании будет предложено шесть задач, длительность соревнования -- три часа. Распределение баллов 500-1000-1000-2000-2500-3000.

Задачи приготовлены разработчиками MemSQL pieguy, nika, exod40, SkidanovAlex и dolphinigle.

Удачи и отличного кодинга!

UPDATE: Опубликован разбор задач (на английском)

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

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

А в онлайн трансляции можно участвовать, если не писал первый раунд?

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

    Можно регистрироваться вне конкурса.

    Update: При этом вне конкурса тоже начисляется рейтинг

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

      UPD: Прежде чем заминусуеш, прочитай все правки выше и здесь. UPD2: Зачем читать...

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

      А для тех, кто вне конкурса, контест будет рейтинговым или нет?

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

are other people allowed to join unofficially for fun? maybe in a separate room?

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

    Will be div2 edition?

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

      Div2 participants are welcome to register for the round unofficially, but the problemset might be too hard for them. Expect problems A and B to be comparable to Div2-C and problem C to be as hard as Div2-D or E.

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

        It's ok, I think most of Div.2 participants could solve at least two problem in this contest.

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

    Yes, it will be possible to participate unofficially.

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

is it rated for Div2 participants?

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

      That's not exactly the answer to the Haghani's question. AlexSkidanov only stated, that round will be rated for those not advanced from round 1

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

      I hope all the commentators could give your reasonable comments. I don't know why this comment(just contains a "Yes", and it's a fact) got two "down"s.

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

    It will be rated for all the users.

    We welcome Div2 users to participate, but if you register for the round, please be advised that this problemset is not designed for Div2 participants, and you might end up with 0 problems, which will result in a significant loss of rating.

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

      if i register but don't attempt any problem, then will i loss point? is there pretest as usual cf?

      Edit: (i asked about rating, cz, there was a notification while registering, it said something like:- "it will not easy for div2, u may loose point, do u still wish to register?" )

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

        u won't...but the rating isn't the most important thing.Just have fun. at least you can do better than me,LOL

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

Hello I have a question.

How can I register the online contest officially if I have advanced to the round two?

According to the statement above, both official and unofficial online participators need to register the online version. I assume the system will automatically recognize the official particpator (who passed the round 1), am I correct?

Thank you

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

    Yes, it automatically registers those who have not advanced to round 2 for the unofficial track. After you register, please double check, than in the list of registrants you do not have a star symbol next to your handle (star symbols means registered for the unofficial track).

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

Можно задать вопрос? Как будет считаться рейтинг для участников онлайн раунда? Для всех вместе или для официальных и неофициальных участников отдельно?

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

все, разобрался!

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

Are unofficial participants competing for T-shirts?

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

Баг или фича? Я зарегистрировался на этот контест (как неофициально Див-2), но кнопка "Зарегистрироваться" не пропала.

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

Hope a good contest for div 2 participants ;)

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

What does the "Unofficial participation" mean? What kind of participants will be considered as unofficial participants.

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

    People who have not advanced to the round two can participate in the round unofficially. Unofficial participation will be rated.

    If you register for an online round, but you have not advanced to round 2, your participation will be unofficial (in the dashboard and the scoreboard such participants are marked with a star).

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

      Thank you.And Will there be round-3? If so, a man who have not advanced to the round 2 but get a high rank in round 2 unoffically, can he participant in round 3 as an offical participant?

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

is it for sql language,

or we can participate in any language

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

А результаты онлайн раунда сразу будут? Или какого-нибудь закрытия онсайта надо ждать?

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

Как решалась C?

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

    Делим на куски вида прямоугольники N*2, бывает 4 вида кусков в зависимости от того, с какой стороны (слева/справа) прололжение воды. Дальше Гранди.

    Я забыл написать мемоизацию, но понятно, что если ее написать, то будет не более 4х100 различных состояний

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

      Может лучше Гранди?:)

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

      Теорема Махатма Ганди.

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

      Ну или можно просто считать гранди для поля динамикой dp[mask][l][r], где l и r границы рассматриваемого подполя а mask показывает какие клетки свободны в l-том и r-том столбиках

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

Хм... Соревнование ведь завершилось. А код других участников смотреть нельзя.

И даже если это ещё можно как-то понять, то почему, собственно, нельзя просматривать профили пользователей?

UPD: Пользуясь случаем, выказываю своё фе участникам, которые зарегистрировались, но не стали отправлять задачи на проверку.

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

    Про твое "фе": Просто участников из див2 сильно пугали для того, чтобы система на онсайте не заглючила.

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

Условие в F-ке такое простое и, казалось бы, знакомое, но...

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

    Мне кажется, что это задача от dolphinigle, у него уже когда-то была очень крутая задача на жадник.

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

Anyone know why profile page says "The page is temporary blocked by administrator." ?

Edit: after system tests it keeps msg as before..

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

    Because when a contest is running they blocked some pages that are not necessary at this moment.

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

    I think it block it until the rates change completely

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

В Д разве не заходит 3000*N?

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

    Не всякая 3000 * N заходит. У меня не зашла (зря я не тестировал на сервере время работы).

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

Стыдно спрашивать, но как решалась В?

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

    Если букв больше, чем 2600, то есть какая-то буква, которая встречается 100+ раз (принцип Дирихле). Иначе — квадратная динамика f[i][j] — длина максимального подпалиндрома в подстроке от i до j.

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

      Один я, как идиот, написал динамику за N*100*26?

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

        Нет, я тоже, как идиот.

        А какая динамика?

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

          dp[i][j] — где заканчивается "палиндромно-хорошая" строка, содержащая палиндром длины i, который начинается в позиции j. Переход — перебираем, какую букву алфавита мы припишем к этой строке с обеих сторон.

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

        Не один :-)

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

        Ахаха :) Ну, у меня динамика за 100*N: [какой суффикс строки смотрим, какую длину палиндрома хотим] = в каком минимальном месте закончим.

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

        Я вообще по-моему какое-то палево сдал. Кто-нибудь умеет объяснять почему это быстро работает? 4223118

        Без if(best.length() >= rest) return best; — TL.

        Я сперва считал, что каждым из концов может быть не более 50 позиций каждой буквы(первые 50 для левого конца, последние 50 для правого), но теперь понял, что это не правда на тесте baaabaaaaaaaaaaaaa... часть a-шек между b-ками тоже бывают правыми концами. Или может кто-то умеет валить?

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

      Такое простое решение, круто! А у меня адская динамика dp[i][j] = длина минимального суффикса строки, такого что у него и у реверса префикса длины i длина максимальной общей подпоследовательности равна j.

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

    Для N>2600, ответ всегда есть, так как хотя бы одной буквы будет больше либо равно 100(доказывается по принципу Дирихле)...а для меньших N пускаем динамику за квадрат.

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

when is the rating changed

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

В D 3000n отсекалось специально (и не проходят все реализации), или такое решение не предполагалось и что-то проходит, а что-то нет?

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

Could anybody tell me some smaller input so that I could figure out the mistake in my code for B. It was hacked on some large random test case when it was possible to have a subsequence of length 100. http://codeforces.me/contest/335/submission/4223108

In that case my code prints out some non printable character. I am unable to figure out why ?? Any help would be appreciated !!

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

    Small inputs: "a" "aa" "aaa" "aaaa" "ab" "abc" "aba" "abac" "abcbabcc". (This isn't meant as a joke, I really used that to debug my solution :D)

    Just write a random generator and make your own input(s). It's hard to find a tricky case here, anyway, so any random string should do.

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

      Oh, it was a silly kind of mistake.
      string t;
      t += s1;
      t += s2;
      where s1 and s2 are two characters
      is not equivalent to
      t += s1 + s2;

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

    "abababababababababababababababababababababababababcbababababababababababababababababababababababababa"

    (101 characters in the string, 100 characters in the solution)

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

Why doesn't multiset in STL have such common operations? Just to find the maximum and the second largest number?

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

no one solved problem F. I am curious to know the approach of this problem. btw it was very gud contest. :) :)

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

When will we be able to register for practice?

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

Возможность отправить на проверку после соревнования есть?

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

i solved B in O(n^2) by using the fact that there are only 26 variety of characters. if n >= 3000 then there is a character that has occurred more than (3000/26) >= 100 times.

so I print a string with length 100 with only this character if n < 3000 then the problem would be the same as LPS (longest palindrome subsequence) which is solvable in O(n^2) if don't think this was the intended solution

and problem C is very similar to problem SGU 328. but with lower constraints (it is solvable in O(R))

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

    I think your solution for problem B is the intended solution, that's why the 100 constraint is there.

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

      Probably. I didn't come up with that solution but a different one with complexity O(100n) that doesn't depend on the number of types of characters.

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

        Sounds like your idea is better than quadratic. Because with 500 types of symbols it would be necessary to process whole length of string (50000). Could you explain in short words?

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

          Let F(i, j) is the maximum index k > i such that we can obtain a palindrome of length 2 * j from characters in [1, i] and [k, n] (j characters in each part).

          Actually, we also need to know the maximum index of occurrences that is less than k for each type of characters. In my submission 4225240, I construct a table in O(26n) for finding in O(1). In case the number of character types is large, this can be handled in O(log(n)).

          So, overall complexity is O(100n + 26n) or O(100n log(n)).

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

    Ken Ichi Kawarabayashi would say: "100 is a constant, alphabet's size is a constant, so B can be solved in constant time" :P

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

Thanks a lot for these nice, short and clear problems.

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

Why the problem-setters' nicks point to topcoder profiles instead of codeforces profiles?

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

Thank you for onsite competition!

It was perfect!

And congratulations to Seikang who won poker tournament!

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

Thanks for the contest and the onsite event! (great problems, awesome people, and tasty pies) Thanks for the poker lessons. I finally learnt! (and for the prize XD)

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

    I'm glad you liked the pies (that was the true prize, of course).

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

    Damn! I missed the pies while walking around San-Francisco :(

    BTW, I also enjoy the event very much but I still think that my performance was quite poor and I got the prize spot only by luck.

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

    The onsite event was great indeed! Thanks a lot.

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

    Yes, it was great! I played the poker first time and it was funny :)

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

А как узнать какое место среди учасников, которые не вне конкурса?

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

Will any editorial be published? I would gladly read solutions to E and F.

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

"топ 100 участников из онлайн раунда получат специальные футболки start[c]up."<--в эти топ 100 неофициальные участники входят?

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

    Надеюсь, что нет. Да и было бы логично, что нет.

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

    Неофициальные не входят в эти топ100

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

      Вот черт... Если бы я не слил первый раунд, то сейчас я бы получил футболку :(

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

Где разборы?

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

Thanks to MemSQL engineers for your contest. I was an offical participant (passed round 1) and finish the online contest with rank 74 (solved 2 problems). So when and how can I receive a T-shirt?

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

    We will be sending them out shortly. Someone will contact you to confirm your t-shirt size and address very soon.

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

when would the editorial be published?

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

Any news about the T-shirt?

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

Наконец-то разборы! Ура-ура-ура!!!

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

is there anybody knows something abouth T-shirts?

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

Has anyone received their t-shirt yet?

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

I've received my shirt now as well. Thanks for this!