Разбор задачи 2013D «Cave»

Презентацию подготовили Белых Евгений и Проскурин Александр

Постановка задачи В задаче нам было дано N дверей и N выключателей. Каждый переключатель соответствует какой-то двери, при этом в одном из положений «вверх» или «вниз», переключатель открывает свою дверь. Кроме того, мы видим двери до первой закрытой. В задаче нам было дано N дверей и N выключателей. Каждый переключатель соответствует какой-то двери, при этом в одном из положений «вверх» или «вниз», переключатель открывает свою дверь. Кроме того, мы видим двери до первой закрытой.

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

Решение первой подзадачи В этой подзадаче переключатель i относится к двери номер i. Чтобы решить эту подзадачу сделаем следующее: будем подряд идти по всем переключателям, и для каждого очередного переключателя будем пробовать включить его «вверх» или «вниз». Затем запомним, в какого положении соответствующая ему дверь будет открыта. Так как дверей всего 5000, а запросов мы можем сделать 70000, то это решение будет работать верно для данной подзадачи, сложность – O(N) В этой подзадаче переключатель i относится к двери номер i. Чтобы решить эту подзадачу сделаем следующее: будем подряд идти по всем переключателям, и для каждого очередного переключателя будем пробовать включить его «вверх» или «вниз». Затем запомним, в какого положении соответствующая ему дверь будет открыта. Так как дверей всего 5000, а запросов мы можем сделать 70000, то это решение будет работать верно для данной подзадачи, сложность – O(N)

Решение второй подзадачи В данной нам заранее дано, что верное положение всех переключателей – положение «вверх». Тогда будем делать следующее: будем брать все переключатели по очереди и переключать их в положение «вниз». Сделав это, мы увидим, какая дверь закроется, следовательно она и относится к текущему переключателю. Запомнив ответы на все запросы, мы и найдем ответ. Сложность решения – O(N) В данной нам заранее дано, что верное положение всех переключателей – положение «вверх». Тогда будем делать следующее: будем брать все переключатели по очереди и переключать их в положение «вниз». Сделав это, мы увидим, какая дверь закроется, следовательно она и относится к текущему переключателю. Запомнив ответы на все запросы, мы и найдем ответ. Сложность решения – O(N)

Решение третьей подзадачи Сначала узнаем верное положение для первой двери. Для этого сначала включим все переключатели в положение «вверх». Если она будет открыта, то «вверх» - это и есть верное положение для нее, иначе верное положение для нее – «вниз». Теперь поставим все переключатели в верное для первой двери положение. Будем идти сначала и менять положение выключателя на противоположное. Сначала узнаем верное положение для первой двери. Для этого сначала включим все переключатели в положение «вверх». Если она будет открыта, то «вверх» - это и есть верное положение для нее, иначе верное положение для нее – «вниз». Теперь поставим все переключатели в верное для первой двери положение. Будем идти сначала и менять положение выключателя на противоположное.

Если после очередного переключения первая дверь изменит свое положение, то значит очередной переключатель относится к ней. Теперь, если мы перестанем в наших запросах изменять положение данного переключателя, то первая дверь всегда будет открыта и мы можем использовать аналогичный алгоритм для всех последующих дверей. Итоговая сложность и количество запросов – O(N^2) Если после очередного переключения первая дверь изменит свое положение, то значит очередной переключатель относится к ней. Теперь, если мы перестанем в наших запросах изменять положение данного переключателя, то первая дверь всегда будет открыта и мы можем использовать аналогичный алгоритм для всех последующих дверей. Итоговая сложность и количество запросов – O(N^2)

Решение четвертой и пятой подзадач Воспользуемся алгоритмом бинарного поиска. Сначала переключив все переключатели в положение «вверх» узнаем верное положение для первой двери. Будем хранить границы l и r – границы отрезка, где может лежать наш переключатель. Изменив положение первой половины выключателей отрезка, мы по изменению положения двери сможем определить, в какой половине текущего отрезка лежит наш переключатель и перейти к решению задачи для этой половины. Воспользуемся алгоритмом бинарного поиска. Сначала переключив все переключатели в положение «вверх» узнаем верное положение для первой двери. Будем хранить границы l и r – границы отрезка, где может лежать наш переключатель. Изменив положение первой половины выключателей отрезка, мы по изменению положения двери сможем определить, в какой половине текущего отрезка лежит наш переключатель и перейти к решению задачи для этой половины.

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

Оценка сложности Для определения выключателя для каждой двери мы делаем Для определения выключателя для каждой двери мы делаем N + N / 2 + N / 4 + … + 1 = 2 * N действий. Также каждый раз уменьшая отрезок в два раза мы делаем logN запросов. Итого O(N ^ 2) действий и O(N * logN) запросов.

Для решения данной задачи мы пользовались рекурсивными вызовами функций. Для решения данной задачи мы пользовались рекурсивными вызовами функций.

Примерное время решения данной задачи составляет: минут на придумывание идеи и минут на написание кода, отладку и тестирование программы. Примерное время решения данной задачи составляет: минут на придумывание идеи и минут на написание кода, отладку и тестирование программы.