Infosys Round 2 Online Assessment(Help me in solving this question)

1

Andy wants to go on a vacation to de-stress himself. Therefore he decides to take a p to an island. It is given that he has as many consecutive days as possible to rest, but he can only make one trip to the island.

Suppose that the days are numbered from 1 to N. Andy has M obligations in his

schedule, which he has already undertaken and which correspond to some specific

days. This means that the ith obligation is scheduled for day D, Andy is willing to cancel at most K of his obligations in order to take more holidays.

Your task is to find out the maximum days of vacation Andy can take by cancelling at most K of his obligations.

Input Format

The first line contains an integer, N, denoting the total number of days

The next line contains an integer, M, denoting the total number of obligations

The next line contains an integer, K, denoting the largest number of obligations he could cancel
Each line i of the M subsequent lines (where 0<=i<=M) contains an integer describing Di.
Constraints

1 <= N <= 10^6
1 <= M <= 210^6
1 <= K <= 210^6
1 <= D[i] <= 10^6
Sample input:
10
5
2
6
9
3
2
7
Sample output:
5(vacation length)
Explanation:
Here he could cancel his 3rd and 4th obligation which makes vacation length 5.

Sample input 2:
7
2
0
3
4
Sample output2:
3
Explanation:
Here he could not cancel any obligation since K=0, so the vacation length is

1 Like
2

n=int(input())

m=int(input())

k=int(input())

l=[]

for i in range(m):

l.append(int(input()))

l.sort()

actual_days=[]

for i in range(n):

actual_days.append(i+1)

if k>0:

l=l[:k]

re=l[-1]

holidays=actual_days[re:]

print(holidays)

print(len(holidays))

else:

re=l[-1]

holidays=actual_days[re:]

print(holidays)

print(len(holidays))
3

Thanks for the answer but some testcases will fail

4

binary search for answer. let answer be x, look for each window of length x , if number of obligations is <=k, this can be done in O(n). Hence total complexity O(nlog(n))

1 Like
5

Accepted Solution :

n = int(input())
m = int(input())
k = int(input())
arr = [int(input()) for i in range(m)]
arr.sort()
arr = [0] + arr + [n+1]
ans = 0
for i in range(k+1, m+2):
    ans = max(ans, arr[i] - arr[i-k-1]-1)
print(ans)
6

can you code that so that I will get a better idea?

7 
// 2 pointers code O(n)
#include<bits/stdc++.h>

using namespace std;


typedef long long ll;
typedef long double ld;

//TIAS MONDAL

const ll maxn=100000+20;
const ll mod=998244353;
const ll m2=1e9+7;
const ll max2=1e3+10;
const ll N = 501;
const ll MAXN=2e5+10;
const ll ALPHABET_SIZE = 2;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")


int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
//long long tt = clock();
#endif
ios_base::sync_with_stdio(NULL);  cin.tie(0); cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,m,k,i;
cin>>n>>m>>k;
int val[n];
memset(val,0,sizeof(val));
for(i=0;i<m;++i)
{
  int x;
  cin>>x;
  --x;
  val[x]=1;

}

int p1=0,p2=0;
int ans=0;
int cur=val[p1];

while(p1<n && p2<n)
{
  if(cur<=k)
  {
    ans=max(ans,p2-p1+1);
    ++p2;
    if(p2<n)
    {
      cur+=val[p2];
    }
  }
  else
  { cur-=val[p1];
    ++p1;

  }
}
cout<<ans;


return(0);

}
1 Like