ppavic's blog

Grand Prix of Siberia
By ppavic, history, 5 years ago, In English

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?

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

Comments Comments (52)
| Write comment?
»
5 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Same

→ Reply
»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

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

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

Same (spbifmo151)

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

Our login is zagreb02

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

Same (login: belgrade01)

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

same(login: zagreb01)

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

When opencup div 2 is going to start?

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

Fix please: Login: kharkiv03

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

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

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

Same(yerevan01)

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

Let's upvote all replies by snarknews

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

login: kharkiv11

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

Login: nnovg04

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

How to solve problems 3 and 9?

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

    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

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

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

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

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.

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

    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.

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

      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.

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

        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.

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

        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.

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

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!

→ Reply