Всем привет, у клавиатуры Кодер Арсений. В начале сентября я узнал о таком сайте, как Codeforces, где можно проходить соревнования и заниматься олимпиадным программированием. В своём блоге я буду каждый день делиться своими результатами участия в соревнованиях (чаще всего виртуальных).
Сегодня я принял виртуальное участие в Codeforces Round #832 (Div. 2).
Первая задача
Первая задача была на первый взгляд неприятная: был дан массив чисел arr, который надо было разбить на два подмассива arr_1 и arr_2 так, чтобы |sum(arr_1)| - |sum(arr_2)| было максимально возможным. И вывести максимальное значение этого выражения.
Решение я понял не сразу, но через какое-то время до меня дошло, что в данном случае больше, чем просто |sum(arr)| мы получить не сможем. И к 5 минуте 57 секунде я решил эту задачу на языке программирования python.
Вторая задача
Вторая задача меня изначально запутала и я её 2-3 раза сдал неправильно. Решение казалось мне очевидным, но я упустил одну вещь в условии. Задача была в том, что мы имеем строку "BAN" * n, нужно сделать так, чтобы подпоследовательность "BAN" больше не встречалась. Надо было посчитать минимальное количество перестановок и вывести их количество + каждую перестановку.
Я перепутал подстроку с подпоследовательностью. Для них совпадает количество возможных решений, которое лежит на поверхности ( оно равно (n+1) // 2, где // - деление с округлением вниз), но вот перестановки я делал неправильно, из-за чего подстроки пропадали, а подпоследовательности - нет.
А перестановки я сделал такими - я менял i-тую слева B с i-той справа N, пока не сделал это со всеми B и N. И после трёх неудачных попыток с неправильным ответом на втором тесте, я сдал задачу на 23 минуте 42 секунде, решив её на языке программирования python.
Третья задача
Третья задача была на теорию игр. Была игра - есть массив чисел и два игрока. Игроки по очереди меняют первый и любой другой элемент массива местами, при этом уменьшая первый элемент на 1. Тот, кто сделает первый элемент, равным 0 - проиграет. И задача после ввода массива чисел написать, кто станет победителем - игрок, который ходит первым (Алиса) или вторым (Боб)? Игроки, естественно, играют оптимально.
Первая мысль, которая приходит в голову при решении задач, где игроки ходят поочередно - это чётность. Но оптимальная стратегия игры пришла ко мне в голову достаточно быстро.
Задача сделать так, чтобы во время хода соперника у него на первой позиции всегда было минимальное число. А рано или поздно, минимальное число станет 0. Отсюда Алиса выигрывает только тогда, когда первое число - не минимальное в массиве. В противном случае выигрывает Боб.
На 31 минуте я сдал решение на языке программирования Python.
Четвёртая задача
Четвёртая задача стала моей последней. Она была на XOR. Ознакомиться с условием задачи в этот раз я вам предлагаю лично, как и предложить решение этой задачи. Я её решил и буду лайкать комментарии с правильным решением.
Условие: https://codeforces.com/contest/1747/problem/D
Сдал я решение через 1 час 38 минут после начала соревнования на языке программирования C++.
Последние 22 минуты соревнования я просто покинул, даже не ознакомившись с решением пятой задачи.
Вывод
Выводом из этого соревнования стал для меня факт, что мне нужно повторить тему побитовых операций с числами. Я потерял много времени на четвёртой задаче (целый час), половину из которого я читал в интернете про XOR, чтобы вспомнить эту тему и думать о решении.