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
