Блог пользователя Vasya.V

Автор Vasya.V, 14 лет назад, По-русски
1) В силу небольших ограничений в задаче можно в цикле перебирать значения n и проверять условие
for (int n = 1; n <= Tn; n++)
{
    if (n * (n + 1) / 2 == Tn)
    {
        cout << "YES\n";
        return;
    }
}
cout << "NO\n";

2) Определим граф, где буквы A, B, C - вершины, и если выполняется x < y, то существует ребро y -  > x. Далее проведем топологическую сортировку. Если при выборе следующей вершины при поиске мы можем перейти в помеченную, но не использованную вершину, значит найден цикл, и надо вывести "Impossible".

3) Задача решается переборо 6! = 720 перестановок. Для каждой перестановки первые 3 слова будем располагать горизонтально, остальные - вертикально. Будем располагать слова так:
  1. hor[0], ver[0] - влево-вверх
  2. hor[2], ver[2] - вправо-вниз
  3. hor[1]: (len(ver[0]) - 1, 0)
  4. ver[1]: (0, len(hor[0]) - 1)
Пусть теперь N = len(ver[1]), M = len(hor[1]).
Для того, чтобы существовало решение, необходимы следующие условия:
  1. len(hor[0]) + len(hor[2]) == M + 1 // углы восьмерки
  2. len(ver[0]) + len(ver[2]) == N + 1  // углы восьмерки
  3. len(hor[0]) >= 3 && len(hor[2]) >= 3 && len(ver[0]) >= 3 && len(ver[2]) >= 3 // восьмерка невырождена
  4. буквы на началах/концах соответствующих строк совпадают
  5. совпадают буквы при пересечении hor[1], ver[1]
При выполнении этих условий получаем правильную доску размером N x M, обновляем ответ.
Замечание: В C++ если хранить доску в виде vector<vector<char> > или vector<string>, то для обновления ответа можно просто использовать оператор "<".

4) Рассмотрим не самый эффективный алгоритм, тем не менее проходящий по времени, со сложностью O(mCn5log(Cn5)).
Рассмотрим 1 ответ системы: <number, v>. Общее число вариантов шифра будет Cnv - не очень большое число, поэтому можно их просто сгенерировать. Объявляем это множество вариантов текущим. Далее, для каждого нового ответа генерируем множество возможных шифров, пересечение текущего и нового множеств объявляем текущим.
В итоге получаем некое множество. Надо исключить из него элементы, которые уже были в ответах системы, и вывести его размер.

PS: В комментариях приветствуются более эффективные алгоритмы

5) Приведу пример решения за O((n + m)log(n + m)).
Предварительно исключим из рассмотрения стенки до которых снаряд не может долететь ни при каких условиях: x > v2 / g
В силу условия α < =π / 4 выполняется следующее
  1. Функция дальности полета от угла монотонная
  2. Функция высоты при фиксированной дальности от угла монотонная
Этот факт позволяет сопоставить каждой стенке отрезок углов атаки [α1, α2]. Если снаряд выпущен под углом из этого отрезка, то он попадает в стенку. Эти углы можно находить, решая уравнение (оно окажется биквадратным), но опять же в силу монотонности можно воспользоваться бинарным поиском.
Отсортируем стенки по координате x. Теперь задача свелась к следующей: для каждого выстрела определить минимальный индекс стенки, при этом угол выстрела лежит между углами атаки стенки. А эту задачу можно решать деревом отрезков для минимума с возможностью обновления на интервале. Вначале заполним дерево значением KInf. Далее, для каждой стенки будем делать update(α1, α2, index). Потом пройдемся по запросам. Если getMin(α) == KInf, значит снаряд благополучно приземлится на землю, иначе врежется в стенку с индексом getMin(α).
Разбор задач Codeforces Beta Round 44 (Div. 2)
  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

14 лет назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

Альтернативное решение задачи D.

Воспользуемся методом деления пополам.

Будем перебирать все возможные маски длины n/2. Предположим, что зафиксированная маска является первой половиной пароля не противоречащего входным данным. Для каждой такой маски будем формировать вектор (далее вектор А), в котором i-й элемент равен количеству совпадений первой половины i-ого введенного пароля и нашей зафиксированой маски. Для каждого такого вектора посчитаем сколько он встречается, для этог оможно использовать map.

Аналогичным образом перебираем и вторую часть, формируя при этом вектор совпадений (далее вектор B) для второй части паролей и зафиксированой маски.

Обозначим вектором S вектор ответов системы на введенные пароли. Тогда перебирая вторую половиу пароля у нас будет столько возможных паролей имеющих такую же вторую половину, как и наша маска, и не противоречащих условию, сколько у нас сужествует векторов А равных S-B. 

Асимптотика этого решения равна O(2^(n/2)*m*n). Используя хэш мапу можно добиться асимптотики O(2^(n/2)*m) . Хочу заметить, что это решение не зависит от ограничения на количество верных цифр в введенных Васей паролях.

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как вариант, в задаче B в силу малого кол-ва монет можно было сгенерировать все перестановки из этих 3х монет и проверить их на "отсортированность".
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Какое простое решение у B :)
Я когда прочитал на контесте решил действовать в лоб. Ну и наркоманский код у меня получился, но получил AC и написал относительно быстро его(~ 20 минут)
http://codepad.org/H026teJ3
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Напишу здесь, чтобы не создавать новую тему.
Если учавствовал в соревновании вне конкурса, а потом зарегистрировался на дорешивание, то во вкладке "Мои послыки" пропадают сабмиты с соревнования, остаются только сабмиты с дорешивания.
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I did some pretty hardcore implementation in Div2B "so called proper brute force" can't be more brute have a look 60172369

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    We can see this problem as a directed graph, so we have to ensure that the following condition should be veryified to have an answer:
    1. Every node in the graph should have not one degree at the same time.
    2. There are no bidirectional edges.
    With the first condition we ensure that there isn't a cycle, with the second we don't have a contradiction.
    My sub: 60185706