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); st.updateOrAdd(0, 0, 1); 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; st.updateOrAdd(b[i]+1, max+1, st.gw); } 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]; addFenwick(ft, 0, 1); addFenwick(ftd, 0, 1); 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++){ addFenwick(ft, prevs[j], -pvs[j]); addFenwick(ftd, prevs[j], -pvs[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]){ addFenwick(ft, (int)t[3], t[2]); addFenwick(ftd, (int)t[3], t[2]); 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; private int readByte() { 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); b = readByte(); } 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; b = readByte(); } 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; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } 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 << "-1n"; else for(int i =0; i < L; i++) cout << ans[i] << ((i == L-1)?"n":" "); return 0;}