LimitedDifferences
SRM 806 · 2021-05-24 · by misof
Problem Statement
Given a sequence S of numbers, its difference sequence D(S) is obtained by writing down the absolute difference between each pair of consecutive elements of S. Note that the length of D(S) is always one less than the length of S.
For example, if S = {10, 50, 50, 40, 30}, we have |10-50| = 40, |50-50| = 0, |50-40| = 10 and |40-30| = 10, thus D(S) = {40, 0, 10, 10}.
You are given N and V.
Arrange the integers from 1 to N into a sequence S such that D(S) will contain exactly V distinct values.
Return the answer as a
Notes
- You must use each of the values from 1 to N exactly once in your sequence. In other words, you must return a permutation of those numbers.
Constraints
- N will be between 2 and 500, inclusive.
- V will be between 1 and N-1, inclusive.
7
1
Returns: {7, 6, 5, 4, 3, 2, 1 }
The returned sequence S = {7, 6, 5, 4, 3, 2, 1} has the difference sequence D(S) = {1, 1, 1, 1, 1, 1}. As required, there is only one distinct value in D(S): the value 1. The sequence S = {1, 2, 3, 4, 5, 6, 7} is also a correct answer. There are no other correct answers for this test case, only these two.
8
2
Returns: {1, 5, 6, 7, 8, 4, 3, 2 }
The difference sequence for the example return value is {4, 1, 1, 1, 4, 1, 1}. Thus, there are exactly two distinct differences: 1 and 4.
5
2
Returns: {2, 4, 1, 3, 5 }
Here each consecutive pair of elements of the returned sequence has a difference of either 2 or 3.
15
5
Returns: {11, 14, 12, 10, 8, 3, 7, 4, 2, 6, 1, 9, 5, 13, 15 }
The differences between consecutive elements of the sequence returned as example output are 2, 3, 4, 5, and 8. There are many other valid solutions.
3
2
Returns: {1, 3, 2 }
Submissions are judged against all 86 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LimitedDifferences with a public method vector<int> arrange(int N, int V) · 86 test cases · 2 s / 256 MB per case