Table of Contents

# Super Kth LISĀ – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

# Solutions of Algorithms Data Structures Hard HackerRank:

## Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts

# C++ replace HackerRank Solution

#include <algorithm> #include <cassert> #include <cstring> #include <iostream> using namespace std; #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define REP(i, n) FOR(i, 0, n) #define TRACE(x) cout << #x << " = " << x << endl #define _ << " _ " << typedef long long llint; const int MAX = 100100; const llint inf = 2e18; int L[MAX]; int getMax(int x) { int r = 0; for (++x; x; x -= x&-x) r = max(r, L[x]); return r; } void update(int x, int v) { for (++x; x < MAX; x += x&-x) L[x] = max(L[x], v); } llint S[MAX]; llint add(llint x, llint y) { return min(inf, x + y); } llint mul(llint x, llint y) { if (x == 0 || y == 0) return 0; if (x < (inf + y - 1) / y) return min(x * y, inf); return inf; } llint sum(int x) { llint r = 0; for (++x; x; x -= x&-x) r = add(r, S[x]); return r; } void add(int x, llint v) { for (++x; x < MAX; x += x&-x) S[x] = add(S[x], v); } void clear(int x) { for (++x; x < MAX; x += x&-x) S[x] = 0; } int a[MAX]; int f[MAX]; llint g[MAX]; vector<int> v[MAX]; int main(void) { int N; llint K; scanf("%d %lld", &N, &K); REP(i, N) scanf("%d", &a[i]); for (int i = N-1; i >= 0; --i) { f[i] = getMax(N-a[i]-1) + 1; update(N-a[i], f[i]); } int L = getMax(N); REP(i, N) v[f[i]].push_back(i); for (int i = 1; i <= L; ++i) { int p = (int)v[i - 1].size() - 1; for (int j = (int)v[i].size() - 1; j >= 0; --j) { while (p >= 0 && v[i-1][p] > v[i][j]) { add(N-a[v[i-1][p]], g[v[i-1][p]]); p--; } if (i == 1) g[v[i][j]] = 1; else g[v[i][j]] = sum(N-a[v[i][j]]-1); } while (++p < (int)v[i-1].size()) clear(N-a[v[i-1][p]]); } llint total = 0; for (int x: v[L]) total = add(total, g[x]); if (total < K) { puts("-1"); return 0; } vector<pair<int, llint>> cur = {{-1, 1}}; vector<int> ans; int last = 0; for (int i = L; i > 0; --i) { auto count = [&] (int x) { int p = (int)v[i].size() - 1; llint total = 0; llint rsum = 0; for (int j = (int)cur.size() - 1; j >= 0; --j) { while (p >= 0 && v[i][p] > cur[j].first) { if (last < a[v[i][p]] && a[v[i][p]] <= x) rsum = add(rsum, g[v[i][p]]); p--; } total = add(total, mul(rsum, cur[j].second)); } return total; }; int lo = last + 1, hi = N; while (lo < hi) { int mid = (lo + hi) / 2; if (count(mid) < K) lo = mid + 1; else hi = mid; } K -= count(lo - 1); vector<pair<int, llint>> ncur; int p = 0; llint rsum = 0; REP(j, (int)v[i].size()) { while (p < (int)cur.size() && cur[p].first < v[i][j]) rsum = add(rsum, cur[p++].second); if (a[v[i][j]] == lo) ncur.push_back({v[i][j], rsum}); } cur = ncur; ans.push_back(lo); last = lo; } for (int x: ans) printf("%d ", x); printf("\n"); return 0; }

# Java rep HackerRank Solution

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); // for(int i = 0;i < n;i++)b[i]++; SegmentTreeRMQSumWhenMax st = new SegmentTreeRMQSumWhenMax(n+5); st.updateOrAdd(0, 0, 1); // shifted by 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); // <=a[i] 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); // <=a[i] 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]); } // 1 4 5 3 5 Arrays.sort(temps, 0, p, new Comparator<long[]>() { public int compare(long[] a, long[] b) { return Long.compare(a[0], b[0]); } }); // tr("temps", temps); 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]){ // tr("add", t); addFenwick(ft, (int)t[3], t[2]); addFenwick(ftd, (int)t[3], t[2]); prevs[pp] = (int)t[3]; pvs[pp] = t[2]; pp++; } } } // tr(g); // tr(maxs); // tr(counts); for(int i = 0;i < lis;i++){ out.print(ret[i] + " "); } out.println(); // tr(K); } 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); } // if x equals to before st[H+pos], +y, else update y 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; // y % mod wd[H+pos] = y; // y % mod } 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))){ // when nextLine, (isSpaceChar(b) && 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)); } }

# Python 3 rep HackerRank Solution

# Python 2 rep HackerRank Solution

# C rep HackerRank Solution

/* Giving 1 <= n <= 10**5 items ranging in [1 ... n] determine the 1 <= kth <= 10**18 lexicographic increasing sequence of maximal length, i.e. for all increasing sequences whose length is maximal determine the kth entry; print -1 should one not exist; We will start by determining the length of the/a longest increasing sub-sequence ending at each member, we first normalize all entries, i.e. we replace each entry by their distinct rank; (the overall number of distinct entries that are lesser than or equal to itself), while keeping track the original values since this are the ones that must be yielded) this can be done in O(n) time/space by sorting all entries using frequency sort since all entries are lesser than or equal to n; Using a fenwick tree and a scan-line algorithm we can determine the greatest length seen among all those previously processed entries whose normalized items are strictly lesser then the current entry; since this entry would increase all previously seen lesser terminals; implying that the longest length for this new terminal must be 1 greater; after which we update all prefixes that takes into consideration the current normalized entry (i.e. all sucessors) being that the tree must take into consideration all processed lengths; Querying/Updating a fenwick tree takes at most log(k) where k is the number of distinct entries, since we are using normalized entries as our keys, implying this at worst would take O(n * log(k)) time w/ O(n + k) space; Since we are only interested in solutions whose length is the same as the overall max (longest), and for each component of our solution we need to shift to the nearest adjacent, we need to calculate the total number of increasing sub-sequences that start at each member and whose overall length is the same as our overall max length; This can be achieved using a combination of merge sort and scan-line; We arg sort all members by their maximal lengths using a stable sorting algorithm; being that the max length has to be lesser than or equal to n this can be achieved in O(n + max_length) space/time using frequency sort; Initialize the totals to 1 for those members whose lengths exactly match our overall max length, while zeroing the rest; Note that as we merge each ordered member of length l and length l + 1 both in descending manner; (assuming we've initialized the totals of all those whose length is exactly the max to 1; for each member of length l we need to sum the totals of all successors i.e. those of length l + 1 and whose respective entries as strictly greater; we can use a fenwick tree to store the sum of totals among all suffixes with respect to processed successors indexed by their corresponding entry; Implying that as we merge should the current member of length l be further out then the current member of l + 1; then the tree must hold all 'valid' sums; and no other other member of l + 1 need be considered since both sets are being processed in descending order; as such we take sum among all suffixes whose entries are strictly are greater then that of the current member of l; On the other hand should the current member of l + 1 be a successor to the current member of l implying that it would also have to be a successor to all predecessors of the current member of l; we would need to instead update our tree by incrementing all suffixes that the current members entry intercepts (i.e. all those lesser) by this members total; We do this while we still have l + 1 members; after which we processed any remaining l entries, since they would have to be predecessors to all members of l + 1; NOTE that the overall number of solutions can very eassily exceed our precession, though sine we will still be iterating a smaller number of solutions overall (O(rank) < 10**18); we can use saturated arithmetic i.e. should at any time our summation exceed our precession (i.e. we overflow) we will store the largest possible value that can be represented instead; Afterwhich we would need to reset our tree since that at any giving time it only considers the current total among those members having the same length; as such we will iterate over each member of l + 1 that was processed, and actually mutated the tree, i.e. it had a non-zero total; reseting all intercepting NON-ZERO suffixes, as such at no time do we ever processed any distinct path more than our once, since we had always incremented all intercepting suffixes, with a non-zero value; if we traverse this path again and should at any time arrive at a zero entry implies that a previous member must have cleared all further entries; Since either quering/updating a fenwick tree always takes at most O(log(n)) implies that this overall would take O(n * log(k)) since we witness each member at most twice once to query and again to update; since each has exactly one length, and while resetting the tree we only traverse each distinct path at most once; Note in order to determine our answer we would need to at the very least start at the overall smallest sub-sequence which would require for each member to determine the smallest 'valid' successor should their be any collisions we will choose the furthest out, i.e. first seen, while applying our previous merge algorithm; since we want the lexicographically smallest, implies that during collisions, should their be any greater successor that lie between the two occurrences implies that the nearest occurrence may have a greater count, but at the same time also share a 'common' number of solutions with those starting at successive occurrences; as such we only want to move to a preceding occurrence once we've exhausted all possible 'smaller' candidates; i.e. since we want to iterate solutions in lexicographic order should we take the nearest (last) occurrence we ran the risk of iterating sub-sequences out of order since if we assume that our answer lies on the next set of sub-sequences we would consume all those that are in common as well as possibly those that are greater on the other hand if we take the furthest out this can't possibly happen since should we take next set of solutions at the very least we would have to iterate overall those in common first before reaching those that are greater; since for all solutions starting a the first occurrence we can also choose any of the preceding occurrences; Either way this does not change our complexities since we would simply use a second fenwick tree to to store the argmax and query/update it at the same we touch the first tree; After which we can filter all members that failed to generate a maximal length i.e. those whose counts remained zero; leaving behind all the candidates at each possible length; Since at any giving time we want to be able to move to the nearest set of solutions at any giving length; for each possible length we will sort all the remaining members in a stable ascending manner; we note that for any giving pair of members should their entries differ, then the one with the smaller entry should precede the greater, on the other hand should the entries match we would need to determine which would yield the overall min, i.e. iterate up to the nearest different successor, and take which ever yielded the smaller; we can speed things up by storing the index of each member at each distinct length after they are sorted in which case should the pairs entries match we can look at the offset of their respective successors; though if the matching entries have the same member as a successor we will instead use their respective total number of sub-sets, i.e. the one with smaller total should preceed the one with greater; since this smaller number is the number of common solution between the two; This at worse would take O(n log(n)) time w/ O(n) space using merge sort; We start with a candidate by iterating all successors starting at the smallest ordered sub-sequence starting at length 1; Note that the overall number of frequency of solutions is also dependent on the distribution of each preceding member; if at any time our current candidate solution can choose from k members that yield the same solution, each representing all occurrences of the same entry leading to the same successor and each being a successor to the previous entry of our solution implies that the overall total would be the product of this two totals, impliying we would also need to calculate the frequency to which this prefix may occur while each being valid to the current suffix; which can be determined while scanning all valid candidates, and keeping track their overall product up to each suffix; Now that we can determine the overall number of sub-sets that are lesser than or equal to some prefix of our solution we can binary search for the nearest suffix whose overall total being (the product frequency of its current prefix and the number of sub-sequences that start at its self) is greater than our rank; implying that at the very least this prefix 'may' remain and we would need to shift its successor to the next set of solutions, since they are each sorted implies if this successors neighbor exists it must contain at the very least the same sub-set of solutions as the original entry; of which we remove from our rank, though if none are available implies that we are at the end of our prefix we would need to search for the nearest predecessor with an available neighbor should none exists implies that we must have exhausted all solutions, as such we set our solution to -1 and terminate; After replacing the successor with a valid neighbor we would need to update all prefix frequencies as well as suffixes starting at this updated point; since the swap values may not point to the same successor, and/or change the distribution of items; Eitherway we repeat until we've either exhausted all solutions in which case we print -1 or our current solution has an overall frequency smaller or equal to our rank; in which case this must be our solution since we're always consuming sets of solutions either with equal or greater lexicographic rank; The complexity of this algorithm is a bit tricky, determining the prefix frequencies takes at worse O(n) since we can simply scan for all valid candidates at each component of our solution; at first glance it seems O(n**2) if we always end up at the first (smallest) component, then we would need to rebuild our solution though obviously if our max length was n, then this can only occur at most once, since we could only have 1 initial component, on the other hand if we have m initial components and our max length is l with c overall candidate components then this would take O(m * (l + c)) since l <= c implying O(m * c), should m = n/2 and c = n/2 in the case where we have n/2 duplicate mins followed by a common suffix (i.e. a strictly increasing sub-sequence of length n/2), and giving a rank exceeding all possible solutions then indeed this would take O(n**2) being that we would have O((n/2) * ((n/2) + log(n/2))) <=> O(n**2) Therefore lets store the prefix frequencies in a fenwick tree where each of its nodes store the product of all its descendant/prefix frequencies indexed by the components offset into the current solution, this would increase our prefix counts from O(n) to O(n * log(max_length)) and our binary search for the nearest overflowed suffix from O(n * log(max_length)) to O(n * log(max_length)**2) since for each query point we would have to also query the second tree to determine the prefix frequency; though now if we where to update a member whose frequency is greater than 1, since we know its neighbor had to have the same successor we need only to update our fenwick tree of products by first removing the previous frequency, i.e. dividing all intercepting prefixes and adding the new frequency being 1 unit lesser, this would take at worse O(log(max_length)), reducing our time complexity to O(n * (log(n)**2 + log(n)) (if we always land on members with frequencies) Still if we where to update an entry whose frequency was 1, instead of rebuilding the rest of our solution we note if at any time we reach a previously matching successor (assuming we've updated its all previous frequencies) then implies that the rest of our solution would remain the same as such we can halt here, implying at worse we are only updating delta components. Note that we need to take great care when moving between set of solutions since there could be many candidates that yield the same total lesser than our current rank; though being we are looking for the next smallest set of solutions implies we should search for the furthest suffix that both yield the same total and has a valid neighbor with our current prefix, since each candidate was sorted assuming to have no prefix, it could be the case that the nearest smaller neighbor may require a greater prefix, should it start before our prefix invalidating our previous assumption of consume sets in a monotonic fashion; */ #include <stdio.h> #include <string.h> #include <stdlib.h> #pragma GCC optimize("O2") unsigned long sat_prod(unsigned long self, unsigned long factor) { if ((self < 0x100000000UL) && (factor < 0x100000000UL)) return (self * factor); if (((__builtin_clzl(self) ^ 63U) + (__builtin_clzl(factor) ^ 63U)) >= 64) return 0xFFFFFFFFFFFFFFFFUL; if (self < factor) { self ^= factor; factor ^= self; self ^= factor; } // a * b; b <=> (b[0]*2**0 + b[1]*2**1 + ... + b[k]*2**k) // => a*b[0]*2**0 + a*b[1]*2**1 + .... + a*b[k]*2**k unsigned long product = 0; for (; factor; factor >>= 1, self <<= 1) { if (factor & 1) { if (product > (0xFFFFFFFFFFFFFFFFUL ^ self)) return 0xFFFFFFFFFFFFFFFFUL; product += self; } if ((self & 0x8000000000000000UL) && (factor > 1)) return 0xFFFFFFFFFFFFFFFFUL; } return product; } void descending_stbl( unsigned cnt, unsigned *self, unsigned *items, unsigned *smallest, unsigned *largest, unsigned *offsets ) { unsigned at, span, at_left, at_right, *left, *right, order[cnt]; for (span = 1; span < cnt; span <<= 1) { left = &((unsigned *)memcpy(order, self, sizeof(order)))[(at = cnt) - 1]; for (right = &left[span]; at > span; ) { right -= (span << 1); at_left = (at < (span << 1)) ? (at - span) : span; for (left -= (at_left + (at_right = span)); at_left && at_right; ) if (items[left[at_left]] == items[right[at_right]]) { if (smallest[left[at_left]] == smallest[right[at_right]]) { if (largest[left[at_left]] == largest[right[at_right]]) self[--at] = right[at_right--]; else self[--at] = (offsets[largest[left[at_left]]] > offsets[largest[right[at_right]]]) ? left[at_left--] : right[at_right--]; } else self[--at] = (offsets[smallest[left[at_left]]] > offsets[smallest[right[at_right]]]) ? left[at_left--] : right[at_right--]; } else self[--at] = (items[left[at_left]] < items[right[at_right]]) ? left[at_left--] : right[at_right--]; memcpy(&self[at -= (at_left | at_right)], &right[1], at_right * sizeof(self[0])); } } } int main() { unsigned cnt; unsigned long rank; scanf("%u %lu", &cnt, &rank); unsigned at, others, tail, next, items[cnt + 1]; for (tail = 0, at = cnt; at--; ) if (tail < ((void)scanf("%u", &items[at]), items[at])) tail = items[at]; unsigned distinct, orig[cnt]; { unsigned ids[++tail]; memset(ids, 0, sizeof(ids)); for (at = cnt; at--; ids[items[at]] = 1); for (; ++at < tail; ids[at + 1] += ids[at]); for (distinct = ids[at], at = cnt; at--; items[at] = ids[items[at]] - 1) orig[ids[items[at]] - 1] = items[at]; } unsigned max_length = 0xFFFFFFFFU, lengths[cnt]; memset(lengths, 0xFF, sizeof(lengths)); { int prefixes[distinct]; memset(prefixes, 0xFF, sizeof(prefixes)); for (at = cnt; at--; ) { for (others = items[at]; others; others &= others + 1) if ((int)lengths[at] < prefixes[--others]) lengths[at] = prefixes[others]; if (max_length == lengths[at]++) max_length++; for (others = items[at]; others < distinct && prefixes[others] < (int)lengths[at]; others |= others + 1 ) prefixes[others] = lengths[at]; } } unsigned order[cnt], indices[++max_length + 2]; memset(indices, 0, sizeof(indices)); for (at = cnt; at--; *(unsigned long *)&indices[lengths[at]] += 0x100000001UL); for (; ++at < (max_length >> 1); ((unsigned long *)indices)[at + 1] += ((unsigned long *)indices)[at]); for (at = 0; at < cnt; at++) order[--indices[lengths[at]]] = at; unsigned long suffix_counts[cnt]; unsigned successors[cnt]; { unsigned suffixes[distinct]; for (orig[(items[at] = distinct)] = 0xFFFFFFFFU; at & 1; successors[--at] = cnt); for (at >>= 1; at--; ((unsigned long *)successors)[at] = 0x100000001UL * cnt); for (at = distinct; at & 1; suffixes[--at] = cnt); for (at >>= 1; at--; ((unsigned long *)suffixes)[at] = 0x100000001UL * cnt) ; memset(suffix_counts, 0, sizeof(suffix_counts)); for (next = (tail = indices[(at += max_length)]); tail < indices[max_length]; suffix_counts[order[tail++]] = 1UL ); unsigned long sums[distinct]; for (memset(sums, 0, sizeof(sums)); at--; tail = indices[at + 1]) { while (indices[at] < next && indices[at + 1] < tail) if (order[tail - 1] < order[next - 1]) { if (suffix_counts[order[--tail]]) for (others = items[order[tail]] + 1; others; others &= others + 1) { if (items[order[tail]] < items[suffixes[--others]]) suffixes[others] = order[tail]; if (sums[others] > (0xFFFFFFFFFFFFFFFFUL ^ suffix_counts[order[tail]])) sums[others] = 0xFFFFFFFFFFFFFFFFUL; else sums[others] += suffix_counts[order[tail]]; } } else for (others = items[order[--next]] + 1; others < distinct; others |= others + 1) { if (items[suffixes[others]] < items[successors[order[next]]]) successors[order[next]] = suffixes[others]; if (suffix_counts[order[next]] > (0xFFFFFFFFFFFFFFFFUL ^ sums[others])) suffix_counts[order[next]] = 0xFFFFFFFFFFFFFFFFUL; else suffix_counts[order[next]] += sums[others]; } while (indices[at] < next) for (others = items[order[--next]] + 1; others < distinct; others |= others + 1) { if (items[suffixes[others]] < items[successors[order[next]]]) successors[order[next]] = suffixes[others]; if (suffix_counts[order[next]] > (0xFFFFFFFFFFFFFFFFUL ^ sums[others])) suffix_counts[order[next]] = 0xFFFFFFFFFFFFFFFFUL; else suffix_counts[order[next]] += sums[others]; } for (; tail < indices[at + 2]; tail++) if (suffix_counts[order[tail]]) for (others = items[order[tail]] + 1; others && sums[--others]; others &= others + 1 ) { sums[others] = 0; suffixes[others] = cnt; } } } for (others = 0; ++at < cnt; ) if (suffix_counts[order[at]]) { order[others++] = order[at]; indices[lengths[order[at]] + 1] = others; } unsigned *offsets = lengths; { unsigned largest_successor[order[0] + 1]; for (tail = (next = indices[at = (max_length - 1)]); tail < indices[max_length]; largest_successor[order[tail++]] = cnt) ; for (items[cnt] = 0; at--; tail = indices[at + 1]) { for (others = cnt; indices[at] < next && indices[at + 1] < tail; ) if (order[tail - 1] < order[next - 1]) { if (items[others] <= items[order[--tail]]) others = order[tail]; } else if (items[order[--next]] < items[others]) largest_successor[order[next]] = others; while (indices[at] < next) if (items[order[--next]] < items[others]) largest_successor[order[next]] = others; } items[cnt] = distinct; distinct = order[0] + 1; for (others = indices[(at = max_length)]; at--; ) for (descending_stbl( others - indices[at], &order[indices[at]], items, successors, largest_successor, offsets ); others > indices[at]; offsets[order[others]] = others ) --others; } unsigned freqs[distinct], solution[max_length + 1]; unsigned long prefix_factors[max_length + 1]; for (at = max_length; at--; prefix_factors[at] = 1UL); for (at = distinct; at & 1; freqs[--at] = 1); for (at >>= 1; at--; ((unsigned long *)freqs)[at] = 0x100000001UL); tail = 0xFFFFFFFFU; at = order[(indices[1] - 1)]; for (next = 0; next < max_length; at = successors[(tail = at)]) { for (others = offsets[(solution[next] = at)]; others-- > indices[next] && items[order[others]] == items[at] && successors[order[others]] == successors[at] && order[others] < tail; freqs[at]++ ); next++; prefix_factors[next] = sat_prod(prefix_factors[next], freqs[at]); if ((next | (next + 1)) < max_length) prefix_factors[next | (next + 1)] = sat_prod( prefix_factors[next], prefix_factors[next | (next + 1)] ); } unsigned long factors, total; unsigned base = 0; for ( ; ; ) { for (others = max_length - base; others; others >>= 1) { tail = (base + (others >> 1)); for (total = suffix_counts[solution[tail++]]; tail && total < rank; tail &= tail + 1 ) total = sat_prod(total, prefix_factors[--tail]); if (total >= rank) { base += (others >> (others != 1)); others += (others & (others != 1)); } } if (base == max_length) break ; for (factors = 1UL, tail = (at = base) + 1; tail; tail &= tail + 1) factors *= prefix_factors[--tail]; for (total = (factors * suffix_counts[solution[at]]); at < max_length && (factors * suffix_counts[solution[at]]) == total; factors *= freqs[solution[at++]] ); do for (others = offsets[solution[--at]]; indices[at] < others && at && solution[at - 1] < order[others - 1]; others--); while (at && others == indices[at]); if (others == 0) { solution[0] = cnt; max_length = 1; break ; } rank -= total; next = order[others - 1]; if (freqs[solution[at]] > 1) { freqs[next] = freqs[solution[at]] - 1; for (solution[at++] = next; at < max_length; at |= at + 1) { prefix_factors[at] /= (freqs[next] + 1); prefix_factors[at] *= freqs[next]; } } else for (; next != cnt; next = successors[next]) { tail = freqs[solution[at]]; for (others = offsets[next], freqs[next] = 1; others-- > indices[at] && items[order[others]] == items[next] && successors[order[others]] == successors[next]; freqs[next]++ ); if (tail != freqs[next]) for (others = at + 1; others < max_length; others |= others + 1) { prefix_factors[others] /= tail; prefix_factors[others] *= freqs[next]; } if (solution[at] == next) break ; solution[at++] = next; } } for (printf("%i", orig[items[solution[(at = 0)]]]); ++at < max_length; printf(" %u", orig[items[solution[at]]])); return 0; }

## Warmup

Implementation

Strings

Sorting

Search

Graph Theory

Greedy

Dynamic Programming

Constructive Algorithms

Bit Manipulation

Recursion

Game Theory

NP Complete

Debugging

## Leave a comment below