Problem B: Restoration of the Permutation

Time Limit per test: 1 Sec

Let A = {a1, a2, ..., an} be any permutation of the first n natural numbers {1, 2, ..., n}. You are given a positive integer k and another sequence B = {b1, b2, ..., bn}, where bi is the number of elements aj in A to the left of the element at = i such that aj ≥ (i + k).

For example, if n = 5, a possible A is {5, 1, 4, 2, 3}. For k = 2, B is given by {1, 2, 1, 0, 0}. But if k = 3, then B = {1, 1, 0, 0, 0}.

For two sequences X = {x1, x2, ..., xn} and Y = {y1, y2, ..., yn}, let i-th elements be the first elements such that xi ≠ yi. If xi < yi, then X is lexicographically smaller than Y, while if xi > yi, then X is lexicographically greater than Y.

Given n, k and B, you need to determine the lexicographically smallest A.

Input:

The first line contains two space separated integers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ n). On the second line are n integers specifying the values of B = {b1, b2, ..., bn}.

Output:

Print on a single line n integers of A = {a1, a2, ..., an} such that A is lexicographically minimal. It is guaranteed that the solution exists.

Sample Tests:

5 2
1 2 1 0 0

4 1 5 2 3 

4 2
1 0 0 0

2 3 1 4

Solution:

For k=1, the given sequence is called Table of Inversions. We notice that if i>j, relative position of i effects the b_j while placing of j does not effect b_i. For this value of k, and sequnce {b_1, b_2, ..., b_n}, we first place n in the permutation. Then we chose (n-1) and check whether n-1 is 0 or 1. If its 0, It lies to the right of n, otherwise to the left of n. Similarly, we proceed for all values from n to 1. For k=1, there is only one possible permutation.

But, when value of k is increased, b_(n-k+1), b_(n-k+2), ..., b_n are all 0. Since we need to find the lexicographically smallest permutation, we insert values from (n-k+1) to n in ascending order first. Then for each value i from n-k to 1, we choose first location in the permutation such that b_i is satisfied.

Table of inversions finds application in Sorting where it is easy to represent the permutation using this.

Reference: 5.1.1 Inversions, Art of Computer Programming, Vol 3, D E Knuth

Code:

#include <stdio.h>
int main()
{
  int n,k,a[1002],b[1002],i,j,temp;
  
  scanf("%d%d",&n,&k);
  
  for(i=1;i<=n;i++)
  {
    scanf("%d",&b[i]);
  }
  
  for(i=k;i>=1;i--)
    a[i] = n-i+1;
  
  for(i=n-k;i>=1;i--)
  {
    temp = b[i];
    
    for(j=n-i;j>=1 && temp>0;j--)
    {
      if(a[j]>=i+k)
        temp--;
      a[j+1] = a[j];
    }
    a[j+1] = i;
  }
  
  for(i=n;i>=1;i--)
    printf("%d ",a[i]);
  printf("\n");
}