357A - Кружок школьников

В задаче нужно было перебрать все варианты проходного балла от 1 до 100 и для каждого варианта посчитать, какие получаются размеры групп. Если нашли подходящие разбиения, выводим соответствующий одном из них проходной балл, иначе выводим 0.

357B - День Флага

Будем обрабатывать танцы в порядке их исполнения, и определять цвета формы участвующим в них танцорам. Если в текущем танце нет ни одного ранее танцевавшего участника, то назначим всем троим танцорам различные цвета формы произвольным образом. В случае же, если есть один такой танцор, тогда для него цвет формы уже известен. Два других цвета формы произвольным образом распределим между остальными двумя танцорами.

356A - Рыцарский турнир

Пусть в очередной битве (l, r, x) сражается K рыцарей. Тогда в этой задаче было достаточно научиться находить всех этих рыцарей за время O(K) или O(KlogN). Рассмотрим несколько способов сделать это.

Способ первый: хранить множество рыцарей в std::set (C++) или в TreeSet(Java). Тогда в C++ мы можем использовать метод lower_bound для нахождения самого первого живого рыцаря в отрезке, а потом итерироваться по множеству, переходя каждый раз к следующему по номеру живому рыцарю. В Java мы бы для этих целей использовали метод subSet.

    set<int> alive;
    for (int i = 0; i < n; i++)
        alive.insert(i);
        
    for (int i = 0; i < m; i++) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        l--, r--, x--;        
        set<int>::iterator it = alive.lower_bound(l);
        vector<int> toErase;        
        while(it != alive.end()){
            int cur = *it;            
            if(cur > r)
                break;                
            if(cur != x){    
                toErase.pb(cur); answer[cur] = x;
            }
            it++;
        }

        for (size_t j = 0; j < toErase.size(); j++)
            alive.erase(toErase[j]);
    }

Способ второй: определим массив next, значения в котором будут иметь следующий смысл:

• если рыцарь v живой, то next[v] = v;
• если рыцарь v выбыл, то next[v] указывает на некоторого рыцаря u > v (next[v] = u), такого, что между v и u нет живых рыцарей.

Тогда для того, чтобы для рыцаря v найти следующего по номеру живого рыцаря, нужно пройти по ссылкам next до первого живого рыцаря. Чтобы не ходить многократно по одним и тем же ссылкам, применяем эвристику сжатия путей из DSU. Надо учитывать случай, когда текущий рыцарь последний и уже выбыл из турнира.

    int getNext(int v){
        if(next[v] == v)
            return v;
        return next[v] = getNext(next[v]);
    }

    ...

     int cur = getNext(l);
     while(cur <= r){
        if(cur == x){
            cur = cur + 1;
        }else{
            answer[cur] = x;
            next[cur] = cur + 1;
        }

        cur = getNext(cur);
    }

356B - Ксюша и Хемминг

Обозначим первую строку за x, |x| = lenX, вторую строку за y, |y| = lenY. Пусть L=НОК(lenX, lenY). Очевидно, что для тех больших строк a и b, которые описаны в условии, L является периодом, поэтому достаточно решить задачу для длины L, а затем умножить ответ на . Зафиксируем позицию i в строке x и посмотрим, с символами в каких позициях в строке y будет сравниваться символ x_i. Из несложных соображений теории чисел это будут такие позиции 0 ≤ j < lenY, что i ≡ j (mod g), где g=НОД(lenX, lenY). Для каждого возможного остатка r от деления на g и каждого символа c можно посчитать count(r, c) — количество символов c, которые встречаются в y на позициях j таких, что j mod g = r. Тогда при вычислении расстояния Хэмминга напротив символа x_i будет ровно count(i mod g, x_i) таких же символов, а все остальные сравнения прибавят единицу к расстоянию Хэмминга.

private void solve() {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong(), m = in.nextLong();
        String x = in.next(), y = in.next();
        int lenX = x.length(), lenY = y.length();
        int g = gcd(lenX, lenY);
        long L = lenX * (long)lenY / g;
        long answer = L;
        int[][] count = new int[g][26];
        for (int j = 0; j < lenY; j++) {
            count[j % g][y.charAt(j) - 'a']++;
        }
        for (int i = 0; i < lenX; i++) {
            answer -= count[i % g][x.charAt(i) - 'a'];
        }
        System.out.println(answer * (n * lenX / L));
    }

356C - Купе

В данной задаче требовалось придумать какой-нибудь правильный жадный алгоритм. Один из правильных подходов делает следующее:

1. Сначала соединяет все <<двойки>> с <<единичками>> (образуются <<тройки>>), путем пересаживания <<единичек>>.
2. Рассматривает два случая в зависимости от того, <<единичек>> больше изначально или <<двоек>>. Если больше единичек, то пробует соединять оставшиеся после первого пункта одинокие <<единички>> в тройки, если <<двоек>>, то пробует из каждых трех <<двоек>> образовать две <<тройки>>.
3. После применения пункта два, могут остаться еще какие-то <<единички>> или <<двойки>>. Нужно разобрать случаи того, что осталось, руками (случаев будет мало).

В задаче нужно руководствоваться скорее здравым смыслом, нежели какими-то известными жадными соображениями. Неплохо помогает написать стресс-тестирование с наивным решением (обходом в ширину), чтобы убедиться в корректности вашей жадности.

356D - Монеты и мешочки

Очевидно, что мешки и отношения "лежит непосредственно в" образуют лес. К каждой вершиной должно быть связано некоторое число c_i — количество монет в соответствующем мешке. Тогда, если мы для каждой вершины посчитаем величину f_i — сумма значений c_j в поддереве этой вершины, то должны выполняться следующие условия:

• f_i = a_i
• сумма f_i по вершинам, которые являются корнями деревьев, равна s.

Очевидно, что мешок с наибольшим a_i будет корнем какого-то из деревьев. Также достаточно легко понять, что решение задачи существует тогда и только тогда, когда можно выбрать такой набор a_i1, a_i2, ..., a_ik, что сумма a_i1 + a_i2 + ... + a_ik равна s, причем один из мешков с наибольшим a_i входит в такой набор. В одну сторону это очевидно, в другую покажем конструктивно: пусть у нас есть такой набор. Тогда все мешки, вошедшие в набор, кроме самого большого, будут "отдельными", то для них c_i = a_i, а все не вошедшие мешки мы последовательно положим друг в друга и в первый, получив матрешку (т.е. дерево с корнем в самом большом мешке будет ориентированной цепью).

Задача свелась к задаче о наборе суммы s из предметов a₁, ... a_n. Это задача является NP-полной, и обычно в подобных ограничениях решается так: пусть T(i, j) = 1, если можно набрать сумму j, используя какие-то из первых i предметов, и T(i, j) = 0 в противном случае. Тогда . Заметим, что i-ая строка этой таблицы зависит только от (i - 1)-ой, поэтому можно хранить в памяти не всю таблицу, а только две строки. Дальше мы будем использовать то, что значения в таблицы — это нули и единицы, поэтому мы можем хранить строчки таблицы побитово, в массиве из 4-битных целых чисел. Тогда, чтобы получить очередную строчку, мы должны сделать побитовое ИЛИ предыдущей строки и предыдущей строки, сдвинутой на a_i бит. Все это можно сделать за действий, поэтому выяснить, можно ли набрать сумму s, можно примерно за операций. Однако, тут нужно применить один трюк для того, чтобы восстановить, какие именно предметы нужно взять. Давайте для каждого значения суммы j будем запоминать величину first(j) — номер такого предмета, после рассмотрения которого стало возможно набрать сумму j. Это позволит нам восстановить ответ.

356E - Ксюша и строковая задача

Во время контеста большинство участников писали решение задачи очень похожее на авторское. Одно из авторских решений (более простое) использует полиномиальные хеши (хотя есть решения и без них). Кратко опишем решение.

1. Для каждой позиции i посчитаем с помощью хешей максимальное такое L_i, что подстрока s[(i - L_i + 1)..(i + L_i - 1)] является строкой Грея. Так же посчитаем максимальное такое P_i, что подстрока s[(i - P_i + 1)..(i + P_i - 1)] отличается от строки грея не более чем на один символ. Очевидно, что P_i ≥ L_i. Причем если P_i > L_i, то также сохраним позицию символа и символ, который различает подстроку и некоторую строку Грея.

2. Понятно, что если бы не нужно было менять символы, тогда ответ был бы равен , где f(L) = 1² + 3² + 7² + ... + L². Посчитаем ответ, без замены символов.

3. Теперь переберем позицию и новый символ, на который будем менять символ в данной позиции. Как понять, на сколько поменяется ответ на задачу? Посмотрим на все строки грея, вхождения которых перекрывают зафиксированную позицию. После изменения символа на другой, они все перестанут быть строками грея (вычтем их длину в квадрате из ответа). Посмотрим на все строки Грея, которые отличаются ровно в одной зафиксированном символе от некоторой подстроки строки. После изменения на этот символ они все добавятся в ответ (их длину в квадрате нужно добавить в ответ).

4. Суммируя вышесказанное, с помощью P_i L_i нужно, используя update на отрезке в offline, посчитать для каждой позиции и символа, на сколько поменяется ответ на задачу, если в данной позиции поставить этот символ. Далее нужно обновит ответ всеми возможными значениями.