CIREQ - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Soumyadeep Pal
Tester: Takuki Kurokawa
Editorialist: Yash Kulkarni

DIFFICULTY:

1620

PREREQUISITES:

Heaps

PROBLEM:

​A 1-indexed array is called positive if every element of the array is greater than or equal to the index on which it lies. Formally, an array B of size M is called positive if B_i \ge i for each 1\le i \le M.

For example, the arrays [1], [2, 2], [3, 2, 4, 4] are positive while the arrays [2, 1], [3, 1, 2] are not positive.

You are given an array A containing N integers. You want to distribute all elements of the array into some positive arrays. The elements of a positive array might not occur in the order they appear in the array A.

Find the minimum number of positive arrays that the elements of the array A can be divided into.

Please see the sample cases below for more clarity.

EXPLANATION:

Hint

It is always better to keep smaller elements before larger ones while forming a positive array because this will surely reduce the number of positive arrays required to distribute all the elements in A.
Hence, sorting will surely help!

Solution

From the hint it is clear that we should form positive arrays which have elements in an ascending order. If there are K elements in an existing positive array then the next element should be \geq K + 1.

We can greedily assign each element of A (in the ascending order) to some already existing positive array if it can accommodate the current element (if A[i] \geq number of elements in the positive array + 1) or in the other case we need to create another positive array.

We can maintain the information about all the existing positive arrays by storing the minimum required element for each of them.

If the current element (A[i]) can be part of any of the existing positive arrays i.e. it is \geq the least among all the minimum required elements for the positive arrays then we can just update the minimum required element and there is no need to create another positive array. The least among all the minimum required elements can be easily obtained if we store all the minimum required elements in a priority queue and updating also becomes easy.

On the other hand, if the current element (A[i]) cannot become a part of any of the existing positive arrays then we create a new positive array with the current element (A[i]) being the first element in it i.e. add a new value (minimum requirement of 2) into the priority queue.

At the end of the iteration over A the size of the priority queue denotes the minimum number of positive arrays required i.e. our answer.

TIME COMPLEXITY:

O(NlogN) for each test case.

SOLUTION:

Setter's solution
using namespace std;

int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n + 1);
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			a[x]++;
		}
		int sum = 0, ans = 0;
		for (int i = 1; i <= n; i++) {
			sum += a[i];
			ans = max(ans, (sum + i - 1) / i);
		}
		cout << ans << '\n';
	}
	return 0;
}
Editorialist's Solution
using namespace std;

int main() {
	int T;
	cin >> T;
	while(T--){
	    int n;
	    cin >> n;
	    vector<int>v(n);
	    for(int i=0;i<n;i++)cin >> v[i];
	    sort(v.begin(),v.end());
	    priority_queue<int,vector<int>,greater<int>>pq;
	    pq.push(1);
	    for(int i=0;i<n;i++){
	        if(v[i]>=pq.top()){
	            pq.push(pq.top()+1);
	            pq.pop();
	        }
	        else{
	            pq.push(2);
	        }
	    }
	    cout << pq.size() << endl;
	}
	return 0;
}

If not already, Can you please consider providing solutions in other languages(java and python atleast)as well instead of only in C++

2 Likes

Can you please explain setters solution ? How it is solving in O(n) time? Yours was intuitive but I can" t understand logic behind 2nd solution.

5 Likes

My solution using multiset(consider as heaps only :slight_smile: )
https://www.codechef.com/viewsolution/69406704
a neat implementation and was very fast intuitive to me

2 Likes

How setter’s code formula works? I didn’t found intuitation here…somebody explain if the know :slight_smile:

4 Likes

The Idea behind setter’s solution is like this.
Since all elements are >= 1 and <= n. Store their frequencies. (Say Fre[i] stores the frequency of element i).
Iterate from i = 1 to n. Since for an array to be good, we need A[i] >= i, which means to put element i in a good array, that array should have at least size i (after you put this element in it). Now I’ll explain the code.

sum += Fre[i];  // sum = total number of elements <= i that we have
ans = max(ans, (sum + i - 1) / i);
// The second part "(sum + i - 1) / i" is basically ceiling devision of sum with i. 
// This division value says how many at least i-sized good arrays we need with
// i at its end.
5 Likes

My solution without any heap and set

void solve() {
	int n;
	cin >> n;
	int arr[n];
	for (int i = 0 ; i < n ; i++) cin >> arr[i];

	sort(arr, arr + n);
	vector<int> v;
	v.push_back(1);
	int cnt = 1;
	for (int i = 0 ; i < n; i++) {
		bool changed = false;
		for (auto &x : v) {
			if (arr[i] >= x) {
				x = x + 1;
				changed = true;
				break;
			}
		}
		if (!changed) {
			cnt++;
			v.push_back(2);
		}
	}

	cout << v.size() << "\n";
}
1 Like

Yes, Please Explain setter’s approach behind solition.

1 Like

This problem can also be solved using Binary Search.
We know the answer can be as minimum as 1 and as maximum as n.
We calculate the mid and validate whether this mid is our answer, by checking if we can accommodate all the elements in mid number of arrays (with satisfying the condition).

        bool ok = 1;
        map<int, int> mp;
        for (int i = 0; i < n; i++)
        {
            int a; cin>>a;
            mp[a]++;
        }

        for (int i = 1; i <= n; i++)
        {
            if (mp.find(i) == mp.end())
            {
                mp[i] = 0;
            }
        }
        int left = 1, right = n;
        while (left < right)
        {
            ok = 1;
            int mid = left + ((right - left) / 2);     
            int rem = 0;
            for (int i = 1; i <= n; i++)
            {
                if (mp[i] <= mid)      // if frequency of i is less than or equal to the 'mid' no. of arrays
                {
                    rem += (mid - mp[i]);
                }
                else
                {
                    if (mp[i] <= (rem + mid))   // else we check if we can accommodate this i in previous vacant positions
                    {
                        int temp = mp[i];
                        temp-=mid;
                        rem-=temp;
                    }
                    else        // if we can't, this 'mid' is not our answer and we need more number of arrays
                    {
                        ok = 0;
                        break;
                    }
                }
            }
            if (ok)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        print(left);
    
2 Likes

A solution using binary search
https://www.codechef.com/viewsolution/69403847

image
please help me to understand the logic briefly. sum means the number of element and i means index and then… ?

I was always placing the smallest element first in each positive array greedily.
For example: [1, 1, 2, 2, 2, 3] becomes [ [1], [1, 2], [2, 2, 3] ].
Why is this approach wrong? Can someone help me with some test cases, I can’t think of any.

I found one:
1 1 2 2

I did this too. For me this implementation was more intuitive.

please provide solution in java language also

@subhash_9523 - Java solutions here - Positive array Submissions | CodeChef

You can click on ‘submissions’ for any problem to view all the submissions.

can you please explain your approach ?

how are you checking that you can accommodate all the elements in mid number of arrays ?

can you please tell how are you checking that you can accommodate all the elements in mid number of arrays ?

I more or less just simulated what precisely the problem was said to do.
I will start creating arrays like I keep my pointer at 1(index) so I need an element greater than equal to 1, I search for such an element, and there can be two cases :
Case 1: element found
you erase this element, increase your pointer(index) by 1 and repeat unless case 2 occurs (caution this searching is just how many elements one array can accommodate according to the given conditions.
Case 2: element not found (means your multiset pointer points to the end)
this shows no more elements can be accommodated in the current array for the current pointer(index) value, you reset the pointer to the beginning(1 here) and increase your arrays count by 1.
This gives you the answer.

1 Like