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?
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;
}