Привет Есть задача https://informatics.msk.ru/mod/statements/view.php?chapterid=112560#1 Пытаюсь решить её через метод динамического плавающего окна,

но похоже что в моём решении есть логическая ошибка, не подскажите какая именно?
fun findMinimumTreeSegment(k: Int, trees: List<Int>): Pair<Int, Int> {
var left = 0
var right = 1
val state = mutableMapOf<Int, Int>() // type, frequency
var min = Int.MAX_VALUE
while (right < trees.size) {
state.computeIfPresent(trees[right]) { _, v -> v + 1 }
state.putIfAbsent(trees[right], 1)
while (left != right && state.size == k) {
min = minOf(min, right - left + 1)
state.computeIfPresent(trees[left]) { _, v -> v - 1 }
if (state[trees[left]] == 0)
state.remove(trees[left])
left += 1
if (min == k + 1)
return Pair(minOf(left + 1, trees.size), minOf(right + 1, trees.size))
}

right++
}

return Pair(minOf(left + 1, trees.size), minOf(right + 1, trees.size))
}

2 ответов

16 просмотров

Первое дерево не положил?

Αλeksandr- Автор вопроса
Evgenii Zheltonozhskii🇮🇱
Первое дерево не положил?

Судя по всему да, если N, K = 1, то ответ неправильный

Похожие вопросы

Обсуждают сегодня

Всем привет Есть достаточно базовая задача: Дан неориентированный граф. Требуется определить, есть ли в нем цикл, и, если есть, вывести его. Входные данные подаются в виде ма...
Αλeksandr
10
Привет всем. Подскажите, как можно данную задачу более менее эффективно решить? В столовой одного известного Завода вот-вот начнётся обед. На обеде есть три гарнира — макарош...
Vitaliy
6
Всем привет Пытаюсь решить следующую задачу: https://informatics.msk.ru/mod/statements/view.php?id=6992&chapterid=101#1 Строка S была записана много раз подряд, после чего из ...
Αλeksandr
10
всем привет. У меня есть неупорядоченный массив точек(в моем случае в трёхмерном пространстве). Есть критерий связанности точек: если евклидово расстояние между ними меньше за...
Павлик Ливаткин
31
Доброе утро. Такой вопрос: есть ли какие-то практически полезные меры вычислительной мощности (в смысле computational complexity) для реальных машин, с ограниченными ресурсам...
Yaroslav Schekin
15
Здравствуйте. Есть задача нужно найти наименшое число P где фактриал P делиться на 10^N. Ограничения 10^9. Знаю что нужно найти такой P в конце как минимум N нулей. Решение с ...
. Azmiddin
20
Друзья, практический вопрос надо счиать скользящую медиану в последовательности по заданному окну (длины N) тупой вариант - взять значения в окне, отсортировать, взять элеме...
Стас Выщепан
17
#pragma once #include <iostream> #include <vector> template <typename T, typename Comp = std::less<T>> class Heap { public: Heap() = default; Heap(const std::vector<T>&...
Степан
1
Должна-ли работать такая стратегия: Мы каждую секунду бросаем монетку - орел или решка. Если орел - покупаем акцию на все деньги, если у нас есть деньги, или продаем все акци...
George Polevoy
13
Как можно сжимать временные ряды в памяти? У меня есть исторические стоимости ценных бумаг. Данные для каждой минуты в истории OHLC (Open, High, Low, Close). Соответственно, O...
George Polevoy
10
Карта сайта