# HackerRank Super Kth LIS problem solution

In this HackerRank Super Kth LIS problem solution, we have given an array of N integers and we need to find all possible increasing subsequences of maximum length L. then we need to print the lexicographically Kth longest increasing subsequences as a single line of space-separated integers and if there are less than K subsequences of length L then print -1.

## Problem solution in Java.

```import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

public class E {
InputStream is;
PrintWriter out;
String INPUT = "";

static long I = 2000000000_000000000L;

void solve()
{
int n = ni();
long K = nl();
int[] a = na(n);
int[] b = Arrays.copyOf(a, n);
for(int i = 0;i < n;i++)b[i] = n-a[n-1-i];
b = shrink(b);

SegmentTreeRMQSumWhenMax st = new SegmentTreeRMQSumWhenMax(n+5);
int[] maxs = new int[n+1];
long[] counts = new long[n+1];
double[] cx = new double[n+1];
for(int i = 0;i < n;i++){
int max = st.maxx(0, b[i]+1);
maxs[i] = max;
if(st.gwd >= I)st.gw = I;
counts[i] = st.gw;
cx[i] = st.gwd;
}
int max = st.maxx(0, n+1);
maxs[n] = max;
counts[n] = st.gw;
cx[n] = st.gwd;
if(cx[n] <= 2E18 && K > counts[n]){
out.println(-1);
return;
}
int lis = maxs[n];
int[][] g = makeBuckets(maxs, lis);
for(int i = 0;i < n+1;i++){
if(cx[i] >= 2E18){
counts[i] = I;
}
}

long[] ft = new long[n+3];
double[] ftd = new double[n+3];
int[] ret = new int[lis];
int[] prevs = new int[n];
long[] pvs = new long[n];
int pp = 0;
prevs[pp] = 0; pvs[pp] = 1; pp++;
for(int h = lis-1;h >= 0;h--){
long[][] temps = new long[g[h].length][];
int p = 0;
for(int i : g[h]){
int ind = n-1-i;
if(h < lis-1 && a[ind] <= ret[lis-(h+1)-1])continue;
long sum = sumFenwick(ft, ind+1);
double sumd = sumFenwick(ftd, ind+1);
if(sumd >= I)sum = I;
long cc = sum*counts[i];
double cd = (double)counts[i]*sum;
if(cd > 2E18){
cc = I;
}
temps[p++] = new long[]{a[ind], cc, sum, ind+1};
}
for(int j = 0;j < pp;j++){
}

Arrays.sort(temps, 0, p, new Comparator<long[]>() {
public int compare(long[] a, long[] b) {
return Long.compare(a[0], b[0]);
}
});

for(int i = 0;i < p;){
int j = i;
while(j < p && temps[j][0] == temps[i][0])j++;
long lnum = 0;
for(int k = i;k < j;k++){
lnum += temps[k][1];
if(lnum >= I)lnum = I;
}
if(K - lnum <= 0){
ret[lis-h-1] = (int)temps[i][0];
break;
}else{
K -= lnum;
}
i = j;
}
pp = 0;
for(int i = 0;i < p;i++){
long[] t = temps[i];
if(t[0] == ret[lis-h-1]){

prevs[pp] = (int)t[3]; pvs[pp] = t[2]; pp++;
}
}
}

for(int i = 0;i < lis;i++){
out.print(ret[i] + " ");
}
out.println();
}

public static long sumFenwick(long[] ft, int i)
{
long sum = 0;
for(i++;i > 0;i -= i&-i){
sum += ft[i];
}
return sum;
}

public static void addFenwick(long[] ft, int i, long v)
{
if(v == 0)return;
int n = ft.length;
for(i++;i < n;i += i&-i)ft[i] += v;
}

public static double sumFenwick(double[] ft, int i)
{
double sum = 0;
for(i++;i > 0;i -= i&-i){
sum += ft[i];
}
return sum;
}

public static void addFenwick(double[] ft, int i, double v)
{
if(v == 0)return;
int n = ft.length;
for(i++;i < n;i += i&-i)ft[i] += v;
}

public static int[][] makeBuckets(int[] a, int sup)
{
int n = a.length;
int[][] bucket = new int[sup+1][];
int[] bp = new int[sup+1];
for(int i = 0;i < n;i++)bp[a[i]]++;
for(int i = 0;i <= sup;i++)bucket[i] = new int[bp[i]];
for(int i = n-1;i >= 0;i--)bucket[a[i]][--bp[a[i]]] = i;
return bucket;
}

public static int[] shrink(int[] a) {
int n = a.length;
long[] b = new long[n];
for (int i = 0; i < n; i++)
b[i] = (long) a[i] << 32 | i;
Arrays.sort(b);
int[] ret = new int[n];
int p = 0;
for (int i = 0; i < n; i++) {
if (i > 0 && (b[i] ^ b[i - 1]) >> 32 != 0)
p++;
ret[(int) b[i]] = p;
}
return ret;
}

private static class SegmentTreeRMQSumWhenMax {
public int M, H, N;
public int[] st;
public long[] w;
public double[] wd;

public SegmentTreeRMQSumWhenMax(int n)
{
N = n;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
st = new int[M];
w = new long[M];
wd = new double[M];
Arrays.fill(st, 0, M, Integer.MIN_VALUE);
}

public void updateOrAdd(int pos, int x, long y)
{
if(x < st[H+pos])throw new RuntimeException("x < st[H+pos]");
if(x == st[H+pos]){
w[H+pos] += y;
wd[H+pos] += y;
}else{
st[H+pos] = x;
w[H+pos] = y;
wd[H+pos] = y;
}
for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);
}

private void propagate(int i)
{
if(st[2*i] < st[2*i+1]){
st[i] = st[2*i+1];
w[i] = w[2*i+1];
wd[i] = wd[2*i+1];
}else if(st[2*i] > st[2*i+1]){
st[i] = st[2*i];
w[i] = w[2*i];
wd[i] = wd[2*i];
}else{
st[i] = st[2*i];
w[i] = w[2*i] + w[2*i+1];
wd[i] = wd[2*i] + wd[2*i+1];
}
}

public long gw;
public double gwd;

public int maxx(int l, int r){
gw = 0;
gwd = 0.;
if(l >= r)return 0;
int max = Integer.MIN_VALUE;
while(l != 0){
int f = l&-l;
if(l+f > r)break;
int v = st[(H+l)/f];
if(v > max){
max = v;
gw = w[(H+l)/f];
gwd = wd[(H+l)/f];
}else if(v == max){
gw += w[(H+l)/f];
gwd += wd[(H+l)/f];
}
l += f;
}

while(l < r){
int f = r&-r;
int v = st[(H+r)/f-1];
if(v > max){
max = v;
gw = w[(H+r)/f-1];
gwd = wd[(H+r)/f-1];
}else if(v == max){
gw += w[(H+r)/f-1];
gwd += wd[(H+r)/f-1];
}
r -= f;
}
return max;
}
}

void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);

long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}

public static void main(String[] args) throws Exception { new E().run(); }

private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;

{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}

private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }

private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){
sb.appendCodePoint(b);
}
return sb.toString();
}

private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}

private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}

private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}```

## Problem solution in C++.

```#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 2234567890123456789ULL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;

#ifdef DONLINE_JUDGE
#define lld I64d
#endif

unsigned long long pw(unsigned long long a, unsigned long long e, unsigned long long mod) {
if(e <= 0) return 1;
unsigned long long x =pw(a,e/2,mod);
x =(x*x)%mod;
if(e%2 != 0) x =(x*a)%mod;
return x;}

struct fins {
vector<unsigned long long> T;
fins() {}
fins(int N) {T.resize(N,0);}

int lastone(int x) {return x&(x^(x-1));}

void put(int pos, unsigned long long val) {
for(int i =pos+1; i < (int)T.size(); i +=lastone(i)) T[i] =min(OVER9000,T[i]+val);
}

unsigned long long get(int pos) {
unsigned long long ret =0;
for(int i =pos+1; i > 0; i -=lastone(i)) ret =min(OVER9000,ret+T[i]);
return ret;}
};

struct finm {
vector<unsigned long long> T;
finm(int N) {T.resize(N,0);}

int lastone(int x) {return x&(x^(x-1));}

void put(int pos, unsigned long long val) {
for(int i =pos+1; i < (int)T.size(); i +=lastone(i)) T[i] =max(T[i],val);
}

void clr(int pos) {
for(int i =pos+1; i < (int)T.size(); i +=lastone(i)) T[i] =0;}

unsigned long long get(int pos) {
unsigned long long ret =0;
for(int i =pos+1; i > 0; i -=lastone(i)) ret =max(ret,T[i]);
return ret;}
};

int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(10);
int N;
unsigned long long K;
cin >> N >> K;
vector<int> A(N);
map<int, vector<int> > pos;
for(int i =0; i < N; i++) {
cin >> A[i];
pos[A[i]].push_back(i);}

vector<int> len(N,0);
vector<unsigned long long> poc(N,0);
finm lisF(N+tisic);
int L =0;
vector<int> V(N+tisic,0);
for(int i =N-1; i >= 0; i--) {
len[i] =lisF.get(N-A[i])+1;
L =max(L,len[i]);
V[len[i]]++;
lisF.put(N-A[i]+1,len[i]);}
vector< map<int,unsigned long long> > lisMs(L+1);
lisMs[0][0] =1;
vector<fins> lisFs(L+1);
for(int i =0; i <= L; i++) if(V[i] > 50) {
lisFs[i] =fins(N+tisic);
if(i < L) lisFs[i+1] =fins(N+tisic);
if(i > 0) lisFs[i-1] =fins(N+tisic);}
lisFs[0] =fins(N+tisic);
lisFs[0].put(0,1);
for(int i =N-1; i >= 0; i--) {
if(V[len[i]-1] > 50) poc[i] =lisFs[len[i]-1].get(N-A[i]);
else {
auto it =lisMs[len[i]-1].upper_bound(N-A[i]);
for(auto jt =lisMs[len[i]-1].begin(); jt != it; jt++) poc[i] =min(OVER9000,poc[i]+jt->ss);}
if(V[len[i]] > 50)
lisFs[len[i]].put(N-A[i]+1,poc[i]);
else
lisMs[len[i]][N-A[i]+1] +=poc[i];
}

vector<unsigned long long> prev_len(N+1,0), prev_poc(N+1,0);
prev_poc[0] =1;
vector<int> ans(L);
int Lcur =0;
finm F(N+tisic);
fins Fp(N+tisic);
Fp.put(0,1);
vector<int> sofar(1,0);
ALL_THE(pos,it) {
vector<int> v =it->ss;
unsigned long long k2 =0;
ALL_THE(v,jt) {
prev_len[*jt+1] =F.get(*jt)+1;
if(len[*jt]+prev_len[*jt+1]-1 != L) continue;
prev_poc[*jt+1] =Fp.get(*jt);
if(poc[*jt] == 0 || OVER9000/poc[*jt] > prev_poc[*jt+1])
k2 =min(OVER9000,k2+prev_poc[*jt+1]*poc[*jt]);
else k2 =OVER9000;}
if(k2 >= K) {
ans[Lcur] =it->ff;
ALL_THE(sofar,jt) {
Fp.put(*jt,-prev_poc[*jt]);
F.clr(*jt);
prev_len[*jt] =prev_poc[*jt] =0;}
Lcur++;}
else K -=k2;
ALL_THE(v,jt) if(prev_len[*jt+1] == Lcur) {
sofar.push_back(*jt+1);
F.put(*jt+1,prev_len[*jt+1]);
Fp.put(*jt+1,prev_poc[*jt+1]);}
}

if(Lcur < L) cout << "-1\n";
else for(int i =0; i < L; i++) cout << ans[i] << ((i == L-1)?"\n":" ");
return 0;}```