K-ая порядковая статистика. В чем проблема?

Question

[Никита]

Добрый вечер. Написал программу для поиска К-ой порядковой статистики, в качестве основы взял алгоритм быстрой сортировки. Программа дает неправильный ответ на 8 тесте. В чем может быть проблема?

Задача

Дан массив из n элементов. Какое число k-ое в порядке возрастания в этом массиве?

Формат входного файла
В первой строке входного файла содержатся два числа n размер массива и
k.(1 <= k <= n <= 3 * 10^7). Во второй строке находятся числа A, B, C, a1, a2 по модулю не
превосходящие 10^9. Вы должны получить элементы массива начиная с третьего по формуле:
a[i] = A * a[i-2] + B * a[i-1] + C. Все вычисления должны производится в 32 битном знаковом типе,
переполнения должны игнорироваться.

Формат выходного файла
Выведите k-ое в порядке возрастания число в массиве a.

Мой код:

#include <iostream>
#include <fstream>

int partition(int l, int h, int* array)
{
	int i = l, j = h;
	int pivot = array[l];
	while (i < j)
	{
		do {
			i++;
		} while (array[i] <= pivot);
		do {
			j--;
		} while (array[j] > pivot);                       
		if (i < j)
			std::swap(array[i], array[j]);
	}
	std::swap(array[j], array[l]);
	return j;
}

int quick_sort(int l, int h, int* array, int k)
{
	int pivot_index;
	if (l < h)
	{

		pivot_index = partition(l, h, array);
		if (k < pivot_index)
			quick_sort(l, pivot_index, array, k);
		else
			quick_sort(pivot_index + 1, h, array, k);
	}
	return array[k];
}


int main()
{
	std::ifstream fin;
	fin.open("kth.in");
	std::ofstream fout;
	fout.open("kth.out");

	int size, k;
	fin >> size >> k;
	int A, B, C;
	fin >> A >> B >> C;
	int* array = new int[size];
	fin >> array[0] >> array[1];
	for (int i = 2; i < size; i++)
	{
		array[i] = A * array[i - 2] + B * array[i - 1] + C;
	}

	fout << quick_sort(0, size, array, k-1);

	fin.close();
	fout.close();
	return 0;
}

Comments

[res2001]

Посмотрите реализацию алгоритма quickselect

Answer 1

[Wataru]

У вас какая-то странная схема в partition.

Представьте, что у вас массив из 2 элементов и первый - больше второго (a[0] = pivot > a[1]).

До цикла l = 0, h = 2, i = 0. Потом в первом while вы делаете i++. Потом сравниваете a[i] с pivot в первом while. a[1] < pivot по предположению, поэтому вы делаете i = 2. Все - вы уже вышли за границу массива.

Перепишите со стандартной схемой разбиения Хоара или Ломуто.

Или придется всякие условия i < j везде дописывать, но я не уверен.

Comments

[Никита]

Переделал функцию partition, но теперь не проходит по времени(( Сначала думал, проблема в опорном элементе: поменял на случайный, но не помогло. Не понимаю, как можно еще уменьшить время работы

#include <iostream>
#include <fstream>

int Partition(int* A, int start, int end)
{
	int last = start;
	int p_index = rand() % (end - start + 1) + start;
	std::swap(A[last], A[p_index]);
	for (int i = start + 1; i <= end; i++)
	{
		if (A[i] < A[start])
			std::swap(A[++last], A[i]);
	}
	std::swap(A[start], A[last]);
	return last;
}
int QuickSort(int* A, int start, int end, int k)
{
	if (start < end)
	{
 		int partitionIndex = Partition(A, start, end);
		if (k < partitionIndex)
			QuickSort(A, start, partitionIndex - 1, k);
		else if (k > partitionIndex)
			QuickSort(A, partitionIndex + 1, end, k);
		else
			return A[k];
	}
	return A[k];
}

int main()
{
	std::ifstream fin;
	fin.open("kth.in");
	std::ofstream fout;
	fout.open("kth.out");

	int size, k, A, B, C;
	fin >> size >> k >> A >> B >> C;
	int* array = new int[size];
	fin >> array[0] >> array[1];
	for (int i = 2; i < size; i++)
	{
		array[i] = A * array[i - 2] + B * array[i - 1] + C;
	}

	fout << QuickSort(array, 0, size - 1, k - 1);

	delete[] array;
	fin.close();
	fout.close();
	return 0;
}

[Wataru]

Никита,
Во-первых, можно соптимизировать код. Вам не нужны на самом деле рекурсивные вызовы. Ведь каждый раз вызов идет только в одну сторону. Надо переписать quicksort с одним циклом while. Вы внутри разбиваете, потом смотрите, в какую сторону нажно идти и меняете переменные. Потом следующая итерация цикла сделает то, что вы хотели сделать вашим рекурсивным вызовом.
Также можно вставить код partition прямо в тело quicksort.
Попробуйте воткнуть в начало srand(ваше-любимое-число). Может жюри подобрали плохой тест. Надо рандомизировать что-то самим. Вмеcто std::swap ручная реализация может быть быстрее.

Но главное, введите тест A=0, B=0, array[0]=array[1]. Все числа в массиве будут одинаковые. Тут ваша реализация будет откусывать по 1 элементу и работать за квадрат.

Можно сделать все числа уникальными, если расширить их до 64-бит, где старшие биты - входные данные, а нижние 32 бита - тупо индекс числа. Найдите тут k-ое число и выведите старшие биты.
Ну, или меняйте ++last с i с некоторой вероятностью, если a[i] == pivot.

Или можно переписать с использованием разбиения Хоара (у вас Ломуто сейчас). Оно на таком вырожденном тесте всегда будет разбивать по середине.