Сведем задачу к задаче на графе. Вершинами будут здания, а ребрами мосты и туннели. В этом случае количество вершин достижимых из какого-либо ребра, будет количество вершин, достижимых из одной из вершин инцидентных ей. Будем поддерживать размер компонент связности с помощью СНМ. При добавлений очередного ребра, ответом будет количество вершин в компоненте связности, в которой находится наше новое ребро.
Итого сложность O(N) либо O(Nlog(N)).
В этой задаче нужно было перевести число в десятичную систему счисления. После перевести данное число в систему счисления, которое дано во входных данных. Ничего сложного, но у большинства людей, включая и меня, решавших эту тренировку возникали проблемы, и они сдавали ее со 2-5 попыток. Проблема была с 0.
Хотелось бы отметить наличие в Java, встроенных функций, считывания числа в системах счисления от 2-36, и вывода числа в системе счисления 2-36. Коротко можно было написать примерно вот такое:
int x = nextInt();
int y = nextInt();
long z = Long.parseLong(nextToken(),x);
System.out.println(Long.toString(z,y).toUpperCase());
Итого сложность O(log(z)).
В этой задаче можно было поступить следующим образом:
Научимся за O(1) находить количество плохих клеток в произвольном прямоугольнике. Для этого заведем массив d[i][j], где d[i][j] равно количеству плохих клеток в прямоугольнике от (0,0) до (i,j). Это легко сделать за O(n^2) по вот такой рекуррентной формуле d[i][j] = d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] + (bad[i][j] ? 1 : 0); Теперь для того, чтобы посчитать количество плохих клеток, в квадрате длинной l, правый нижний угол которого имеет координаты (i,j), используем следующую формулу d[i][j] - d[i - l][j] - d[i][j - l] + d[i - l][j - l]; Легко видеть, что возможность найти квадрат фиксированной длины, в нашей мозайке есть монотонная функция. Воспользуемся бинарным поиском по длине квадрата. Проверяя для фиксированной длины можно ли найти такой квадрат. То есть для каждого положения проверить, что d[i][j] - d[i - l][j] - d[i][j - l] + d[i - l][j - l] <= L.
Итого сложность O(N^2log(N)).
Хотелось бы услышать, разбор задач C,E.
Comments (0)
