Problem Link: ↵
https://cses.fi/problemset/task/3175↵
↵
Problem Statement: Generate a permutation of numbers from 1 to n such that absolute difference between any two adjacent numbers is not equal to 1. We need to generate the lexicographically smallest such permutation.↵
↵
↵
Solution:↵
↵
Idea#1 : Greedily generate the permutation by choosing the smallest available number whose difference with previous number is not 1. ↵
↵
Why this won't work?:↵
Consider the example n = 8↵
↵
we choose 1 in first iteration, so perm = [1]↵
↵
we can't choose 2 in second iteration, so we choose 3, so perm = [1, 3]↵
↵
we can't choose either 2 or 4 in third iteration so we choose 5, so perm = [1, 3, 5]↵
↵
we can't choose either 3 or 4 in fourth iteration so we choose 2, so perm = [1, 3, 5, 2]↵
↵
we can't choose either 1 or 3 in the fifth iteration so we choose 4, so perm = [1,3, 5, 2, 4]↵
↵
Now we have exhausted all the numbers from 1-5, we are only left with 6, 7, 8. However any arrangement of 3 consecutive numbers produces an adjacent difference 1. ↵
↵
↵
↵
↵
Improvising the idea:↵
↵
Consider the following idea: Generate the first n-i elements greedily using the method described above and for the last i elements brute force over all possible i! permutations and choose the lexicographic smallest permutation that satisfies the following two conditions:↵
1. the i-length permutation in the end must be valid.↵
2. the first element in the i-length permutation and the last element in the n-i length permutation must not differ by 1.↵
↵
↵
How small can i be?↵
Does i = 2. work? No, because we might generate n-2 elements greedily and end up with two elements of the form x, x+1 which cannot be arranged in the two left over slots.↵
↵
Does i = 3, No. Because we might end up with x, x+1, x+2 type elements which cannot be arranged in 3 slots.↵
↵
Does i = 4 work? Let us suppose we ended up with a1, a2, a3, a4 such that a1 < a2 < a3 < a4 then since a3-a1 >= 2 and a4-a2 >= 2, we have that [a2, a4, a1, a3] and [a3, a1, a4, a2] are valid permutations. However, since the last element in the n-i greedily generated elements can still have a difference of 1 with both a3 and a2. Thus↵
i = 4 might not be sufficient.↵
↵
Does i = 5 work? Yes, because if we have five elements a1, a2, a3, a4, a5 (with a1 < a2 < a3 < a4 < a5) we can make a valid permutation starting with a2, or staring with a3 or starting with a4 and since the last element in n-i length permutation can be adjacent with utmost 2 numbers, it follows that i = 5 always works.↵
↵
↵
↵
Algorithm Summary:↵
↵
1. For i = 1 to n-5 choose the entry greedily, we can do this by maintaining a stack = [1, 2, 3, ... n] and choosing the least number that is not adjacent to the last number choosen.↵
↵
2. After we finish the above procedure we are left with 5 elements in the stack. We generate all the 5! permutations of those elements, and pick the smallest permutation (lexically) that satisfies the following two conditions ↵
↵
a. The permutation must not have an adjacent difference 1↵
b. The first element of the permutation must not have a difference 1 with the last element of the n-5 size list.↵
↵
↵
Final Note:↵
I realized that i = 4 also works. But the proof for the same is a bit difficult (more cases) but proving i = 5 is easy.↵
↵
https://cses.fi/problemset/task/3175↵
↵
Problem Statement: Generate a permutation of numbers from 1 to n such that absolute difference between any two adjacent numbers is not equal to 1. We need to generate the lexicographically smallest such permutation.↵
↵
↵
Solution:↵
↵
Idea#1 : Greedily generate the permutation by choosing the smallest available number whose difference with previous number is not 1. ↵
↵
Why this won't work?:↵
Consider the example n = 8↵
↵
we choose 1 in first iteration, so perm = [1]↵
↵
we can't choose 2 in second iteration, so we choose 3, so perm = [1, 3]↵
↵
we can't choose either 2 or 4 in third iteration so we choose 5, so perm = [1, 3, 5]↵
↵
we can't choose either 3 or 4 in fourth iteration so we choose 2, so perm = [1, 3, 5, 2]↵
↵
we can't choose either 1 or 3 in the fifth iteration so we choose 4, so perm = [1,3, 5, 2, 4]↵
↵
Now we have exhausted all the numbers from 1-5, we are only left with 6, 7, 8. However any arrangement of 3 consecutive numbers produces an adjacent difference 1. ↵
↵
↵
↵
↵
Improvising the idea:↵
↵
Consider the following idea: Generate the first n-i elements greedily using the method described above and for the last i elements brute force over all possible i! permutations and choose the lexicographic smallest permutation that satisfies the following two conditions:↵
1. the i-length permutation in the end must be valid.↵
2. the first element in the i-length permutation and the last element in the n-i length permutation must not differ by 1.↵
↵
↵
How small can i be?↵
Does i = 2. work? No, because we might generate n-2 elements greedily and end up with two elements of the form x, x+1 which cannot be arranged in the two left over slots.↵
↵
Does i = 3, No. Because we might end up with x, x+1, x+2 type elements which cannot be arranged in 3 slots.↵
↵
Does i = 4 work? Let us suppose we ended up with a1, a2, a3, a4 such that a1 < a2 < a3 < a4 then since a3-a1 >= 2 and a4-a2 >= 2, we have that [a2, a4, a1, a3] and [a3, a1, a4, a2] are valid permutations. However, since the last element in the n-i greedily generated elements can still have a difference of 1 with both a3 and a2. Thus↵
i = 4 might not be sufficient.↵
↵
Does i = 5 work? Yes, because if we have five elements a1, a2, a3, a4, a5 (with a1 < a2 < a3 < a4 < a5) we can make a valid permutation starting with a2, or staring with a3 or starting with a4 and since the last element in n-i length permutation can be adjacent with utmost 2 numbers, it follows that i = 5 always works.↵
↵
↵
↵
Algorithm Summary:↵
↵
1. For i = 1 to n-5 choose the entry greedily, we can do this by maintaining a stack = [1, 2, 3, ... n] and choosing the least number that is not adjacent to the last number choosen.↵
↵
2. After we finish the above procedure we are left with 5 elements in the stack. We generate all the 5! permutations of those elements, and pick the smallest permutation (lexically) that satisfies the following two conditions ↵
↵
a. The permutation must not have an adjacent difference 1↵
b. The first element of the permutation must not have a difference 1 with the last element of the n-5 size list.↵
↵
↵
Final Note:↵
I realized that i = 4 also works. But the proof for the same is a bit difficult (more cases) but proving i = 5 is easy.↵
↵
