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

Автор ppavic, история, 5 лет назад, По-английски

When we log in into the Yandex contest, we get the following message: "You are not allowed to view this contest"

Is anyone else having the same problem?

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

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

Same

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

If someone has the .pdf with tasks, please share, so we can at least start solving. Thanks

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

Same (spbifmo151)

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

Our login is zagreb02

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

Same (login: belgrade01)

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

same(login: zagreb01)

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

When opencup div 2 is going to start?

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

Fix please: Login: kharkiv03

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

It seems that there is a bug with automatical (or ever mass) addition for several sectors on the Yandex.Contest. So please write down your logins and they will be added manually

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

Same(yerevan01)

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

Let's upvote all replies by snarknews

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

login: kharkiv11

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

Login: nnovg04

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

How to solve problems 3 and 9?

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

    9: Build a suffix array for $$$s + * + t$$$, then you will decrease $$$k$$$ from $$$min(n, m)$$$ to $$$1$$$. It`s pretty easy to maintain groups of suffixes with a common prefix of length $$$\leq$$$ $$$k_{current}$$$, processing events like "a suffix appears because of its length becomes exactly $$$k_{current}$$$" or "unite two groups into one", and to recalculate answer iteratively after every change of structure

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

Okay, so you tell me that Russia didn't have timezones change xd? Yeah, I knew that, but it came rather as a surprise to is today xd

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

I never thought fflush is that slow and inconsistent. We literally TLed problem 8 with c++17 and got like 1100 ms with c++11.

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

    Our solution written on Java works for 4300ms. I thought it would work much faster, but it seems that without buffering input/output any interaction becomes very slow.

    BUT they said:

    Pay attention: interactor could alter the contents of the classified array in runtime if all the previously given answers stay true.
    

    So even if interaction is fast, their interactor may work slower than expected because of changing the array.

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

      There is a very simple randomized solution, which we decided to cut off. Basically, go through the array, while maintaining two minimal elements. When you take a new element, compare it to the second minimum, and if it is less, then compare to the first minimum. With a preliminary random shuffle, the second comparison is needed in only about $$$\ln N$$$ cases on average. In order to cut it off, we set very strict query limit $$$N + 20$$$. However, the solution can check how many queries it has made and simply return the current answer if queries are depleted. The probability that those few unprocessed elements at the end of the array are important is very small.

      The interactor checks that every element took part in at least one comparison. If some element was not touched, then it can be the sought-for second minimum in some array, probably not the one jury intended initially, so interactor returned WA in such case. This hack allowed us to cut off randomized solution, but we had to add this sentence, so that contestants could understand why their randomized solution does not pass.

      P.S. Yes, flushes are expensive. Interaction with its context switches is expensive too. Moreover, interactive problems show wildly different performance on different machines, OS-es and testing systems. We even get noticeable deviation when rejudging the same solution many times in a row.

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

        What is the purpose of $$$N \leq 10^5$$$?

        I've seen this exact problem some time ago (sadly, cannot find a link) but with $$$N \leq 10^3$$$, general solution in $$$N + log_2 N$$$ queries was exactly the same but setting this limit resolves all issues with slow interactions.

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

        Our randomized solution was accepted. If n <= 20 one can ask n — 1 queries to find first minimum, erase it from array and then ask n — 2 queries to find second minimum which will be the answer. If n > 20 one can keep array b of size 20, which will contain (not for 100% but with high probability) first minimum and second minimum. We assume first and second minimums are somewhere in first 20 indices, and then starting from 21-th element for every index i we randomly choose ind such that 0 <= ind < 20 and compare b[ind] with a[i] and if a[i] < b[ind] we replace b[ind] with a[i]. This process will take n — 20 queries and after it we solve for case n = 20 with algorithm I described before.

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

Выкладываю описания решений "от жюри" (какие нашёл):

Симметричная матрица
Olmec
Игра в строки
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    В задаче про строки можно построить суффиксное дерево для этой пары строк и "сканировать" его сверху вниз, поддерживая в дереве отрезков последовательность упорядоченных лексикографически подстрок, которые имеют длину k вместе с их числом вхождений в первую и вторую строку.

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

The teams from Cambridge also had the same problems (logins cambridge01 — cambridge04) and we saw this post just now. Could you fix for upsolving? Thanks!