Super Kth LIS
Problem Statement :
Given an array of N integers (a0,a1,...,aN-1), find all possible increasing subsequences of maximum length, L. Then print the lexicographically Kth longest increasing subsequence as a single line of space-separated integers; if there are less than K subsequences of length L, print -1. Two subsequences [ap0,ap1,...,apL-1] and [aq0,aq1,...,aqL-1] are considered to be different if there exists at least one i such that pi != qi. Input Format The first line contains 2 space-separated integers, N and K, respectively. The second line consists of N space-separated integers denoting a0,a1,...,aN-1 respectively. Constraints 1 <= N <= 10^5 1 <= K <= 10^18 1 <= ai <= N
Solution :
Solution in C :
In C++ :
#pragma comment(linker, "/STACK:512000000")
#define _CRT_SECURE_NO_WARNINGS
//#include "testlib.h"
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <deque>
#include <ctime>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
//#include <unordered_map>
using namespace std;
//#define FILENAME ""
#define mp make_pair
#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve();
void precalc();
clock_t start;
//int timer = 1;
int testNumber = 1;
bool todo = true;
int main() {
#ifdef _DDEBUG
freopen("input.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#else
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
//freopen(FILENAME".in", "r", stdin);
//freopen(FILENAME ".out", "w", stdout);
#endif
start = clock();
int t = 1;
cout.sync_with_stdio(0);
cin.tie(0);
precalc();
cout.precision(10);
cout << fixed;
//cin >> t;
int testNum = 1;
while (t--) {
//cerr << testNum << endl;
//cout << "Case #" << testNum++ << ": ";
solve();
++testNumber;
//++timer;
}
#ifdef room111
cerr << "\n\n" << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";
#endif
return 0;
}
//BE CAREFUL: IS INT REALLY INT?
//#define int li
/*int pr[] = { 97, 2011 };
int mods[] = { 1000000007, 1000000009 };
const int C = 300500;
int powers[2][C];*/
//int MOD = 1000000007;
//int c[5010][5010];
template<typename T>
T binpow(T q, T w, T mod) {
if (!w)
return 1 % mod;
if (w & 1)
return q * 1LL * binpow(q, w - 1, mod) % mod;
return binpow(q * 1LL * q % mod, w / 2, mod);
}
/*int curMod = 1000000009;
int fact[100500], revfact[100500];
int getC(int n, int k) {
int res = fact[n] * revfact[n - k] % curMod * revfact[k] % curMod;
return res;
}*/
/*const int C = 7000500;
int least_prime[C];*/
void precalc() {
/*for (int i = 2; i < C; ++i) {
if (!least_prime[i]) {
least_prime[i] = i;
for (li j = i * 1LL * i; j < C; j += i) {
least_prime[j] = i;
}
}
}*/
/*fact[0] = revfact[0] = 1;
for (int i = 1; i < 100500; ++i) {
fact[i] = fact[i - 1] * i % curMod;
revfact[i] = binpow(fact[i], curMod - 2, curMod);
}*/
/*for (int w = 0; w < 2; ++w) {
powers[w][0] = 1;
for (int j = 1; j < C; ++j) {
powers[w][j] = (powers[w][j - 1] * 1LL * pr[w]) % mods[w];
}
}*/
/*for (int i = 0; i < 5010; ++i) {
c[i][i] = c[i][0] = 1;
for (int j = 1; j < i; ++j) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
}
}*/
}
template<typename T>
T gcd(T q, T w) {
while (w) {
q %= w;
swap(q, w);
}
return q;
}
template<typename T>
T lcm(T q, T w) {
return q / gcd(q, w) * w;
}
//#define int li
const int mod = 1000000007;
//#define double ld
const int shift = 1 << 17;
struct Node {
int mx;
li sum_mx;
Node():mx(0), sum_mx(0) {}
Node(int mx, li sum_mx):mx(mx), sum_mx(sum_mx) {}
};
const li INF = 2e18;
Node merge(const Node& l, const Node& r) {
Node res = l;
if (res.mx < r.mx) {
res = r;
}
else if (res.mx == r.mx) {
res.sum_mx += r.sum_mx;
if (res.sum_mx > INF) {
res.sum_mx = INF;
}
}
return res;
}
Node tree[2 * shift + 5];
void update(int v, Node new_val) {
v += shift;
tree[v] = new_val;
v /= 2;
while (v) {
tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
v /= 2;
}
}
Node rmq(int l, int r) {
if (l >= r) {
return Node(0, 0);
}
if (l & 1) {
return merge(tree[l], rmq(l + 1, r));
}
if (r & 1) {
return merge(tree[r - 1], rmq(l, r - 1));
}
return rmq(l / 2, r / 2);
}
Node get_rmq(int l, int r) {
return rmq(l + shift, r + shift);
}
li mult(li a, li b) {
if (b == 0) {
return 0;
}
if (a > INF / b) {
return INF;
}
return a * b;
}
li sum(li a, li b) {
li res = a + b;
if (res > INF) {
return INF;
}
return res;
}
void solve() {
int n;
li K;
cin >> n >> K;
vector<pair<int, int>> a(n);
vector<int> vals(n);
for (int i = 0; i < n; ++i) {
cin >> a[i].first;
vals[i] = a[i].first;
a[i].second = -i;
}
sort(all(a));
reverse(all(a));
for (int i = 0; i < n; ++i) {
a[i].second = -a[i].second;
}
vector<vector<int>> best_positions(n + 1);
vector<li> nums(n);
for (int i = 0; i < n; ++i) {
int pos = a[i].second;
Node cur_res = get_rmq(pos, n);
cur_res.mx += 1;
if (cur_res.mx == 1) {
cur_res.sum_mx = 1;
}
update(pos, cur_res);
best_positions[cur_res.mx].push_back(pos);
nums[pos] = cur_res.sum_mx;
}
for (int i = 0; i <= n; ++i) {
sort(all(best_positions[i]));
/*cout << "i = " << i << "\n";
for (int z : best_positions[i]) {
cout << z << ' ';
}
cout << "\n";*/
}
int cur_long = 0;
int last_value = 0;
li sum_all_ways = 0;
for (int i = n; i >= 0; --i) {
if (!best_positions[i].empty()) {
cur_long = i;
for (auto cur : best_positions[i]) {
sum_all_ways = sum(sum_all_ways, nums[cur]);
}
break;
}
}
if (sum_all_ways < K) {
cout << "-1\n";
return;
}
vector<int> ans;
vector<int> last_vec;
last_vec.push_back(-1);
vector<li> last_ways;
last_ways.push_back(1);
for (; cur_long > 0; --cur_long) {
vector<pair<pair<int, int>, pair<li, li>>> candies;
for (int pos : best_positions[cur_long]) {
if (vals[pos] > last_value) {
int id = upper_bound(all(last_vec), pos) - last_vec.begin();
if (id == 0) {
continue;
}
li new_sum_mx = mult(nums[pos], last_ways[id - 1]);
candies.push_back(mp(mp(vals[pos], pos), mp(new_sum_mx, last_ways[id - 1])));
}
}
sort(all(candies));
for (int i = 0; i < candies.size();) {
int j = i;
li sum_ways = 0;
while (j < candies.size() && candies[j].first.first == candies[i].first.first) {
sum_ways = sum(sum_ways, candies[j].second.first);
++j;
}
if (sum_ways >= K) {
ans.push_back(candies[i].first.first);
last_value = ans.back();
last_vec.clear();
last_ways.clear();
for (int r = i; r < j; ++r) {
last_vec.push_back(candies[r].first.second);
last_ways.push_back(candies[r].second.second);
}
for (int r = 1; r < last_ways.size(); ++r) {
last_ways[r] = sum(last_ways[r - 1], last_ways[r]);
}
break;
}
K -= sum_ways;
i = j;
}
}
for (int c : ans) {
cout << c << ' ';
}
}
In Java :
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
public class E {
InputStream is;
PrintWriter out;
String INPUT = "";
static long I = 2000000000_000000000L;
void solve()
{
int n = ni();
long K = nl();
int[] a = na(n);
int[] b = Arrays.copyOf(a, n);
for(int i = 0;i < n;i++)b[i] = n-a[n-1-i];
b = shrink(b);
// 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)); }
}
In Python3 :
#!/bin/python3
import os
import sys
class Node:
prev = []
marked = False
def __init__(self, num: int):
self.num = num
def _set_all_prefixed(new_heap, patience_heaps, curr_ind):
prefix_list = list()
prev_patience_heap = patience_heaps[curr_ind - 1]
patience_heap_size = len(prev_patience_heap)
for i in range(0, patience_heap_size):
elem = prev_patience_heap[i]
if elem.num < new_heap.num:
prefix_list.append(elem)
else:
pass
return prefix_list
def patience_sorting(A: list):
size = len(A)
patience_heaps: list(list(Node)) = [[Node(A[0])]]
for i in range(1, size):
curr = A[i]
smallest_number_bigger_than_curr = sys.maxsize
snbtc_ind = -1
patience_heaps_size = len(patience_heaps)
for j in range(patience_heaps_size):
patience_heap_top = patience_heaps[j][-1]
if smallest_number_bigger_than_curr > patience_heap_top.num >= curr:
smallest_number_bigger_than_curr = patience_heap_top.num
snbtc_ind = j
set_prev = False
if snbtc_ind < 0:
new_heap = Node(curr)
set_prev = True
patience_heaps.append([new_heap])
else:
new_heap = Node(curr)
if snbtc_ind > 0:
set_prev = True
patience_heaps[snbtc_ind].append(new_heap)
# point to the top of the previous patience heap
if set_prev:
# new_heap.prev = patience_heaps[snbtc_ind-1][-1]
new_heap.prev = _set_all_prefixed(new_heap, patience_heaps, snbtc_ind)
return patience_heaps
# def print_all_LIS_wrapper(patience_heaps, k):
# sequence_tails = patience_heaps[-1]
# sequence_tails.reverse()
# count = 1
# for tail in sequence_tails:
# count = print_all_LIS(list(), tail, k, count)
#
#
# def print_all_LIS(subsequence, node, k, count):
# if count > k:
# return count
# temp = [node] + subsequence
# if len(node.prev) == 0:
# if count == k:
# print(' '.join([str(n.num) for n in temp]))
# return count+1
# else:
# node.prev.reverse()
# for prev in node.prev:
# count = print_all_LIS(temp, prev, k, count)
# return count
def print_all_LIS_wrapper(patience_heaps, k):
sequence_tails = patience_heaps[-1]
sequence_tails.reverse()
count = 0
subsequence = list()
for node in sequence_tails:
stack = [node]
while len(stack) != 0:
curr = stack.pop(0)
while len(subsequence) > 0 and curr.num >= subsequence[0]:
subsequence.pop(0)
subsequence.insert(0, curr.num)
prevs = curr.prev
if len(prevs) == 0:
count += 1
if count == k:
return subsequence
else:
for prev in prevs:
stack.insert(0, prev)
return -1
def superKth(k, a):
sorted_heaps = patience_sorting(a)
subsequence = print_all_LIS_wrapper(sorted_heaps, k)
if isinstance(subsequence, list):
retval = [str(a) for a in subsequence]
print(' '.join(retval))
else:
print(subsequence)
if __name__ == '__main__':
nk = input().split()
n = int(nk[0])
k = int(nk[1])
a = list(map(int, input().rstrip().split()))
result = superKth(k, a)
View More Similar Problems
Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →Tree : Top View
Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.
View Solution →Tree: Level Order Traversal
Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F
View Solution →