DIVTHREE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Smit Mandavia
Tester: Radoslav Dimitrov
Editorialist: Akash Bhalotia

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given the number of problems set, and the number of problems required to host a contest, find the maximum number of contests that can be hosted in D days if there can be at most one contest per day.

EXPLANATION

show

We are given the number of problems set by each of the N setters. We are given the number of problems required to host a contest, K. We need to find the maximum number of contests that can be hosted in D days, if we can host at most one contest per day.

The first observation that we can make is that since there are D days and at most one contest can be hosted per day, the number of contests that can be hosted is at most D.

Each contest requires exactly K problems. So, if we have X problems, we can host at most \lfloor \frac{X}{K} \rfloor contests. The actual distribution of problems doesn’t matter. Nor does the number of problems set by any individual setter. We only need the total number of problems.

(Note: \lfloor \frac{X}{K} \rfloor means the floor value of the division of X by K. In other words, it means rounding down the value that we get on dividing X by K to the nearest integer).

So we see that the maximum number of contests that can be hosted has two limitations: the number of days, D, and the number of contests that can be made out of the problems, \lfloor \frac{X}{K} \rfloor. The answer is the minimum of these two quantities.

Thus, in order to solve the problem, we add up the number of problems set by each individual setter. Let’s call this sum X. Then we find the minimum of \lfloor \frac{X}{K} \rfloor and D.

TIME COMPLEXITY:

show

The time complexity is: O(N) per test case.

Why?

Adding the number of problems to obtain their sum takes O(N) time. Finding the minimum of D and \lfloor \frac{X}{K} \rfloor takes O(1) time. Thus, the time complexity is O(N).


SOLUTIONS:

Setter
#include<bits/stdc++.h>
using namespace std;
 
int main() {
	int t, n, k, p, total_problems, contests;
	cin >> t;
	while (t--) {
	    cin >> n >> k >> p;
	    int a[n];
	    total_problems = 0;
	    for (int i = 0; i < n; i++) {
	        cin >> a[i];
	        total_problems += a[i]; // Counting total number of problems availale
	    }
	    contests = total_problems / k; // total contests Chef can prepare this month
	    contests = min(contests, p); // Chef cannot host more than p contests this month
	    cout << contests << "\n";
	}
	return 0;
}
Tester
#include <bits/stdc++.h>
#define endl '\n'
 
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
 
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
 
int n, k, p;
int a[MAXN];
 
void read() {
	cin >> n >> k >> p;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
}
 
void solve() {
	int s = 0;
	for(int i = 0; i < n; i++) {
		s += a[i];
	}
 
	cout << min(p, s / k) << endl;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int T;
	cin >> T;
	while(T--) {
		read();
		solve();
	}
 
	return 0;
}
Editorialist
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
	public static void main(String[] args) throws Exception
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

		int i,N;

		int T=Integer.parseInt(br.readLine().trim());
		StringBuilder sb=new StringBuilder();

		while (T-->0)
		{
			String[] s=br.readLine().trim().split(" ");
			N=Integer.parseInt(s[0]);
			int K=Integer.parseInt(s[1]);
			int D=Integer.parseInt(s[2]);

			s=br.readLine().trim().split(" ");
			int[] a=new int[N];
			for(i=0;i<N;i++) a[i]=Integer.parseInt(s[i]);

			//Total number of problems
			int sum=0; for(int x:a) sum+=x;

			//Bounded by the minimum of the number of days
			//and the number of contests possible with the
			//total number of problems.
			sb.append(Math.min(sum/K,D)).append("\n");
		}
		System.out.println(sb);
	}
}

VIDEO EDITORIAL:

Feel free to share your approach if it differs. You can ask your doubts below.