user_of_toster
@user_of_toster

Где ошибка в рассуждениях?

Задача https://codeforces.com/contest/602/problem/B

Я перефразировал задачу так:
Найти длину наибольшего отрезка, в котором максимум два различных числа.

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

Лучше прочесть код:

using namespace std;

bool isValidIndex(int index) {
	return index >= 0;
}

int main(){
	// data input
	int n; cin >> n;
	vector<int> dataPoints(n);
	for (int i{}; i < n; i++) cin >> dataPoints[i];
	
	// pair consists if <number, how many times met>
	vector<pair<int, int>> lastTwoNumbers{};
	
	// now, iterate over all data points
	// if data point equal to one of <last two numbers>
	// then increate <how many times met> of this number
	// otherwise push new number in <lastTwoNumbers>
	// in the end, refresh best answer;
	int answer = 0;
	
	for (int i{}; i < n; i++) {
		int number = dataPoints[i];
		bool foundInLastTwoNumbers = false;
		for (int j{}; j < 2; j++) {
			int index = lastTwoNumbers.size() - 1 - j;
			if (isValidIndex(index) and number == lastTwoNumbers[index].first) {
				lastTwoNumbers[index].second++;
				foundInLastTwoNumbers = true;
				break;
			}
		}
		
		if (!foundInLastTwoNumbers) {
			lastTwoNumbers.push_back(make_pair(number, 1));
		}
		
		// calculating answer
		int currentAnswer = 0;
		for (int j{}; j < 2; j++) {
			int index = lastTwoNumbers.size() - 1 - j;
			if (isValidIndex(index)) currentAnswer += lastTwoNumbers[index].second;
		}
		
		answer = max(answer, currentAnswer);
	}
	
	cout << answer;
}


К сожалению, часть тестов не проходят - мой ответ выходит меньше, чем правильный ответ. В чем ошибка в рассуждениях\имлементации?
  • Вопрос задан
  • 156 просмотров
Решения вопроса 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Вы считаете только отрезки на самом конце, а ведь они могут быть и в середине.

Вам надо вместо суммы чисел на конце как-то во время основного цикла выбирать максимум.

Но, кстати, ваше решение не работает и так, например, на таком тесте:

0 0 0 0 1 1 1 1 0 0 2 2

Когда вы обработаете нули и единицы, вы будете видеть 6 нулей и 4 единицы. Потом вы добавляете новое число 2 и подсчитаете что его 2. Но нельзя брать все двойки и нули вместе! Там же еще единицы между ними. Более того, у вас в массиве последних чисел будут {{0, 6}, {1, 4}, {2, 2}} - то есть вы постараетесь взять двойки и единицы вместе.

Нужны подсказки по правильному решению?
Ответ написан
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
В чем ошибка в рассуждениях

Зря очередным попаданием затираете предыдущие. В результате прохода по всей последовательноси могут образоваться несколько «кандидатов», из которых победит не факт, что последний:
1 0 1 0 1 2 1 0 1

Как вариант
Как вариант, я бы входные данные переделал в дельты (изменения) каждого шага:
1  0  1  1  0  1  2  2  1  0  1
 -1 +1  0 -1 +1 +1  0 -1 -1 +1

Возможны только 3 значения: -1, 0, +1. "0" влияет только на длину. Искать отрезки, где не находятся подряд (игнорируя нули) два перехода одного знака. Кандидаты могут пересекаться, но не более двух:
+1 0 -1 0 0 0 -1 0 +1
|-----------|
        |-----------|
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
MANAB
@MANAB
Разрабатываю на C#: Web, Desktop, Gamedev
Найти длину наибольшего отрезка, в котором максимум два различных числа.
в вашей трактовке опускается случай [0, 1, 0, 1, 0, 0, 1] хотя по исходной формулировке весь отрезок должен подойти.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы