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

Автор snarknews, история, 10 месяцев назад, По-русски,

Традиционно проект SnarkNews проводит голосование "Итоги года".

Цель голосования — отметить лидеров спортивного программирования прошедшего года — как участников, так и тренеров, а также наиболее удачные проекты и наиболее удачные публикации в прессе.

В настоящий момент проходит первый этап — выдвижение номинантов. Первый этап проходит до 13:00 31 декабря. Желающие опубликовать своё предложение по номинантам (и подискутировать по этому поводу) могут сделать это в комментариях к данному сообщению.

В этом году голосование вновь проходит на базе системы Яндекс.Контест. Соответственно, предложить номинантов может любой, кто имеет логин в этой системе. При входе в систему описаны правила; для перехода к конкретным номинациям и выдвижению номинантов перейдите в раздел "Задачи"; справа появится список номинаций. По каждой номинации принимается не более двух вариантов; каждый вариант задаётся в отдельной строке в соответствии с правилами номинации (которые находятся на том же экране, что и форма отправки).

UPD: Первый этап голосования завершён; в начале января эксперты объявят списки для второго этапа голосования (который пройдёт по той же схеме, что и в прошлом году).

Кроме того, Простой Новогодний Контест и Новогодний Блиц-Контест в этом году также пройдут на базе системы Яндекс.Контест; по сравнению с прошлым годом особых изменений в правилах не ожидается.

Открыта регистрация на оба контеста:

Простой Новогодний Контест — начнётся 30 декабря в 0:00, завершится 10 января в 23:50. Состоит из задач, предлагавшихся на различных командных соревнованиях по программированию в 2016 году, но так и не решённых в основное время.

Новогодний Блиц-Контест начнётся 31 декабря в 16:00, завершится 1 января в 8:00. Контест пройдёт по правилам Multiple Language Round (то есть за каждую задачу, успешно сданную на языке программирования, на котором участник ещё не сдал ни одной задачи, начисляется бонус -100 минут от штрафного времени) и по правилам Новогоднего Блиц-контеста (отличие от системы ACM в том, что время отсчитывается не от начала, а от 0:00 1 января по времени сервера, то есть и успешная сдача в 23:55, и успешная сдача в 0:05 дают штрафное время 5 минут).

Контесты уже стартовали, но зарегистрироваться можно в любой момент до окончания контеста.

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

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

Автокомментарий: текст был обновлен пользователем snarknews (предыдущая версия, новая версия, сравнить).

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

Автокомментарий: текст был обновлен пользователем snarknews (предыдущая версия, новая версия, сравнить).

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

Где ссылка "Задачи" то?

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

Автокомментарий: текст был обновлен пользователем snarknews (предыдущая версия, новая версия, сравнить).

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

Auto comment: topic has been translated by snarknews (original revision, translated revision, compare)

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

Auto comment: topic has been updated by snarknews (previous revision, new revision, compare).

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

Автокомментарий: текст был обновлен пользователем snarknews (предыдущая версия, новая версия, сравнить).

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

Auto comment: topic has been updated by snarknews (previous revision, new revision, compare).

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

Is there an editorial for the New Year Blitz contest?

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

How to solve 3. (Ancient City) and 17. (Generator)? Maybe there are some online editorials in English?

I hope Ancient City's intended solution doesn't require coding dynamic convex hull. I thought about decomposing interval of time when points lives into base intervals, compute hulls in every base interval and then for each query binary search on angle of side which line intersects, but htat leads to O(log3n) per query which I guess is too slow (one log for binary search on sides's slope, one for log n base intervals, one for binary search on extremal points with respect to chosen slopes). Aaaand exactly during writing that I realized that last log is not necessary since it can be reduced if we do parallel binary search and process all queries of maximal points wrt some slopes from one binary search pass in linear time of convex hull size <_<. However it is still messy to code.

So, what about 17? I thought for a long while and maybe I have a solution giving correct answers, but significantly too slow (but better than some straightforward Gausses :P). Summon zimpha, aid.

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

    First, let's solve this problem for n = 1. Let s be our string, p(i) be probability that there are no occurrences of s in the first i symbols produced by generator, q(i) be probability that there is exactly one occurrence of s in the first i symbols and it ends at i-th symbol. Also, let , and .

    Assume that we generated i symbols and didn't find s. When we generate the next symbol, we either don't find s or find one occurrence of it, and in the latter case it ends at (i + 1)-th symbol. So, p(i) = p(i + 1) + q(i + 1), and tf(t) = f(t) + g(t) - p(0) - q(0) = f(t) + g(t) - 1.

    Now, instead of appending 1 symbol, let's append the whole s. Then, we can find the first occurrence of s at positions i + 1, i + 2, ..., i + |s|, but not all of them are possible. If we find s at position i + j, then s must have a border of length j, and all such j are good. Let B be the set of all such j. So, we have , where , and sj is j-th suffix of s. And in terms of generating functions: , where .

    So, we have system of 2 linear equations, which we can solve to find f(t) for any t. The answer to our problem, is, of course, f(1).

    We can do the same thing with multiple strings, instead of 2 equations with 2 variables, there will be n + 1 equation with n + 1 variable. But in this case f(1) will be the expected time to find occurrence of some string from our set, and we need to find all strings from our set. We can do it using inclusion-exclusion formula. Let pA(i) be probability that no string from the set A occurs in the first i symbols produced by the generator, rA(i) be probability that not all strings from A occur in the first i symbols, , and . , and . So, we can find hA(1) by counting fB(1) for all . The complexity is O(n2l + 2nn3).

    There is a small problem with this solution. When we use Gauss, we can get a matrix with determinant divisible by 109 + 7, and we will not be able to solve the system. I solved this problem by not doing anything and hoping that there are no such tests, which turned out to be true.

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

    For Ancient City, there is a similar problem Dogs' Candies in ACM/ICPC 2014 Guangzhou and another similar problem Misha & Geometry in CodeChef June Challenge 2016.

    Divide the convex hull into Upper Convex Hull and Down Convex Hull. It's ok just to consider Upper Convex Hull (Down Convex Hull is just the same).

    For each point (xi, yi), find the interval of time [li, ri) when the point exists. Now we can solving all problem use divide-and-conquer by queries. The pseudo code is below:

    def solve(L, R, queries):
      M = (L + R) >> 1
      for q in queries:
        if q.l <= L and q.r >= R:
          upper_hull.add(q.x, q.y)
        elif q.l >= R or q.r <= L:
          continue
        else:
          new_queries.add(q)
       if L + 1 == R:
         # here, we got the upper convex hull at time L
       solve(L, M, new_queries)
       solve(M, R, new_queries)
    

    You can use a persistent treap (or treap with rollback) to maintain the upper/lower convex hull (Since we only need to insert point to treap, this is easy to code). Then, adding point in upper convex hull will work in , solve(0, n) function has complexity , so the total complexity is .

    As for the geometry part, several simple binary search will work.