Напоминаю, что сегодня (09.03.2013) в 18:00 по Москве состоится шестой (и последний регулярный) контест хорватской олимпиады по информатике. Залогиниться/зарегистрироваться можно тут. Продолжительность: 3 часа. Удачи!
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
07:01:01
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
07:01:01
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 10:33:59 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
I believe it is on 9 March :[ http://hsin.hr/coci]
Oops, thanks a lot.
Там в последней заходит прекалк количества шагов чтобы прийти в ловушку и смотреть в заданную сторону для каждой бактерии, а потом перебор для каждой бактерии в какую сторону она смотрит в момент, когда все придут в ловушку. Тогда ведь можно диафантовы уравнения решить и получить ответ.
Кто-то такое писал?
Я писал такое. Только там длины периодов маленькие (до 10000), так что уравнения можно решать за O(длины периода). По сути то же самое, только кодить проще и не нужно никаких расширенных алгоритмов Эвклида.
А почему период маленький? Мы ведь получаем до 5 выражений kx+b, и да, у каждого из них период до 10К, но их надо решить одновременно. А 2 (k * x + b) & (l * x + c) заменяются на одно lcm(k,l) * x + (место первой встречи), и тут уже период вырастает. Или я что-то недопонял?
Да нет, период для одной бактерии маленький.
Да, ну что я придумал и не успел написать — для каждой бактерии получаем до четырёх выражений, когда она будет в ловушке — const, если это в предпериоде или kx+b — если в цикле.
Перебираем все 4^K вариантов. Если хоть одна константа — проверка элементарная, иначе — K выражений kx+b. k <= 10K у каждого да, но как их решить одновременно без расширенного Евклида, можно поподробнее, пожалуйста?
Или решение вообще отличается?
Решение точно такое же, просто без расширенного Евклида.
Пусть у нас есть 2 арифметические прогрессии ax + b и cx + d, где b < a и d < c. Понятно, что если b - d не делится на gcd(a, c), то общих членов нет. Иначе проверим, принадлежит ли число b второй прогрессии. Если нет, то будем прибавлять к нему число a до тех пор, пока оно нам не подойдет. Ясно, что это произойдет за O(c) шагов. Теперь у нас есть прогрессия вида lcm(a, c) * x + y, где y мы только что нашли. Таким образом будем сливать по очереди первую и вторую прогрессии, потом ту что вышла с третьей и т.д.. В конце получим прогрессию Ax + B. Теперь осталось проверить, что число B не слишком маленькое (оно может не подойти к какой-то прогрессии). Если оно маленькое, то будем прибавлять A пока не станет нормальным.
А, у одной только прогрессии будет большой период, у второй маленький всё ещё. ОК, понял, спасибо большое!
Кстати, почему на первый сэмпл ответ 3? там же два шага?
Там время — это количество шагов плюс 1.
May anyone suggest a suitable method to solve 4th problem ? I only came up with the following observation.
I used 2 segment trees to handle the horizontal and vertical cases , but that scored 80 / 120 , due to exceeding the memory limit in the last 2 testcases. I think there are some tricks(coordinate compression , solving the horizontal cases then clearing the segment tree then solving the vertical cases) , but I'm not sure if they can help out.
And may anyone suggest how to approach 5-th problem ?
If you have the range of [0..2^x-1] you can easily store a segment tree in one array of integers — for values. Every other needed information is easily computed on-the-go.
You only need to do two sweep lines, one for the X queries, and another for the Y queries.
In each sweep line, you need to keep a counter that tells you the number of active triangles.
Regarding the 4th problem: First off, lets simplify the prob by assuming we deal with rectangles rather than triangles. Using that simplification we can make two arrays X and Y. where we are going to append X_min and X_max and Y_min and Y_max for each rectangle respectively. Secondly, we make two new arrays for X and Y: X' and Y' where on the i-th index we write the number of rectangles, edges of which are situated on the different sides of X[i].
This is just an idea.
The 5th problem can be solved with a simple O(N2) DP. The key observation is that any two adjacent elements in a good sequence differ by not more than 1. The reverse is also true: any sequence in which every two adjacent elements differ by not more than 1 and the first and the last elements are equal to 0 is good.
I would also say that the correct relief of length N form a bijection with correct bracket sequence of length N-1, where in N-1 spaces we can put spaces as well. For example in 3rd sample case:
The numbers represent the level of bracket sequence at a given point.
I had implemented the same idea, and it got accepted.
also we can improve this using combinatorics making the solution become O(N)
Can u explain more about the O(N) solution? I can't solve it with O(N^2) neither because of memory limit...
you use dinamic array as i think dn[N][N]
you can use dinamic array like this dn[2][N]
because f(n,k) = f(n+1,k)+f(n+1,k-1)+f(n+1,k+1)
n is the position in the array and k is the what is the array[i]
so you must only know N th and N+1 th rows .
Интересно, а какой максимально возможный ответ в 6-й задаче? В тестах жюри это
9298781157357368. А можно ли построить тест где ответ не влазит в long long?Понятно, что каждый период четный и не превосходит 104. Значит lcm пяти периодов не больше 1020 / 24, а это влазит в long long. И я сильно сомневаюсь, что период реально может быть 104.
Точно, он же четный. Тогда ясно что влазит. Я не подумал об этом и хранил ответ в паре лонг лонгов.
Just published Results.