Longest arithmetic subsequence

3.7

30 votes
Basic Programming, Recursion, Recursion and Backtracking
Problem

An arithmetic progression is a sequence of numbers such that the difference between the consecutive terms is constant. The examples of arithmetic progressions are as follows:

  • {1,3,5,7}: Difference is 2
  • {7.53,4.32,1.11,2.1,5.31}: Difference is 3.21 

Whereas, {1,2,1} is not an arithmetic progression.

A subsequence of sequence A is a sequence that is obtained from A by removing several (zero or more) elements from it. For example, {1,3,4}{1,2,3,4,5}, and {} (empty sequence) are the subsequences of {1,2,3,4,5}.

An arithmetic subsequence of sequence A is a subsequence of A, that is an arithmetic progression. You are given integers n and k. Your task is to construct any permutation of first n positive integers such that the length of the longest arithmetic subsequence of the permutation is equal to k or determine that there is no such permutation at all.

Input format

The first and only line of input contains two integers n and k denoting the length of the required permutation and the length of the longest arithmetic subsequence of the required permutation respectively.

Output format

If there no such permutations exist, then print No in a single line. If such permutations exist, then print Yes in the first line and the constructed permutation in the second line. The permutation must contain each integer from 1 to n (both inclusive) exactly once. The elements must be space-separated. If there are several possible permutations, then you can output any of them.

Constraints

1kn5000

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

{1,3,5} is the longest arithmetic subsequence of a permutation {4,1,3,2,5}. Of course, this is not the only possible answer.

Editor Image

?