PERMEXIS - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author and Editorialist: Lalit Kundu
Tester: Kamil Debowski

DIFFICULTY:

simple

PREREQUISITES:

logic, basic programming, sorting

PROBLEM:

You are given a list of integers A_1, A_2, ..., A_N. You have to rearrange them to get B_1, B_2, ..., B_N. Also, the conditions that |B_i - B_{i + 1}| \le 1 should be satisfied \forall i < N.
You have to output if it’s possible to do so.

QUICK EXPLANATION:

======================
If in sorted array A, any two adjacent elements differ by more than 1, answer is NO, otherwise YES.

EXPLANATION:

================

Claim : If in sorted array A, any two adjacent elements differ by more than 1, answer is NO, otherwise YES.

Proof: Let’s assume there are two elements l and r in array A, where r - l > 1 and no other element lies between l and r. We have to show that there doesn’t exist a permutation of A where adjacent elements don’t differ by more than 1, no matter what the other elements of array A are.

We assume there exists such a permutation. Then, there are two cases:

  • l occurs before r in this permutation. Since each adjacent element differs by atmost 1, we can observe that we have to go from element l to r and in each step we can either remain at same value or increase by one or decrease by one, with the condition that new value should be present in array A. The only way to reach r is through r-1(since l occurs before r in array), which can’t be achieved since there is no such value in the array A.
  • r occurs before l in this permutation. Since each adjacent element differs by atmost 1, we can observe that we have to go from element r to l and in each step we can either remain at same value or increase by one or decrease by one, with the condition that new value should be present in array A. The only way to reach l is through l + 1(since r occurs before l in array), which can’t be achieved since there is no such value in the array A.

Pseudo code:

A = []
scan(T)
for test = 0 to T - 1:
	ans = "YES"

	scan(N)
	for i = 0 to N - 1:
		scan(A[i])
	sort(A)
	for i  = 0 to N - 2:
		if A[i + 1] - A[i] > 1:
			ans = "NO"

	print ans

COMPLEXITY:

================
O(N \text{log} N), since we sort array A.

AUTHOR’S, TESTER’S SOLUTIONS:

setter
tester

2

@codemath it passed because the test cases were weak… but as per the question… it needs to be sorted and then checked for no difference to be more than 1.

3

Weak test cases.

This code gives wrong answer for test

1

3

5 7 6

Output - NO

Answer - YES

4

https://www.codechef.com/viewsolution/11930803
Please View this solution . I m Getting Wrong Answer…
Please do reply

5

Hello @tejaram15,
Regarding your solution https://www.codechef.com/viewsolution/11930803

  1. You should use int return type of main.

  2. Should return 0 by main.

  3. In this Qn a[i] ranges till 10^9 thus use long instead of int.

  4. In your Solution there is logical mistake, you should break the loop only when |a[i]-a[i-1]| > 1, but in you code due to missing bracket it will break at first run of loop.

Here is your accepted code https://www.codechef.com/viewsolution/11941195

Keep Coding,

Habe Fun. :slight_smile: