Shuffle Array

4.5

4 votes
C++, Greedy Algorithms, Basics of Greedy Algorithms, Algorithms
Problem

Note: This is an approximate problem. There is no exact solution. You must find the most optimal solution. Please, take a look at the sample explanation to ensure that you understand the problem correctly.

Problem statement

Given an array A of N integers. We need to decompose A into K consecutive non empty subarrays such that every integer is present in only one subarray.

Say subarrays are S[1], S[2], S[3], .... , S[K]. Choose an array B , which is a permutation of 1 to K i.e. it is of size K and include every element from 1 to K.

Now, form a new array V = S[B[1]] + S[B[2]] + ......  + S[B[K]]

Aim is to maximize X for array V.

  • \(X = LIS \times LDS - LIS \oplus LDS\), where \(\oplus\) denotes bitwise xor operator.

Note:

  • 1 based indexing is followed.
  • LIS stands for longest increasing subsequence of \(V\) i.e. every element in the subsequence is greater than the previous one.
  • LDS stands for longest decreasing subsequence of \(V\) i.e. every element in the subsequence is less than the previous one.

Input format

  • First line contains two space-separated integers : N and K 
  • Second line contains N space-separated integers denoting the array A

Output format

  • In the first K lines, print one integer denoting end index of i-th subarray (indexes are 1 based).
  • In next line print K space separated integers, denoting array B (permutation of 1 to K)
  • End index of subarrays should be in increasing order.

Verdict and scoring

  • Your score is equal to the sum of the values of all test files. The value of each test file is equal to the value of X that you found.

    If decomposition of array A is invalid, or array B is invalid you will receive a wrong answer verdict.

Constraints

  • \(N = 10^3\)
  • \(50 \le K \le 10^2\)
  • \(1 \le A[i] \le 10^5\)
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  • S1 = [3, 4]
  • S2 = [1, 2]
  • V = S[B[1]] + S[B[2]] = S[2] + S[1] = [1, 2] + [3, 4] = [1, 2, 3, 4]
  • LIS = 4, LDS = 1
  • X = 4 - 5 = -1


Sample Test is for understanding purpose. Constraints in test files are as mentioned above.

Editor Image

?