PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh
DIFFICULTY
Cakewalk
PREREQUISITES
None
PROBLEM
Given N problems in a contest given in the increasing order of difficulty, whose ids are given in sequence A. The team solves the problems in the order of difficulty. Find the minimum number of problems to be solved such that all problems with id in the range [1, 7] are solved.
QUICK EXPLANATION
The minimum number of problems to be solved is the maximum among positions of any problem with difficulty in the range [1, 7].
EXPLANATION
We need to solve all problems with ids in the range [1, 7] and we want to solve the minimum number of problems. We can solve problems only in increasing order of difficulty.
Method 1
Since we can only solve the problems in one order, let’s keep solving the problem until we have solved all problems with ids in the range [1, 7] and stop. i.e. Let’s solve the problem one by one, and after solving each problem, check if we solved all problems with ids in the range [1, 7]. If yes, terminate, otherwise, we proceed to solve the next problem.
We’d need to keep a set of solved problems, and checking if all problems in the range are solved by looping over problem ids in the range [1,7] and checking if all of them are present. When a problem is solved, its id is added to the set.
This sikytuib works in O(N*log(N)) time.
Method 2
Let’s start from the end. Assume we have solved all problems. Now, try reducing the number of solved problems, by leaving problems with the highest difficulty unsolved one by one. When, the problem with the highest difficulty has an id in the range [1, 7], we can no more delete a problem, so the minimum number of problems to be solved is N less the number of problems left unsolved.
This solution can be implemented by a pointer starting from the right end, and moving towards the left one step at a time until it reaches a problem with id in the range [1, 7].
The time complexity of this solution is O(N)
Method 3
Find the positions of all problems, whose ids are in the range [1, 7]. Let’s say X is the maximum among those positions. Then we need to solve exactly X problems, as X is the minimum number of problems, such that by solving the first X problems, we solved all problems with ids in the range [1,7]
The time complexity of this approach is O(N) as well.
Bonus
Let’s say you want to solve at least 6 problems with ids in the range [1, 7]. What is the minimum number of problems you must solve to achieve that, given you can solve the problems in the order of difficulty, and A_i denotes the id of ith problem
TIME COMPLEXITY
The time complexity is O(N) or O(N*log(N)) per test case depending upon implementation.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
using namespace std;
const int maxn = 15, maxtn = 1e5;
bool inc[16];
int cnt[16];
int main()
{
int t, n, x; cin >> t;
int tn = 0;
while(t--){
cin >> n;
tn += n;
memset(inc, false, sizeof(inc));
int mask = 0, rmask = (1 << 7) - 1;
bool found = false;
for(int i = 1; i <= n; i++){
cin >> x;
assert(!inc[x]); inc[x] = true;
if(found)continue;
mask |= (1 << (x - 1));
if((mask & rmask) == rmask){
cout << i << endl;
cnt[i]++;
found = true;
}
}
}
}
Tester's Solution
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int main(){
int T = readIntLn(1, 10500);
while(T-->0){
int N = readIntLn(7, 15);
vector<int> A;
int ans = -1;
for(int i = 1; i<= N; i++){
int x;
if(i+1 <= N)x = readIntSp(1, N);
else x = readIntLn(1, N);
A.push_back(x);
if(x <= 7)ans = i;
}
sort(A.begin(), A.end());
for(int i = 0; i< N; i++)assert(A[i] == i+1);
cout<<ans<<endl;
}
assert(getchar()==-1);
cerr<<"SUCCESS\n";
}
Feel free to share your approach. Suggestions are welcomed as always. 