BALLOON - Editorial

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. :slight_smile:

A simpler approach

#include <bits/stdc++.h>
using namespace std;
#define test_case \
  int t;          \
  cin >> t;       \
  while (t--)
void initial() {  std::ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0); }

int main(){
  initial();
  test_case 
  {
    int n, x;
    cin >> n;
    bool found = false; // To indicate whether all 7 (1-7) (VIBGYOR) are solved
    int mask = 0, rmask = (1 << 7) - 1;
    // mask - 0 (Indicates no problem is solved
   // 1<<7 = 2^7 = 1000 0000
   // 1<<7 = 2^7 - 1 = 111 1111 (all 7 bits are set)
    for (int i = 0; i < n; i++)
    {
      cin >> x;
      if (found)  continue; // If we solved all VIBGYOR once, then no need to increment the count, only read remaining input

      mask |= (1 << (x - 1)); // Whenever a number is read, set that integer position 
     // Ex: 3 is input, mask |= (1<<(3-1) 
     // mask |= (1<<2) 
     // mask |= 100 (3rd bit is set)
     // similarly when all 7 bits are set, then **mask** will become equal to **rmask**
     // which indicates that we solved VIBGYOR
     // since array is 0 indexed, we print **i + 1** as output
      if ((mask & rmask) == rmask) {
        cout << i + 1 << "\n";
        found = true; // set VIBGYOR is present
      }
    }
  }
  return 0;
}
2 Likes

can you please share the test cases used for this program?

1 Like

https://www.codechef.com/viewsolution/47969234

Please tell me why this code is incorrect?

2 Likes

Please tell me why this is giving WA
int tt;
cin >> tt;
while(tt–){
int n;
cin >> n;
int i;
int count = 0;
for(i = 1; i <= n; i++){
int x;
cin >> x;
if(x <= 7)
count++;
if(count == 7){
cout << i << endl;
break;
}
}
}

Can you explain your code since I am a beginner I am unable to understand the logic of the code.

In test cases such as 1,1,2,3,4,5,6,7,8 your count will be equal to 7 when your i reaches to 6 so he didn’t solve question with difficulty 7 and still your code printed the output.
The bottom line is this code won’t work if there is any duplicate.

1 Like

@entschluselt Same doubt!
Any help would really be appreciated!
Thank you.

In test cases such as 1,1,2,3,4,5,6,7,8 your count will be equal to 7 when your i reaches to 6 so he didn’t solve question with difficulty 7 and still your code printed the output.
The bottom line is this code won’t work if there is any duplicate.

That code won’t work if there is any duplicates in the input

@nishant_sagar Thank you for taking time to help.
May I know why is this code failing even though I considered the duplicate test cases and re-wrote the code once again.

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

int main()
{
int t,n,i;
cin>>t;
while(t–)
{
cin>>n;
int a1=0,a2=0,a3=0,a4=0,a5=0,a6=0,a7=0,f=0;
int a[n+1];
for(i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==1 && a1==0)
{
a1++;
f++;
}
else if(a[i]==2 && a2==0)
{
a2++;
f++;
}
else if(a[i]==3 && a3==0)
{
a3++;
f++;
}
else if(a[i]==4 && a4==0)
{
a4++;
f++;
}
else if(a[i]==5 && a5==0)
{

            a5++;
            f++;
        }
        else if(a[i]==6 && a6==0)
        {
            a6++;
            f++;
        }
        else if(a[i]==7 && a7==0)
        {
            a7++;
            f++;
        }
        if(a1==1 && a2==1 && a3==1 && a4==1 && a5==1 && a6==1 && a7==1 && f==7)
        {
            cout<<i<<"\n";
            break;
        }
    }
}
return 0;

}

@ekatva your solution would have worked fine if you would have first taken all the array elements, and then would have written the rest of the logic in the next for loop. for eg., if you consider the test case :
2
9
7 4 3 5 6 1 8 2 9
7
1 2 3 4 5 6 7
then for the first test case, your code only read input till the eighth element only in the first case and then would have moved to the next test case where it would have taken 9 as the value of n and then would produced a runtime exteption

2 Likes

@hi_anusha consider the test case
2
9
7 4 3 5 6 1 8 2 9
7
1 2 3 4 5 6 7
just seperate the code for reading input of test case and the rest of the logic. you will get an AC then, and ya you don’t need to keep check for duplicates as the question clearly states that the array elements are pairwise distinct

@deonarayan_08 Thanks a lot !!!

The entries are pairwise-distinct. They cannot be identical. The only error is that she takes the input and processes it in the same loop.

2 Likes

Hi all. I couldn’t solve the question initially. This is my solution. pls have a look. I don’t know why it wouln’t work. i applied a different logic and got the code working but still if you can help me then thanks.

    #include <iostream>

using namespace std;

int main() {

int N,T;

cin>>T;


while(T!=0)
{
    int countSeven = 0;
    int count = 0;
    int minCount = 0;
    cin>>N;
    int arr[N];
    for(int i = 0; i < N;i++)
    {
        cin>>arr[i];
        
        if(arr[i] <= 7)
        {
            countSeven++;
        }
        else
        {
            count++;
        }
        
        if(countSeven == 7)
        {
            break;
        }
    }

    minCount = count + countSeven;
    cout<<minCount<<endl;
    T--;
}


return 0;

}

This solution should work right? because the elements are pairwise distinct. Honestly speaking, my definition of pairwise distinct is that there would be no repeating digits in the whole array. correct me if I am wrong. Thanks!

Ok, I understand. Thanks for the help!

2 Likes

There is a slack in the test cases because my solution which technically shouldn’t pass gave AC
https://www.codechef.com/viewsolution/47977518
This solution doesn’t work for the test case 1 2 3 4 5 6 7 1 2 3 4 5 6 7
@admin look at it thanks!

Yes,Your logic is correct I think you are going wrong because you are not taking the entire elements in the array.You are trying to break the solution as soon as you find seven elements but you must run the entire loop try to modify the loop accordingly.

1 Like

Quick Editorial:
Prequisites: Basic Hashing

My approach towards the problem was kind of mixture of editorials method 1 and method 3. I solved the problem using simple hashing.At First,I took all the elements in the array and thereafter incremented the problem id by 1.At every point I increment I made sure that I used the check function to check whether all the problems 1 to 7 were done as soon as the problems are done I marked min_idx = i + 1(since i used 0 based indexing) in case of 1 based indexing you can do the necessary changes.

Code:
https://www.codechef.com/viewsolution/47972437

Time Complexity:O(7*N) per test case
If I am wrong somewhere feel free to correct me.:slight_smile: