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

Автор snarknews, 10 лет назад, По-английски

SnarkNews opened special project related to SEERC-2014, which is started at 10:00 Kyiv time in Vinnytsia (Ukraine) and Bucharest (Romania). For now it contains table of standings (main and separately by Vinnytsia and Bucharest sites), standings for Championship of Ukraine, and text translation (at the moment English is very poor).

Upd: standings are updated. Congrats to Lviv NU Penguins!

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

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

Who are in team LNU Penguins? Is it this team ?

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

What is the meaning of Dirt and SE in the scoreboard?

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

    Dirt: number of submits on the all solved problems / number of the solved problems

    SE: "average hardness". Problem, solved by N teams out of M, have hardness (M-N)/M.

    Another special fields:

    Jump — prediction of place after successful submit right now (or when it changes).

    Idle — time after last attempt.

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

Will the problems from SEERC-2014 be used as an OpenCup contest?

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

    It seems logical that contest named Grand Prix of SPb should be based on ХХХIX Championship of St. Petersburg State University (which is scheduled on tomorrow), but not on problemset from SEERC:)

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

I think it is good idea always to include last names of participants in team names like SPb SU 4 (Kunyavskiy, Egorov, Suvorov). First, ITMO used it on NEERC and other contests and I really think that it is a great idea.

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

First place: Lviv NU: LNU Penguins (Roman Bilyi, Vitaliy Herasymiv, Bohdan Pryshchenko) 9
Second place: Taras Shevchenko Kiev NU: Flawless (Roman Furko, Dmytro Ignatenko, Andrii Mostovyi) 9
Third place: Taras Shevchenko Kiev NU: Unicon (Maksym Bevza, Sergey Nagin, Yevgen Vasyliv) 9

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

Может кто-нибудь в двух словах написать, что такое SEERC, NEERC. Это полуфиналы ACM ICPC? И кто куда и в каком количестве проходит. В википедии про это ничего не сказано ну и на icpc.baylor.edu мне ничего не ясно((

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

    Да, это полуфиналы ACM ICPC.

    Расскажу про систему отбора в Украине.

    Есть 3 этапа отбора.

    На первом этапе соревнуются команды вузов одной области. Проходит ориентировочно в апреле

    На втором — команды из одного региона (Украина поделена на 5 регионов — Запад, Восток, Юг, Центр, Киев). Проходит ориентировочно в сентябре (один год было в мае)

    На третьем этам уже соревнуются все команды из SEERC (там несколько стран, цитата с официального сайта: Regional Boundaries include the following countries: Albania, Bulgaria, Croatia, Greece, Moldova, Romania, Turkey, Lebanon, Israel, Macedonia, Cyprus, Ukraine, and Serbia). Этап проходит в октябре. Лучшие команды из SEERC выходят на финал. Квота каждый раз разная, окончательно все понятно в начале декабря

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

      большое спасибо! и еще про количество команд:

      • в первом этапе — все желающие
      • второй — не больше 5 команд от вуза
      • третий — не больше 3 команд от вуза
      • финал — не больше 1 команды от вуза

      правильно?

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

        Про второй этап — точно не знаю, остальное вроде бы правильно

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

Can anyone share the solution for B?

Statement: You have a circular buffer of n ≤ 106 digits. You need to split that buffer somehow into k ≤ n consecutive parts. Out of all splits find the one whose maximum number is minimal.

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

    Public discussion of the problems is bad idea, because they will be used in opencup.

    UPD you can hide your comment by editing it.

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

      Oh, I did not know that. Let's discuss them after Open Cup then. :)

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

    Problems from SEERC will not be used at opencup at this year, as i mentioned before.

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

    There is one important thing: we don't have zeros in buffer. So we know the length of answer, it will be LEN = (n + k - 1) / k.

    Let's sort all sort all substring of length LEN (by building a suffix array, for example), and do binary search by answer.

    So we fixed some number S as answer, how to check if we can split our string in such way, that all parts will be not greater than S? We can do it greedily. We need to iterate over start position of the first part, because we have a circular string. And after that try greedily to get a part of length LEN, if it's impossible then we need to take part of length LEN-1.

    The total complexity will be O(nlogn).

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

      That's right. We forgot that we could binary search there. Thanks for the solution. :)

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

      Solution is clear, but how can we prove that we can greedily take part of length LEN?

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

        I don't know formal proof. But if it's not true, it means that we need to take part of length LEN-1(while it's possible to take part of length LEN), and sometimes later take part of length LEN. But it's obvious that we can take part of length LEN, and after of length LEN-1, and it won't change anything.

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

      if S is sorted and Si<=Sj,i<j. when we greedily know the Si can not be split that all parts whill be not greater than Si ,then what should we search next?

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

Дорешивание будет?

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

    1) After each query answer increases at most by 1.

    2) Let current answer be equal to d. After each query we can calculate, how many numbers, that are strictly less then (d+1) are in our array right now. This knowledge helps us to calculate the answer after current query. One should use sqrt decomposition to be able to do all the calculations. O(N*sqrt(N)*log(n)) solution easily passes the system test.

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

      Did you use tree<> from STL to find how many numbers are less than d+1 ?

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

        For O(N * sqrt(N) * log(N)) simple sqrt-decomposition is OK.

        You may set block size to sqrt(N). Now store sorted order for every block. For add query — update leftmost and rightmost block in naive way, and for all blocks between them — just remember that you made +1 over these blocks. And to find how many numbers are less than d — for every block you have to find how many numbers in this block are less than d - X, where X is your counter of +1's over whole given block, it can be done with binary search (for this purpose we are storing sorted blocks).

        Carefully implemented, this solution works in O(N * sqrt(N)). This is the way we decided to do it during contest, and it took some more time :) When rebuilding block, you can merge 2 parts in linear time, instead of simply doing sort; and part with binary search may be improved by storing pointer to median in every block, instead of searching for it every time.

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

          Thanks a lot! I got it accepted.

          Do you know what the time limits were at SEERC? My O(N*sqrt(N)*log(N)) needed ~7.7s and the O(N * sqrt(N)) ~3.4s.

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

            Time limits weren't mentioned in problem statements at SEERC; later in duscussion of contest maksay said that TL was set to 5s, and author's solution works 0.8-1.0s on C++ and 3.0-3.1s on Java — running time was almost same for O(N * sqrt(N)) and O(N * sqrt(N) * log(N)) solutions.

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

              During the contest our O(N * sqrt(N) * log(N)) approach timed out. I'm not sure if it was possible to get accepted without O(N * sqrt(N)) complexity.

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

Could anyone sketch the solution for problem G and/or problem I ?

Thanks!

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

    For problem G look at CYK algorithm, it will give you simple DP solution.

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

      Finally AC! I had coded this algorithm, but it seems storing DP(low,high,char) was much slower than DP(char,low,high).

      Thanks again!

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

        BTW, you should be familiar with this problem, in case you are representing SWERC — it was used as A — Mixing Colours at SWERC-2013.

        And CYK algorithm is mentioned in editorial as intended solution.

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

          Yes! That problem is burned in my mind for unfortunate reasons :(

          I had learned the CYK algorithm in an NLP course months before SWERC-2013, but problem A was the only problem I didn't read because my teammates told me it looked very hard and nobody had solved it... had I read it, we would probably have gone to the WF ^^'

          From that moment, I always read all the problems