snarknews's blog

SEERC-2014: current standings and text translation
By snarknews, 10 years ago, In English

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!

  • Vote: I like it
  • +34
  • Vote: I do not like it

Comments Comments (32)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

    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.

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

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

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

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

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

      Btw will you please tell how many problems did you solve finally ?

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

        9 problems with time ~1139 (we solved G at ~4:10).

        I guess that final standings will be published soon:)

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

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.

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

    List of participants arrived to me at last hour only.

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

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

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

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.

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

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

    UPD you can hide your comment by editing it.

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

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

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

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

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

    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).

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

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

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

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

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

        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.

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

      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?

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

Any hints for "Most Influential Pumpkin"? https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=656&page=show_problem&problem=4872

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

    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.

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

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

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

        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.

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

          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.

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

            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.

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

              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.

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

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

Thanks!

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

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

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

      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!

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

        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.

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

          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

          → Reply