Странно, что никто не запостил, но 10 мая, в 20:00 МСК начнется SRM 620
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3741 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3489 |
| 7 | Radewoosh | 3483 |
| 8 | Kevin114514 | 3442 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | atcoder_official | 162 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | nor | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.12.2024 04:30:49 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
It coincides with TOKI14 run 2
Sam lalka(
Da ya shutkuyu prost))
Странные дела творятся, не смог зайти в арену: то your arena does not support что-то, то your login request timed out. И пару раундов назад такое же было. Я расстроен(
Unable to parse markup [type=CF_MARKDOWN]
Казалось бы, действительно, int — так себе аллокатор.
Me too so my score in 250 is low just discovered that function name is sort :D
so I make another function outside it called SRT then i add sort function inside it :D
actually I don't know why the writer use sort as a function name :( :(
Good example showing that
using namespace stdis not an appropriate statement in C++ program developing (though almost every contestant does it)When you're going to use multiple libraries in some project, you will figure out that using namespace really harms your program
Жаль, что в А не ломались решения, использующие в худшем случае несколько миллионов операций с сетами. 2 штрафные попытки взлома из-за этого :(
Здесь была написана фигня =)
a = a — b
Да, я не прав.
Я локально запустил программу с двумя миллионами создаваемых элементов в
map <pair <int, int>, int>, увидел 0.7 секунды и успокоился.А каким тестом ломать перебор в 500?
Какая основная идея в DIV1-500 ?
У красных в моей комнате есть решение с DFS, есть решение без него. Но ни то, ни другое не понял.
Можно просто жадно добавлять с конца то, что не противоречит конфигурации. Если добавили всё что получилось, а сортировка всё ещё неправильная, значит Impossible.
Решение. Во-первых, применять один и тот же порядок два раза бесполезно.
Будем строить ответ с конца. Изначально все элементы образуют один класс.
Найдем какой-нибудь неиспользованный порядок, который согласован, и применим его последним. Порядок можно применять, если для всех соседних в одном классе, он такой как надо. Если можно применять, применим.
При этом какие-то классы распались на части.
В конце, все классы должны быть упорядоченны (то есть в том порядке, в котором было изначально).
Строго не доказывал, если махать руками, все действия остаются возможными, поэтому если применим будет не хуже.
У меня была идея, но она упала. Как будет дорешка — смогу точно сказать, идея лажа или реализация.
В общем, для пары параметров определяем, могли ли они следовать друг за другом в цифровой сортировке. Утверждается, что если могли, то если мы возьмём элементы с одинаковым первым параметром, они будут отсортированы по второму параметру. Также добавляем параметр, равный для каждого кандидата его начальному положению. И помечаем параметры, которые могут быть замыкающими, то есть, в итоге у нас посортировано по ним. Моё предположение: ответ есть, если есть путь по параметрам от добавленного фиктивного к любому "хорошему".
Похоже, идея действительно неправильная, не обращайте внимания
For Div2 500, I thought that for a solution to exist, c = pa + qb, d = ra + sb, should be satisfied where p,q,r,s are integers. So, after searching I came to know that Linear Diophantine Equation is related to this. How exactly can I solve this problem using the concept of linear diophantine eqn? I know that we can solve the same problem in different ways, but I want to know if it can be solved using this algorithm, as it was the first thing that came to my mind.
Вот это скорость: рейтинг обновили через 17 минут после окончания раунда.
Как решать Hard?
Гауссом по модулю два. Каждое число — переменная. Считаем число независимых переменных, ответ — 2ans. Условия — на строки, на столбцы, а дальше каждое число развалили на простые и получили еще X строк, где X — количество различных простых.
Совершенно стандартная задача на линейные уравнения по модулю.
Посмотроим такую систему уравнений по модулю 2, что каждое решение — это одной из решений нашей задачи. В этой системе будет n2 переменных, каждая переменная a[i][j] отвечает за то, берем мы в ответ соотвествующее число или нет. Уравнения, которые нужно записать:
В последнем уравнении p — это простое число (одно из тех, которые содержатся в заданных числах). power(p, x) — в какой степени число p встречается в x.
Дальше нужно алгоритмом Гаусса найти ранг матрицы r, ответ на задачу 2n2 - r.
Any idea on Div1 800? I thought about some dp[i][j][k] = number of solutions given the parity of the columns (i = bitmask), the current line (j) and k = the current square free part of the product (k should be compressed). Didn't find a good way of compression or a fast enough recurrence. Am I on the right path or am I overlooking something? Thanks in advance.
It's classic exercise for Gauss elimination.
You have n2 variables, 2n rows to fix parity of number of selected numbers in each row/column and then we have one additional row for each prime number which occurs in the input.
After you solve the system, you will either get contradiction or number of free variables. Answer is 2 to this number.
How to solve Div2 1000)?
I have an idea, but I don't know if it's correct. I'll try to code it, and will post UPD with results
Let's find the answer for n = 4 first. Now we can use inclusion-exclusion principle to calculate probability for at least one event (connected component with >= 4 verteces) happen.
It is more convenient to answer the complementary question of what is the probability that all connected components are of size at most 3. This can be done with a one-dimensional dynamic programming with the state being the number of vertices. To build the transitions observe that there are only three possible choices for Vertex 1: it may be in a component by itself, it may be connected to exactly one other vertex and form a component with it or it can be in a component of size 3.
any idea for div1 500?
We can use greedy algorithm, If some skill not contradict, we take this skill to sort. Take skills while it is possible. :)