В данной задаче нужно было проверить, выполняются ли ограничения, описанные в условии. Чтобы это сделать, можно было завести два множества. В одно множество сложить диагональные элементы матрицы, в другое — остальные. Элемент ai, j стоит на главной диагонали, если i = j, и стоит на побочной, если i = n - j + 1. После того, как мы сложили все элементы в множества, нужно проверить, что размеры обоих множеств равны единице, и элементы этих множеств различны.
В этой задаче нужно было заметить, что пройдя расстояние 4·a, Валера окажется в той же точке, откуда стартовал. В момент, когда Валера получит i-ое питание, он пробежит расстояние i·d. Давайте посчитаем величину — сколько полных кругов пробежит Валера по стадиону. Тогда на своем последнем кругу Валера уже пробежал L = i·d - c·4·a метров. В зависимости от этого L можно легко определить позицию Валеры. Например, если 2·a ≤ L ≤ 3·a, то Валера будет находиться в точке с координатами (3·a - L, a). Аналогичным образом разбираются остальные 3 случая.
Заметим, прежде всего, что в массиве d должен быть один и только один 0. При этом d[start] = 0 обозначает, что start именно та вершина, от которой Валера считал расстояние до всех остальных. Заметим, что любая вершина u, для которой d[u] = i должна быть соединена ребрами только с вершинами v, у которых d[v] ≥ i - 1. При этом хотя бы для одной вершины v0 из соседей u должно выполняться d[v0] = i - 1. Будем строить искомый граф добавляя по одной вершине в порядке увеличения их расстояния до start. Изначально в нашем графе будет одна вершина с номером start. При добавлении вершины u с d[u] = i рассмотрим все вершины v, у которых d[v] = i - 1. Выберем среди таких вершин вершину минимальной степени. Если эта степень равна k, то ответа не существует. Иначе добавим в граф вершину u и ребро (u, v). Если вершин с расстоянием до start равным i - 1 нет, то ответ также - 1. В противном случае после добавления всех вершин, мы получим граф, удовлетворяющий условиям задачи, который при этом будет деревом, а значит количество ребер в нем n - 1 ≤ 106.
Задача решается методом динамического программирования. Будем считать d[i][type] — количество корректных способов заполнить префикс полоски длиной i так, что последняя заполненная клетка имеет один из пяти типов. Типы последних клеток будут следующие:
в клетке записано "0"
в клетке записано "1" и слева от нее стоит бомба
в клетке записано "1" и слева от нее нет бомбы
в клетке записано "2"
в клетке находится бомба
Когда мы хотим заполнить очередную клетку, мы перебираем, что туда запишем, и проверяем два условия. Во-первых в заданной строке значение заполняемой клетки должно либо совпадать с тем, что мы хотим записать, либо быть равно "?". Во-вторых новый префикс должен оставаться корректно заполненным. Это значит, например, что если мы находимся в состоянии (i, 1) (то есть в последней заполненной клетке записан "0"), то в следующую клетку мы можем либо записать "0" и перейти в состояние (i + 1, 1), либо записать "1" и перейти в состояние (i + 1, 3). Записать "2" мы не можем, так как у клетки с "2" оба соседа должны быть заполнены бомбами. Поставить бомбу после "0" мы не можем по очевидным причинам. Обратите внимание, что записав "1" после "0" мы переходим именно в состояние (i + 1, 3), а в состояние (i + 1, 2) мы можем перейти лишь записав "1" после бомбы. Аналогичным образом разбираются остальные переходы динамики.
Рассмотрим случай, когда последовательность ходов робота заканчивается буквой "R". Если она заканчивается на "L", то можно заменить в исходной строке все "L" на "R" и все "R" на "L" и ответ от этого не изменится. Покажем, что количество препятствий, которое потребуется Валере, не превосходит 1. Предположим Валера поставил препятствия в какие-то клетки. Будем говорить, что номер препятствия — это номер клетки в которой оно стоит. Рассмотрим среди всех препятствий с отрицательными номерами самое правое (обозначим его obs1), а среди препятствий с положительными — самое левое (обозначим его obs2). Очевидно, что робот не сможет оказаться левее препятствия obs1 и правее obs2. Поэтому требуемое количество препятствий не превосходит двух. Покажем, что Валере не нужно ставить препятствия в клетки с номерами больше нуля. Предположим он поставит препятствие в клетку с номером a > 0. Если робот ни разу не попытается сходить в эту клетку, то, очевидно, препятствие лишнее. Если в какой-то момент робот пытается пойти в клетку a, то в последующем он посетит финишную клетку более одного раза. Это так, потому что на последнем ходу роботу нужно пойти направо, но из клетки a - 1 направо пойти нельзя, а все клетки, которые левее уже были посещены. Таким образом мы получаем, что Валере потребуется не более одного препятствия, которое должно иметь номер меньше нуля.
Давайте теперь проверим, может ли Валера обойтись вообще без препятствий. Если может, то робот не пропустит ни одного хода и успешно закончит выполнение инструкции в какой-то клетке. Тогда Валера может выбрать только эту клетку в качестве финишной и ответ на задачу в этом случае равен единице. Остается случай, когда Валера должен поставить одно препятствие.
Заметим, во-первых, что по тому, где Валера поставил препятствие, однозначно восстанавливается финишная клетка. Это значит, что количество способов выбрать препятствия и финишную клетку, равно количеству клеток, в которые нужно поставить одно препятствие. Предположим Валера поставил препятствие в клетку с номером b < 0 и робот успешно закончил инструкцию. Заметим, что в этом случае робот пропустит какие-то ходы типа "L", выполнит все ходы типа "R" и последним своим ходом пойдет направо в какую-то не посещенную клетку. Если теперь мы подвинем наше препятствие на одну клетку вправо, то от этого робот может лишь пропустить больше ходов типа "L". Это значит, что финишная клетка может лишь подвинуться вправо. Но так как в прошлый раз мы ее посетили последней, то и новую финишную клетку мы посетим последней. Это в свою очередь значит, что существует какая-то клетка p < 0 такая, что если мы поместим препятствие во все клетки c ≥ p, то робот сможет успешно выполнить инструкцию, а если поместим препятствие в клетку d < p, то не сможет. Эту клетку p можно найти при помощи бинарного поиска и простого моделирования за O(n) на каждой его итерации. Таким образом получаем решение за O(n log n).
probably for the first time in my life, i have used the function
fmod
of C++ (to solve problem B).i always used to think this was a useless function! :D
fmod is a great function... but less of people know about it...
Oh, I was seeking for such a function... Thanks anyway.
It's so great.Thank you for sharing this function.
Hi,
I've got a question about Problem E. I think the solution doesn't always exist, but the problem description doesn't mention this and neither does the editorial.
Let RLR be an example. If we don't place any obstacles, we end at position 1, which has been visited before. We can't place an obstacle on position 0, so the only other option is to place the obstacle at position 1. In that case, we end at position 0, which is also an invalid result. What's the correct answer for these cases?
A similar case is found in test#4 in system test ... The output should be zero at that case.
Кто-нибудь может объяснить, почему
D:=D — 4*a*trunc(D / (4*a) ); — это правильно, а
While D >= a*4 do D := D — a*4; — это неправильно ?
WA17
AC
UPD. problem B
Странные проблемы с точностью. Если заменить real на extended, то все работает
For problem E I have an O(n) algorithm: http://codeforces.me/contest/404/submission/6085167. We should set 0 or 1 obstacle only. If we don't set any obstacle, and the robot make a valid way, just print 1. Else, all I need to find is the last position of the robot and the minimum position of the robot if I set an obstacle on position x(x>0).
For the problem E I have an O(n) algorithm: http://codeforces.me/contest/404/submission/6085167. I only set 0 or 1 obstacle on the line. If I don't set any obstacle, and the robot makes a valid way, just print 1. Else, all I need are the minimum position of the robot for all process and the last position if I set an obstacle on position "pos" (pos>0).
nice algorithm~~~
I don't have time to solve problem D
I'm getting a wrong answer bcz of 0.00014 relative error in prob B Marathon of DIV -2.I'm unable to think of what exactly needs to be done to get an AC.Here is my code:-
import java.util.*;
public class Main {
In problem C, Why last test case i.e.
5 4
0 1 1 1 4
returns '-1' ?
can this be the answer :
4
1 2
1 3
1 4
2 5
your answer is valid if input 5 4 0 1 1 1 2
well, there is no vertex can be in distance 4 if there is no vertex in distance 2 and 3. so there are no answer
That means all the edges are of 1 unit length. Am i right? if yes, then it is not mentioned in question.
exactly. its been clarified during the contest
Problem C. Restore Graph ***** The distance between two vertices is the minimal number of edges in the path between themc
Thanks. Just checked.
Can anyone explain me Minesweeper 1D in detail. I'm unable to find out the recurrence ? If you have code for this question then please add comments in Code so that I'm able understand the logic as well as Code . Thank You !!!
It is really easy!!!
For Problem C — Restore Graphs. What is test case number 35 ?
My submission was also getting Wrong answer on that test case... The problem with my code was "int overflow" when I was multiplying v[i-1].size() * (k-1) for checking for the -1 case.
If you have a doubt regarding the test case of Problem C, then check this link.