• Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
Wednesday, February 1, 2023
  • Login
Zeroplusfour
No Result
View All Result
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
No Result
View All Result
Zeroplusfour
No Result
View All Result
Home Code Solutions Hackerrank Algorithms

Super Kth LIS – HackerRank Solution

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

admin by admin
August 24, 2022
Reading Time: 1 min read
0
15 Days to learn SQL Hard SQL(Advanced)-Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution alt text

Spread the love

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
  • Java rep HackerRank Solution
  • Python 3 rep HackerRank Solution
  • Python 2 rep HackerRank Solution
  • C rep HackerRank Solution
    • Warmup Implementation Strings Sorting Search Graph Theory Greedy Dynamic Programming Constructive Algorithms Bit Manipulation Recursion Game Theory NP Complete Debugging
    • Leave a comment below
      • Related posts:

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


Copy Code Copied Use a different Browser

#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


Copy Code Copied Use a different Browser

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


Copy Code Copied Use a different Browser

 



Python 2 rep HackerRank Solution


Copy Code Copied Use a different Browser

 



C rep HackerRank Solution


Copy Code Copied Use a different Browser

/*
    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

 

Related posts:

15 Days to learn SQL Hard SQL(Advanced)-SolutionKth Ancestor – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionA Super Hero – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionBike Racers – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionNo Prefix Set – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionHuarongdao – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionCounting Sort 1 – HackerRank Solution
Tags: Cc++14full solutionGoHackerRank Solutionjavajava 15java 7java 8java8javascriptpypy 3Python 2python 3Super Kth LIS
ShareTweetPin
admin

admin

Related Posts

Leetcode All Problems Solutions
Code Solutions

Exclusive Time of Functions – LeetCode Solution

by admin
October 5, 2022
0
30

Exclusive Time of FunctionsĀ - LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions...

Read more
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
32
Leetcode All Problems Solutions

Course Schedule III – LeetCode Solution

October 5, 2022
25
Leetcode All Problems Solutions

Maximum Product of Three Numbers – LeetCode Solution

September 11, 2022
52
Leetcode All Problems Solutions

Task Scheduler – LeetCode Solution

September 11, 2022
119
Leetcode All Problems Solutions

Valid Triangle Number – LeetCode Solution

September 11, 2022
28
Next Post
15 Days to learn SQL Hard SQL(Advanced)-Solution

Counting the Ways - HackerRank Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution

Hard Disk Drives - HackerRank Solution

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

You may also like

15 Days to learn SQL Hard SQL(Advanced)-SolutionKth Ancestor – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionA Super Hero – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionBike Racers – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionNo Prefix Set – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionHuarongdao – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionCounting Sort 1 – HackerRank Solution

Categories

  • Algorithms
  • Anime
  • Biography
  • Business
  • Code Solutions
  • Cosmos
  • Countdowns
  • Culture
  • Economy
  • Education
  • Entertainment
  • Finance
  • Games
  • Hackerrank
  • Health
  • How to
  • Investment
  • LeetCode
  • Lifestyle
  • LINUX SHELL
  • Manga
  • News
  • Opinion
  • Politics
  • Sports
  • SQL
  • Tech
  • Travel
  • Uncategorized
  • Updates
  • World
  • DMCA
  • Home
  • My account
  • Privacy Policy
  • Top Posts

Recent Blogs

Leetcode All Problems Solutions

Exclusive Time of Functions – LeetCode Solution

October 5, 2022
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
The Girl From Plainville
Entertainment

The Girl From Plainville Episode 9 Countdown , Release Date

May 5, 2022
10
15 Days to learn SQL Hard SQL(Advanced)-Solution
Algorithms

Drawing Book – HackerRank Solution

May 31, 2022
6
15 Days to learn SQL Hard SQL(Advanced)-Solution
Code Solutions

Paste – 2 – HackerRank Solution

August 25, 2022
0
12 BENEFITS OF DOING EXERCISE: Scientifically proven
Health

12 BENEFITS OF DOING EXERCISE: Scientifically proven

May 19, 2022
0

Ā© 2022 ZeroPlusFour - Latest News & Blog.

No Result
View All Result
  • Home
  • Category
    • Business
    • Culture
    • Economy
    • Lifestyle
    • Health
    • Travel
    • Opinion
    • Politics
    • Tech
  • Landing Page
  • Support Forum
  • Contact Us

Ā© 2022 ZeroPlusFour - Latest News & Blog.

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking ā€œAccept Allā€, you consent to the use of ALL the cookies. However, you may visit "Cookie Settings" to provide a controlled consent.
Cookie SettingsAccept All
Manage consent

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
CookieDurationDescription
cookielawinfo-checkbox-analytics11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional11 monthsThe cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy11 monthsThe cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytics
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
Advertisement
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Others
Other uncategorized cookies are those that are being analyzed and have not been classified into a category as yet.
SAVE & ACCEPT
Are you sure want to unlock this post?
Unlock left : 0
Are you sure want to cancel subscription?