Codeforces Beta Round #24

14 лет назад, # ^ |

Проходит. Единственная "тонкость" - желательно определять -1 до бинпоиска.

→ Ответить

mastersobg

14 лет назад, # ^ |

Ассимптотика у Вас ровно O(Nlog(1<<30))? Дополнительно log(N) не встречается? )

→ Ответить

14 лет назад, # ^ |

Ровно O(nlog(1<<30)). Проверка на пересечение при фиксированном времени происходит за линейное время, поскольку массив отсортирован.

→ Ответить

Ripatti

14 лет назад, # ^ |

объясните, пожалуйста, как проверять на пересечение не сортируя массив?

→ Ответить

14 лет назад, # ^ |

+10

У нас есть массив отрезков, которые отсортированы по одному из концов. Идем слева направо. Если встретили левую границу отрезка, который "растет" вправо, то сохраняем его правую границу. Очевидно, что если мы до этой границы встретим любую точку отрезка, который "растет" влево, то пересечение есть. Очевидно, что идя слева направо, мы встретим правую границу такого отрезка (если он существует) и проверим его левую границу и сравним.

→ Ответить

mmaxio

14 лет назад, # ^ |

Ого, они отсортированы были... А я и не заметил=)

→ Ответить

Ripatti

14 лет назад, # ^ |

спасибо! понял))

→ Ответить

Ripatti

14 лет назад, # ^ |

еще раз спасибо, сдал :D

→ Ответить

freopen

14 лет назад, # ^ |

Прошло на 3 теста дальше. И все равно упало. Да что ж за задача такая

→ Ответить

forest

14 лет назад, # |

Как друзей добавлять в табличке ?

→ Ответить

14 лет назад, # ^ |

В профиле надо на звёздочку нажать

→ Ответить

taras.klaskovsky

14 лет назад, # ^ |

+12

в профиле нажать на звездочку справа от ника.

→ Ответить

14 лет назад, # |

+12

Спасибо за контест! Поднадоели временами очень хитрые задачи C и почти нерешаемые (за время контеста) для простых смертных задачи D и E. А тут все гораздо более радостно. Еще раз спасибо, лично мне понравилось!

→ Ответить

14 лет назад, # |

туплю с D, кто-нибудь может объяснить решение?

→ Ответить

14 лет назад, # ^ |

+12

Составляем очевидным образом трёхдиагональную (?) матрицу и решаем каким-нибудь методом.
Удивительно, но метод итераций держит 4 цифы.

→ Ответить

14 лет назад, # ^ |

+12

Считаем d[i][j] - мат. ожидание количества шагов, которое нужно сделать из клетки (i,j). Научимся переходить от i-го ряда к (i-1)-му. Для этого нужно решить линейную систему из n уравнений с n неизвестными. Матрица этой системы трехдиагональная, причем выполняется условие строгого диагонального преобладания. Решаем методом прогонки.

→ Ответить

14 лет назад, # ^ |

До трёхдиагональной матрицы и прогонки я допёр :) Просто не заметил что робот может на месте остаться... внимательней надо быть.

→ Ответить

Egor	14 лет назад, # ^ \| +5 Я тоже не заметил. Но заметил, что ответ отличается ровно на N - i. Так что тупо добавил - и сдал → Ответить

14 лет назад, # ^ |

здорово. я это тоже заметил но не поверил :(

→ Ответить

wangzhihao

14 лет назад, # |

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++ ?

→ Ответить

YuukaKazami

14 лет назад, # ^ |

Oh..In GNU C++ you can use %I64d...%lld sometimes doesn't work...

→ Ответить

Fcdkbear

14 лет назад, # ^ |

You can read about this problem here

→ Ответить

14 лет назад, # ^ |

+11

FAQ really should be easily accessible from the main page

→ Ответить

wangzhihao

14 лет назад, # ^ |

thank you~

→ Ответить

mohamed.gaber

14 лет назад, # |

please can anyone describe the solution of the third problem ?

→ Ответить

14 лет назад, # ^ |

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 лет назад, # ^ |

Если не сложно, то поясните, каким образом получается M[2 * n] = M[0].

→ Ответить

14 лет назад, # ^ |

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 лет назад, # ^ |

A point that is symmetric to (x, y) with respect to (x₀, y₀) is (x + 2· (x0 - x), y + 2· (y0 - y)), that is, (2· x₀ - x, 2· y₀ - 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.

→ Ответить

mohamed.gaber

14 лет назад, # ^ |

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.

→ Ответить

P___	14 лет назад, # ^ \| 0 I checked it, there is no test with j = 0. (please delete my previous post in wrong place) → Ответить

Ministr

14 лет назад, # |

А разбор будет ?

→ Ответить

wRabbits_AlMag

14 лет назад, # ^ |

В комментариях почти все разобраны, в принцыпе :)

Скоро должен быть

→ Ответить

14 лет назад, # ^ |

Здесь неплохо все описано.

→ Ответить

P___	14 лет назад, # \| 0 I checked it, there is no test with j = 0. → Ответить

johnfn

14 лет назад, # |

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 лет назад, # ^ |

+17

Topcoder SRM often starts at 5AM MSK. That is our revenge :)

→ Ответить

gen	14 лет назад, # \| +5 Может я слишком придирчивый, но в задаче С обозначение "A_{(i - 1)%n}" математически некорректно (насколько я знаю), и человек, не использующий С-подобные языки, мог бы и не понять, что это такое. → Ответить

sdryapko

14 лет назад, # |

если я не ошибаюсь то это модуль, хотя я не уверен

→ Ответить

sdryapko

14 лет назад, # |

я тоже недавно стал изучать C++

→ Ответить

Medium

14 лет назад, # |

В E я так понимаю, что если перебрать возможные дроби (xi - xj)/(|vi|+|vj|), то ответ по точности не пройдет?

→ Ответить

14 лет назад, # ^ |

По времени

→ Ответить

Medium

14 лет назад, # ^ |

Время временем, а по точности такое деление подойдет?

→ Ответить

14 лет назад, # ^ |

При желании можно представлять эти дроби рациональными числами, т.е. точность получается абсолютная. В даблах тоже должно хватить

→ Ответить

chowyunfat

14 лет назад, # |

Please tell me the sollution of problem d, my algorithm is too slow , does someone has a fast algorithm , like O(n^2) ?

→ Ответить

Nedy88

14 лет назад, # ^ |

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.

→ Ответить

miaout17

14 лет назад, # |

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 лет назад, # ^ |

The key is to use binary search.

→ Ответить

Fcdkbear

14 лет назад, # |

Похоже, какие-то проблемы с проверяющей системой. Мой сабмит по задаче Е уже час в очереди.

→ Ответить

yuyan

14 лет назад, # |

Excuse me,could you please tell me how to solve problem D?

→ Ответить

14 лет назад, # ^ |

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.

→ Ответить

yuyan

14 лет назад, # ^ |

Thank you very much!!!I have learnt some useful knowledge with your help!Sorry for my poor English:)

→ Ответить

14 лет назад, # |

Может кто подсказать, где ошибка... Для решения задачи Е применил следующий подход: пусть частицы находятся на отрезке АС, а В - середина АС. Тогда решение будет либо принадлежать отрезку АВ, либо ВС, либо одна частица будет принадлежать первому отрезку, а вторая - второму. Последний случай проверяю жадно за линию, а первый и второй - рекурсивно... Решение валится на 59-ом тесте :(.

→ Ответить

Egor	14 лет назад, # ^ \| 0 А какая жадность для точек из разных отрезков? → Ответить

14 лет назад, # ^ |

За линию, если я правильно понял вопрос.

→ Ответить

Egor	14 лет назад, # ^ \| 0 Меня сам алгоритм интересует. Какая разница какой он сложности, если был WA, а не TL (или таки TL?) → Ответить