SSORT1 - Editorial

editorial
1

PROBLEM LINK:

Contest

Author: Rahul Sharma

Tester: Sumukh Bhardwaj

Editorialist: Rahul Sharma

DIFFICULTY:

Simple

PREREQUISITES:

Sorting

PROBLEM:

Given a positive integer array of size N and an integer K. You need to arrange the array such that first K elements are increasing, next K are decreasing and so on. The last section of elements will be less than or equal to K

EXPLANATION:

Let array with N integers be arr. You need to sort the window of size K alternatively in increasing decreasing fashion i.e.
arr[0:K] \uparrow, arr[K+1:2K] \downarrow , arr[2K+1:3K] \uparrow … arr[xK:N] \updownarrow . This new ordering will be the answer.

COMPLEXITIES:

Time Complexity: O(NlogK) for each test case
Space Complexity: O(1) for each test case

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

int arr[1000005];
int main()
{
	int n, k;
	bool flag = true;
	cin >> n;

	for(int j = 0; j < n; ++j)
	{
		cin >> arr[j];
	}

	cin >> k;
	int i = 0;
	while ( i + k < n )
	{
		if (flag)
		{
			sort(arr + i, arr + i + k);
			flag = false;
		}

		else
		{
			sort(arr + i, arr + i + k, greater<int>());
			flag = true;
		}

		i = i + k;
	}
	
	if (flag)
		sort(arr + i, arr + n);
	else
		sort(arr + i, arr + n, greater<int>());

	for(int j = 0; j < n; ++j)
	{
		cout << arr[j] << ' ';
	}
}
1 Like