Local Optimizations Is All You Need

Недавно maroonrk сказал, что задачу ARC142E не взяли в AtCoder Grand Contest (а взяли только в Regular), потому что боялись, что какие-то эвристические решения могут зайти. Мимо такого заявления нельзя было пройти спокойно, и надо было срочно загнать какую-то лажу в эту задачу.

Задача следующая. Есть два массива a и b (до 100 элементов в каждом, значения до 100), а также список пар (i, j). Нужно поувеличивать элементы в a так, чтобы для каждой пары (i, j) из списка выполнялось хотя бы одно из двух условий:

• a[i] >= b[i] && a[j] >= b[j].
• a[i] >= b[j] && a[j] >= b[i].

При этом каждый раз когда увеличиваем a[i] на 1, платим одну монету. Нужно минимизировать количество потраченных монет.

Общая идея

Пусть мы откуда-то узнали, в каком порядке должны быть отсортированы a[i] в конце. Тогда восстановить сами a[i] оптимально довольно легко. Пусть информация про сортировку нам известна в формате массива rank, такого что: rank[i] < rank[j] обозначает, что a[i] < a[j]. Тогда если есть ограничение на пару (i, j), то оптимально будет a[i] сделать хотя бы min(b[i], b[j]), а a[j] сделать хотя бы max(b[i], b[j]).

Самая простая версия — будем генерировать случайную перестановку rank, строить ответ исходя из нее, считать стоимость. И повторять пока есть время. Это решение получает несколько АС, но большинство WA:

Локальные оптимизации

Локальные оптимизации это очень клевая техника, которая часто используется в marathon-style задачах, но иногда ее можно применить и в обычных контестах. Идея в том, чтобы немного изменять текущее решение, и применять только те изменения, которые улучшают итоговый результат.

В случае с перестановками типичный пример локальной оптимизации — поменять местами два соседних элемента. Другая возможная оптимизация — взять случайный элемент, и переставить его в случайное место. Именно ее и будем использовать.

Для простоты имплементации массив rank сделаем не перестановкой, а массивом даблов. Тогда основная часть решения будет выглядеть так:

let calc_score = |rank: &[f64]| -> usize {
    let mut cur_values = init_values.to_vec();
    let mut cur_res = 0;
    for (fr, to) in all_restrictions.iter() {
        let need = max(need[fr], need[to]);
        if rank[fr] >= rank[to] && cur_values[fr] < need {
            cur_res += need - cur_values[fr];
            cur_values[fr] = need;
        }
    }
    cur_res
};

let mut rnd = Random::new(787788);
let mut rank = gen_vec(n, |_| rnd.gen_double());
let mut best_res = calc_score(&rank);

let start_time = Instant::now();
while start_time.elapsed().as_millis() < 1000 {
    let pos = rnd.gen(0..n);
    let new_val = rnd.gen_double();
    let old_val = rank[pos];
    rank[pos] = new_val;
    let new_res = calc_score(&rank);
    if new_res <= best_res {
        best_res = new_res;
    } else {
        rank[pos] = old_val;
    }
}

Такое решение уже работает гораздо лучше:

Во время дорешивания на AtCoder можно смотреть названия тестов, в данном случае они выглядят так (тут только часть тестов):

С одной стороны почти все случайные тесты это решение проходит, но с другой есть еще много "maximal" тестов, которые получают WA. Но есть один обнадеживающий момент — какой-то максимальный тест все-таки прошел:

Оптимизации

Часто при написании локальных оптимизаций, нужно уметь быстро пересчитывать ответ при каждом изменении. Сейчас мы делаем это за O(n^2), потому что должны посмотреть на каждое ребро. Но поскольку мы меняем rank только одного элемента, то можно пересчитать ответ за O(n).

Сам процесс оптимизации довольно скучный, так что не будем его тут описывать.

Но важно понимать, что лучше всего начинать с простого решения, чтобы проверить, что локальные оптимизации вообще работают, и только потом начинать оптимизировать.

После оптимизаций результат был такой:

После изменения rand seed, суммарный результат остался такой же, но разбиение по тестам было другое:

Из этого можно было сделать вывод, что шанс есть :)

Была идея, что можно сделать какие-то константные оптимизации, после которых решение успеет проверить больше перестановок, и в итоге получить АС.

После довольно долгих оптимизаций результат был примерно такой:

Причем в зависимости от rand seed, не работает разный тест...

Последняя оптимизация

Локальные оптимизации это хорошо, но еще лучше когда исходное решение уже сгенерировано хорошей эвристикой. Хотелось как-то учитывать, что если исходное значение элемента уже большое, то и rank должен быть скорее всего больше (но не всегда).

В итоге сработал какой-то такой код:

fn gen_initial_ranks(rnd: &mut Random, start: &[usize], need: &[usize]) -> Vec<usize> {
    let n = start.len();

    let mx = rnd.gen(10..200i32);
    let a = rnd.gen(-mx..mx);
    let b = rnd.gen(-mx..mx);
    let mut scores = gen_vec(n, |pos| {
        (
            pos,
            start[pos] as i32 * a + need[pos] as i32 * b + rnd.gen(0..mx * mx),
        )
    });
    scores.sort_by_key(|(_, y)| *y);
    let mut ranks = vec![0; n];
    for i in 0..n {
        ranks[scores[i].0] = i;
    }
    ranks
}

После этого решение уже заходит с довольно большим запасом по времени:

Вывод

Лучше писать нормальные решения. Но когда правильное решение не придумывается, важно уметь запихивать и то, чего не хотели авторы задачи.