HackerEarth Sherlock and Numbers problem solution

In this HackerEarth Sherlock and Numbers problem solution Watson gives to Sherlock a bag of numbers [1, 2, 3 ... N] and then he removes K numbers A1, A2 ... AK from the bag. He now asks Sherlock to find the P'th smallest number in the bag.


HackerEarth Sherlock and Numbers problem solution


HackerEarth Sherlock and Numbers problem solution.

#include<bits/stdc++.h>
#define assn(n,a,b) assert(n<=b && n>=a)
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%d\n",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("\n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007
LL mpow(LL a, LL n)
{LL ret=1;LL b=a;while(n) {if(n&1)
ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}
#define MAXK 100000
#define MAXN 1000000000
int ar[MAXK];
int get(int n, int k){
int i=0;
while(i<k and ar[i]<=n)i++;
return n-i;
}
int main()
{
int t;
sd(t);
assn(t,1,10);
while(t--){
int n,k,p,s=0;
sd(n),sd(k),sd(p);
assn(n,1,MAXN);
assn(k,0,MAXK);
assn(p,1,n);
for(int i=0; i<k; i++)
sd(ar[i]);
sort(ar,ar+k);
int l=0,r=n,mid;
if(get(r,k)<p){
pdn(-1);
continue;
}
while(r-l>1){
mid=(r+l)/2;
int q=get(mid,k);
if(q<p)l=mid;
else r=mid;
}
pdn(l+1);
}
return 0;
}

Second solution

#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define sz size()

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

set<int > s;
vi v;

int lessThan(int x) {

int lo = 0, hi = (int)v.size() - 1;
int res = -1;

while(lo <= hi) {
int mi = (lo + hi) >> 1;
if(v[mi] <= x) {
res = mi;
lo = mi + 1;
} else {
hi = mi - 1;
}
}

return res + 1;
}

int main() {
int t;
S(t);

assert(t >= 1 && t <= 10);

while(t--) {
int n,k,p;
scanf("%d%d%d",&n,&k,&p);
assert(n >= 1 && n <= 1000000000);
assert(k >= 1 && k <= min(n, 100000));
assert(p >= 1 && p <= 1000000000);
s.clear();
v.clear();
rep(i,0,k) {
int x;
S(x);
assert(x >= 1 && x <= n);
if(s.find(x) == s.end()) {
v.push_back(x);
s.insert(x);
}
}

sort(all(v));
int lo = 1, hi = 2*n;

int ans = 0;
while(lo <= hi) {
int mi = (lo + hi * 1LL) / 2;
int x = lessThan(mi);

int tot = mi - x;
if(tot >= p) {
ans = mi;
hi = mi - 1;
} else {
lo = mi + 1;
}
}
if(ans > n) ans = -1;
P(ans);
}

return 0;
}


Post a Comment

0 Comments