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 :



title-img 


                            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

Palindromic Subsets

Consider a lowercase English alphabetic letter character denoted by c. A shift operation on some c turns it into the next letter in the alphabet. For example, and ,shift(a) = b , shift(e) = f, shift(z) = a . Given a zero-indexed string, s, of n lowercase letters, perform q queries on s where each query takes one of the following two forms: 1 i j t: All letters in the inclusive range from i t

View Solution →

Counting On a Tree

Taylor loves trees, and this new challenge has him stumped! Consider a tree, t, consisting of n nodes. Each node is numbered from 1 to n, and each node i has an integer, ci, attached to it. A query on tree t takes the form w x y z. To process a query, you must print the count of ordered pairs of integers ( i , j ) such that the following four conditions are all satisfied: the path from n

View Solution →

Polynomial Division

Consider a sequence, c0, c1, . . . , cn-1 , and a polynomial of degree 1 defined as Q(x ) = a * x + b. You must perform q queries on the sequence, where each query is one of the following two types: 1 i x: Replace ci with x. 2 l r: Consider the polynomial and determine whether is divisible by over the field , where . In other words, check if there exists a polynomial with integer coefficie

View Solution →

Costly Intervals

Given an array, your goal is to find, for each element, the largest subarray containing it whose cost is at least k. Specifically, let A = [A1, A2, . . . , An ] be an array of length n, and let be the subarray from index l to index r. Also, Let MAX( l, r ) be the largest number in Al. . . r. Let MIN( l, r ) be the smallest number in Al . . .r . Let OR( l , r ) be the bitwise OR of the

View Solution →

The Strange Function

One of the most important skills a programmer needs to learn early on is the ability to pose a problem in an abstract way. This skill is important not just for researchers but also in applied fields like software engineering and web development. You are able to solve most of a problem, except for one last subproblem, which you have posed in an abstract way as follows: Given an array consisting

View Solution →

Self-Driving Bus

Treeland is a country with n cities and n - 1 roads. There is exactly one path between any two cities. The ruler of Treeland wants to implement a self-driving bus system and asks tree-loving Alex to plan the bus routes. Alex decides that each route must contain a subset of connected cities; a subset of cities is connected if the following two conditions are true: There is a path between ever

View Solution →