Booksort Iarcs online judge!

general
,
1

here’s the problem - opc.iarcs.org.in/index.php/problems/BOOKSORT

here’s my code -

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
#define pb push_back

int binarysearch(int a[],int e, int low, int high){
    int pos = -1,mid;
    while (low <= high){
            mid = (low+high)/2;
            if (a[mid] >= e){
                high = mid-1;
                pos = mid;
            }
            else{
                low = mid+1;
            }
    }
    return pos;
}

int lis(int a[], int n){
    int b[n];
    b[0] = a[0];
    int l = 1,x;
    for (int i = 1; i < n; i++){
        if (a[i] < b[0]){
            b[0] = a[i];
        }
        else if (a[i] > b[l-1]){
            b[l] = a[i];
            l ++;
        }
        else{
            x = binarysearch(b,a[i],0,l-1);
            b[x] = a[i];
        }
    }
    return l;
}

int main() {

	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) cin >> a[i];
	int y = lis(a,n);
	cout << n-y << endl;
}

Can someone tell me why it is failing one test-case?

2

2 testcases 4 and 8 , to be specific

3

Probably some kind of memory corruption was there in your program , though when I converted your program to vectors instead of c style arrays , the program worked but got TLE’s for the first and last testcases,

#include <iostream>
#include <vector>

int binarysearch(std::vector<int>a,int e, int low, int high){
    int mid;
    while (low <= high){
            mid = (low+high)/2;
            if (a[mid] > e){
                high = mid-1;
            }
            else{
                low = mid+1;
            }
    }
    return low;
}

int lis(std::vector<int>a, int n){
    std::vector<int> b(n,0);
    b[0] = a[0];
    int l = 1,x;
    for (int i = 1; i < n; i++){
        if (a[i] < b[0]){
            b[0] = a[i];
        }
        else if (a[i] > b[l-1]){
            b[l] = a[i];
            l++;
        }
        else{
            x = binarysearch(b,a[i],0,l-1);
            b[x] = a[i];
        }
    }
    //std::cout << l << std::endl;
    return l;
}

int main() {

	//ios::sync_with_stdio(false);
	int n;
	std::cin >> n;
	std::vector<int> a(n,0);
	for (int i = 0; i < n; i++) std::cin >> a[i];
	int y = lis(a,n);
	std::cout << n-y << std::endl;
}

Well my approach is exactly same but I dont store the inputs in an array instead I dynamically take them and create my longest increasing subsequence.

#include <iostream>
#include <vector>

int binaryS(const int &target,const std::vector<int> &arr,const int &size){
    int low =0;
    int high = size - 1;
    while(low <= high){
        int mid = low + (high-low)/2;
        if(arr[mid] > target ){
            high = mid -1;
        }else{
            low = mid +1;
        }
    }
    return low;
}

int main (){
    int n;
    std::cin >> n;
    std::vector<int>nums(n);
    int size=0;
    for(int i=0;i<n;i++){
        int key;
        std::cin >> key;
        int temp = binaryS(key,nums,size);
        nums[temp] = key;
        if(temp == size){
            size++;
        } 
    } 
    std::cout<< n-size << std::endl;
    return 0;
}
1 Like