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

Автор Nedy88, 14 лет назад, перевод, По-русски
Привет всем,

Добро пожаловать на Codeforces Beta Round #24. Сегодня я автор большинства задач. Немного о себе: меня зовут Недялко Присадников, я студент Софийского университета, в Болгарии. Здесь вы можете посмотреть мои фотографии. Большое спасибо Михаилу Мирзаянову и Артему Рахову за организацию контеста, написание альтернативных решений и за условия нескольких задач.

Интересного вам раунда, удачи!

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Люди, в чем соль задачи E? Почему там стандартный бинпоиск не проходит? Там есть какая-то незаметная тонкость?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    траблы с точностью. По крайней мере у меня))

    Сдал в итоге, сделав не просто проверку на наличие столкновения за m секунд и выходом обратно в дихотомию, а ещё и присваиванием минимума из времен всех найденных таким образом столкновений.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    Проходит. Единственная "тонкость" - желательно определять -1 до бинпоиска.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      Ассимптотика у Вас ровно O(Nlog(1<<30))? Дополнительно log(N) не встречается? )
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ровно O(nlog(1<<30)). Проверка на пересечение при фиксированном времени происходит за линейное время, поскольку массив отсортирован.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          объясните, пожалуйста, как проверять на пересечение не сортируя массив?
          • 14 лет назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится
            У нас есть массив отрезков, которые отсортированы по одному из концов. Идем слева направо. Если встретили левую границу отрезка, который "растет" вправо, то сохраняем его правую границу. Очевидно, что если мы до этой границы встретим любую точку отрезка, который "растет" влево, то пересечение есть. Очевидно, что идя слева направо, мы встретим правую границу такого отрезка (если он существует) и проверим его левую границу и сравним.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Прошло на 3 теста дальше. И все равно упало. Да что ж за задача такая
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как друзей добавлять в табличке ?
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Спасибо за контест! Поднадоели временами очень хитрые задачи C и почти нерешаемые (за время контеста) для простых смертных задачи D и E. А тут все гораздо более радостно. Еще раз спасибо, лично мне понравилось!
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
туплю с D, кто-нибудь может объяснить решение?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    Составляем очевидным образом трёхдиагональную (?) матрицу и решаем каким-нибудь методом.
    Удивительно, но метод итераций держит 4 цифы.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    Считаем d[i][j] - мат. ожидание количества шагов, которое нужно сделать из клетки (i,j). Научимся переходить от i-го ряда к (i-1)-му. Для этого нужно решить линейную систему из n уравнений с n неизвестными. Матрица этой системы трехдиагональная, причем выполняется условие строгого диагонального преобладания. Решаем методом прогонки.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    До трёхдиагональной матрицы и прогонки я допёр :) Просто не заметил что робот может на месте остаться... внимательней надо быть.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Я тоже не заметил. Но заметил, что ответ отличается ровно на N - i. Так что тупо добавил - и сдал
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In the problem C, i submit a solution in GNU C++ which contains
/*
    long long id;
    int n;
    scanf("%d %lld",&n, &id);
*/
and got wrong answer on test 3, but when  i changed to Ms C++ with the same code, i got yes. Can anyone tell me the reason ? can not i use %lld in GNU C++ ?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
please can anyone describe the solution of the third problem ?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    M[k + 1] = 2 * A[k % n] - M[k]. It is easy to check that M[2 * n] = M[0]. So you can calculate M[j % {2 *n)] instead of M[j]
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если не сложно, то поясните, каким образом получается M[2 * n] = M[0].
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        M[1] = 2 * A[0] - M[0],
        M[2] = 2 * A[1] - 2 * A[0] + M[0],
        M[3] = 2 * A[2] - 2 * A[1] + 2 * A[0] - M[0],
        ...
        M[n] = 2 * A[n] - 2 * A[n - 1] + ... + 2 * A[0] - M[0] (т.к. по условию n нечетно),
        ...
        M[2 * n] = 2 * A[n] - 2 * A[n - 1] + ... + 2 * A[0] - M[n] = M[0].
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    A point that is symmetric to (x, y) with respect to (x0, y0) is (x + 2· (x0 - x), y + 2· (y0 - y)), that is, (2· x0 - x, 2· y0 - y). This gives us the O(j) method of solving the problem.
    To speed it up notice that the first j / n "cycles" can be processed faster with a sort of parity trick. In particular, any even number of cycles can be dismissed and the rest can be processed with the naive algorithm.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    there is a small notification about the constraints. it is said that 1<=j<=10^18 and it gave me wrong answer becaues i assumed that j will not less than 1 but i got accepted when i handled the case j = 0.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I checked it, there is no test with j = 0. (please delete my previous post in wrong place)
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
А разбор будет ?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I checked it, there is no test with j = 0.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Fun contest :) The timing really killed me though... had to get up at 5AM PST (I live in the USA, on the west coast)! That was nasty. I wish there was a possibility to bump the time back a few hours to help out all of us over in North/South America. 
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Может я слишком придирчивый, но в задаче С обозначение "A(i - 1)%n" математически некорректно (насколько я знаю), и человек, не использующий С-подобные языки, мог бы и не понять, что это такое.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
если я не ошибаюсь то это модуль, хотя я не уверен
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
я тоже недавно стал изучать C++
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В E я так понимаю, что если перебрать возможные дроби (xi - xj)/(|vi|+|vj|), то ответ по точности не пройдет?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По времени
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Время временем, а по точности такое деление подойдет?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        При желании можно представлять эти дроби рациональными числами, т.е. точность получается абсолютная. В даблах тоже должно хватить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Please tell me the sollution of problem d, my algorithm is too slow , does someone has a fast algorithm ,  like O(n^2) ?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    If you solve the problem row by row starting from the last one, then for every row you'll have tridiagonal matrix which can be solved much faster then standard Gauss elimination.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I have wrote a brute-force solution (O(n^2)) for problem E. Of course, I got TLE. 
I have no idea how to prune the search space, any hint? 
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Похоже, какие-то проблемы с проверяющей системой. Мой сабмит по задаче Е уже час в очереди.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Excuse me,could you please tell me how to solve problem D?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Let d[i][j] be the expected number of steps to reach the bottommost row from the cell (i, j). Calculate d[i][j] for rows N, N-1, ..., 1 in this order. To get d[i][j], j = 1, ..., m from d[i-1][j] you have to solve a linear system with tridiagonal matrix which can be solved in O(n) operations. 
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Thank you very much!!!I have learnt some useful knowledge with your help!Sorry for my poor English:)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Может кто подсказать, где ошибка... Для решения задачи Е применил следующий подход: пусть частицы находятся на отрезке АС, а В - середина АС. Тогда решение будет либо принадлежать отрезку АВ, либо ВС, либо одна частица будет принадлежать первому отрезку, а вторая - второму. Последний случай проверяю жадно за линию, а первый и второй - рекурсивно... Решение валится на 59-ом тесте :(.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А какая жадность для точек из разных отрезков?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      За линию, если я правильно понял вопрос.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Меня сам алгоритм интересует. Какая разница какой он сложности, если был WA, а не TL (или таки TL?)