There is a task, the essence of which boils down to checking the possibility of sorting a certain set of numbers. If sorting is possible then output YES, otherwise NO.

k-sort

This year, Grisha entered the University of IT. At the University of IT a lot of new items, and not very interesting. Grisha especially likes the subject "Algorithms and Data Structures". In the last lecture, sorting algorithms were told. Grisha is a very ambitious young man and wants to invent his own algorithm, which will later be named after his beloved grandfather. Inspired by the reading of Knuth’s multi-volume, Grisha decided to upgrade some existing algorithm for sorting natural numbers, imposing the following restriction. Any two elements can be interchanged only if they are comparable in magnitude to some natural number k, that is, they give the same residues when divided by k. But all innovative methods require verification, so Grisha turned to you for help!

Check if the new version of the algorithm can sort the given array of natural numbers.

Input data

The first line of the input file contains two numbers n (1 ≤ n ≤ 1000) and k (1 ≤ k ≤ 10 9 ) - the number of elements in the array and the number modulo which the elements of the array are compared.

The second line of the input file contains n integers ai - array elements (1 ≤ ai ≤ 10 9 ).

Output

In the output file output YES, if the algorithm can sort the specified array and NO - otherwise.

Actually, this is the text of the problem itself. Test data are as follows:

5 2 1 2 3 4 5 - результат YES 3 2 2 3 1 - результат NO.

My algorithm for solving the problem is as follows

 #include <iostream> #include <ctype.h> using namespace std; int main() { int n = 0; int k = 0; int *array; cin >> n; if (n == 1) { cout << "YES" << endl; return 0; } cin >> k; if (k == 1) { cout << "YES" << endl; return 0; } array = new int[n]; for (int i = 0; i < n; ++i) { cin >> array[i]; } int afterTemp = 0; int beforeTemp = 0; afterTemp = array[0] % k; beforeTemp = array[1] % k; bool switchMod = true; for (int i = 2; i < n; ++i) { if (switchMod) { if (array[i] % k == afterTemp) { switchMod = false; } else { cout << "NO" << endl; return 0; } } else { if (array[i] % k == beforeTemp) { switchMod = true; } else { cout << "NO" << endl; return 0; } } } cout << "YES" << endl; return 0; }

In the testing system I pass only half of the correct answers (53%). If anyone has any ideas that I could miss, please tell me.

2 answers 2

 #include <iostream> #include <algorithm> using namespace std; int A[1111],B[1111]; int main(){ int N,K; cin >> N >> K; for (int i=0;i<N;i++){ cin >> A[i]; B[i] = A[i]; } sort(A,A+N); for (int i=0;i<N;i++) if (A[i] % K != B[i] % K){ cout << "NO"; return 0; } cout << "YES"; }

Like so. Note that we can change arbitrarily the elements with the same remainder of dividing by K. Therefore, the remainder of dividing by K the number in each position does not change. Sort and verify that this is so. If not, the answer is no. Otherwise, yes.

    Just by checking the sequence of residues from division it is impossible to determine whether it is possible to sort the sequence of numbers or not, because one and also the sequence of residues corresponds to different numerical sequences, for example:

    The sequence of numbers: 6 3 4 9 with k = 2 gives the sequence of residuals 0101 and cannot be sorted because 9 and 6 cannot be interchanged in places (different residues).

    The sequence of numbers: 6 5 4 3 with k = 2 gives the same sequence of residues 0101 while the original sequence is already sorted.

    Therefore, the alternation of residues will not determine anything. The condition does not specify the complexity of the solution, and with such a limitation of the number of elements 0 <n <1000, you can try to simply modify one of the simple sorts (bubble, sample, etc. O (N2))

    So I modified the sorting a bit with the sample, but, oddly enough, the same 53% gave the e-olymp run, and then I tried to change the NO to YES in one place and got 53% again:

     #include <iostream> #include <ctype.h> using namespace std; int main() { int n = 0; int k = 0; int *array; cin >> n; if (n == 1) { cout << "YES" << endl; return 0; } cin >> k; if (k == 1) { cout << "YES" << endl; return 0; } array = new int[n]; for (int i = 0; i < n; ++i) { cin >> array[i]; } int temp; int pointerMax = 0; int pointerMin = 0; for (int i = 0; i < n - i; i++) { pointerMax = i; pointerMin = i; for (int j = i + 1; j < n - i; j++) { if (array[j] < array[pointerMin]) { pointerMin = j; } if(array[j] > array[pointerMax]) { pointerMax = j; } } if (array[i] % k != array[pointerMax] % k) { cout<<"NO"<<endl; return 0; } temp = array[pointerMax]; array[pointerMax] = array[i]; array[i] = temp; pointerMin = (pointerMin == i) ? pointerMax: pointerMin; if (array[n - (i + 1)] % k != array[pointerMin] % k) { cout<<"NO"<<endl; return 0; } temp = array[pointerMin]; array[pointerMin] = array[n - (i + 1)]; array[n - (i + 1)] = temp; } cout << "YES" << endl; return 0; }
    • Something difficult ... - Qwertiy ♦
    • Yes it is at first glance :) Normal sorting by selection. On each pass, the maximum and minimum element is selected. Since the sequence of residuals should not change, the maximum element must have the same residue as the element in the leftmost position (we sort in descending order), and the minimum is the same residue as the element in the extreme right. We check and if it is not so it is impossible to sort, otherwise we narrow the search range and look for a new pair. I'm not sure that you can use library methods for solving, and of course the previous answer is much more concise, but the meaning is the same. - elf2707
    • You can always use library methods in Olympiad tasks. Except multithreading. - Qwertiy ♦