PROBLEM LINK:
Setter: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
For the chef’s exam, there are M subjects and N topics. The i^{th} topic belongs to {C_i}^{th} subject and takes T_i hours to complete. There is K hours time in the test. We need to find the maximum marks possible for the chef to score in this exam if the score is calculated as follows: \lceil \frac{x_1}{2} \rceil + \lceil \frac{x_2}{2} \rceil + \dots + \lceil \frac{x_M}{2} \rceil if x_1 topics are chosen from subject 1, x_2 topics are chosen from subject 2, \dots x_M topics are chosen from subject M.
In this problem, \lceil . \rceil denotes the ceil function.
QUICK EXPLANATION:
-
This problem can be solved constructively. Initially we are are at state x_1=0, x_2=0, \dots x_M=0 and for each state we try to increase score by 1 to go to another state until the total time doesn’t exceed K.
-
Suppose we are at some state with values x_1, x_2, \dots x_M. In order to increase score by 1, we need to add topics for the subject with minimum cost where cost_i is defined as follows:
-
If x_i =0, cost_i is defined as minimum time required to increase the number of topics of subject i by 1. Else x_i must always be odd and cost_i is defined here as the minimum time to increase the number of topics of subject i by 2.
-
We can proceed in this manner by utilizing a min heap to get the index i with minimum cost at each stage and keep on incrementing scores until there are no possible topics left we can add for a particular subject in order to increase the score by 1.
EXPLANATION:
The first observation we need is that if we select x_i topics from the i^{th} subject, to minimize time, we obviously need to select the first x_i values of the topics of subject i when they are sorted in ascending order by time.
The second observation is that x_i is either 0 or an odd number in the optimal answer.
Proof
Suppose there is some x_i \gt 0 and is even. From the properties of ceil function, we know that, \lceil \frac{x_i}{2} \rceil = \lceil \frac{x_i-1}{2} \rceil as x_i is even. Thus, removing an extra topic doesn’t effect the score but will infact benefit us since we are lowering the time required for this same score. Therefore, we can always remove a topic and make x_i odd in this case.
Let us solve this problem constructively. Suppose we are at some state where already x_1, x_2, x_3, \dots x_M topics are selected from the corresponding subjects respectively. Now say we want to increase the total score further by 1. The main question under consideration is how can we go about it?
The main idea is that we calculate the minimum time cost_i needed to increase the score by 1 if we add topics from subject i for each 1 \leq i \leq M. Now we need to add topics to that subject which has value min(cost_1, cost_2, \dots cost_M) in order to increase the score by 1.
If we know how to calculate cost_i, our job is done since at every stage we can put cost_1, cost_2 \dots cost_M in a min heap and pop the items and perform the updates accordingly. (more details in code). This procedure is done as long as we do not cross the total time K.
Let us now calculate cost_i. Already x_i topics from this subject are selected and we want to increase the score by 1 by adding some more topics with minimum extra time added. This can be solved in two cases depending on x_i =0 or an odd number.
-
Case 1: \hspace{1 mm} x_i =0
In this case, we can simply add one topic belonging to subject i with minimum time in order to increase the score by 1. Therefore, cost_i is the minimum time needed to increase the number of topics of subject i by 1. -
Case 2: \hspace{1 mm} x_i is odd.
In this case, we need to add atleast two topics belonging to subject i in order to increase the score by 1. This is because of the property of ceil function, \lceil \frac{x_i}{2} \rceil = \lceil \frac{x_i+1}{2} \rceil when x_i is odd. Therefore, cost_i is the minimum time needed to increase the number of topics of subject i by 2.
Knowing all this, we initially start with the state x_1=0, x_2=0, \dots x_M=0 and slowly increase the score by 1 by choosing subjects and the topics inside them accordingly. We can use a min heap to keep track of our states at each stage.
TIME COMPLEXITY:
O(N \cdot (\log N + \log M)) for each testcase.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tests;
cin >> tests;
while (tests--)
{
int n, m, k;
cin >> n >> m >> k;
vector<int> c(n + 1);
vector<int> t(n + 1);
vector<vector<int>> subject(m + 1);
for (int i = 1; i <= n; i++)
cin >> c[i];
for (int i = 1; i <= n; i++)
cin >> t[i];
for (int i = 1; i <= n; i++)
subject[c[i]].push_back(t[i]);
for (int i = 1; i <= m; i++)
sort(subject[i].begin(), subject[i].end());
//simulates min heap
set<pair<int, pair<int, int>>> min_heap;
for (int i = 1; i <= m; i++)
{
if (!subject[i].empty())
{
int x = 1;
int cost = subject[i][0];
min_heap.insert({cost, {x, i}});
}
}
int score = 0, time = 0;
while (!min_heap.empty())
{
pair<int, pair<int, int>> p = *min_heap.begin();
int cost = p.first, x = p.second.first, ind = p.second.second;
min_heap.erase(min_heap.begin());
if (cost > k - time)
break;
time += cost;
score++;
if (x + 1 < (int)subject[ind].size())
{
int cost1 = subject[ind][x] + subject[ind][x + 1];
min_heap.insert({cost1, {x + 2, ind}});
}
}
cout << score << endl;
}
}
Setter's solution
#include<bits/stdc++.h>
using namespace std;
template <class T> ostream &operator << (ostream &os, const vector<T> &p) { os << "["; for (auto&it : p) os << it << " "; return os << "]";}
template <class S, class T> ostream &operator << (ostream &os, const pair<S, T> &p) { return os << "(" << p.first << "," << p.second << ")";}
#ifndef ONLINE_JUDGE
#define deb(...) dbs(#__VA_ARGS__,__VA_ARGS__)
template <class T> void dbs(string str, T t) { cerr << str << ":" << t << "\n";}
template<class T, class...S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << ":" << t << ","; dbs(str.substr(idx + 1), s...);}
#else
#define deb(...){}
#endif
#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
const int INF = 1e18;
const int N = 1e5; // check the limits
clock_t start = clock();
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;
}
// deb(l, r, x);
assert(l <= x && x <= r);
return x;
} else {
assert(false);
}
}
}
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');
}
template<typename T> using MPQ = priority_queue<T, vector<T>, greater<T>>;
int n, m, k, type[N], t[N];
vector<int> v[N];
void solve(int tc) {
n = readIntSp(1, 100000);
m = readIntSp(1, n), k = readIntLn(1, 1000000000);
rep(i, n) {
if (i < n - 1) type[i] = readIntSp(1, m);
else type[i] = readIntLn(1, m);
type[i]--;
}
rep(i, n) {
if (i < n - 1) t[i] = readIntSp(1, 1e9);
else t[i] = readIntLn(1, 1e9);
}
rep(i, m) v[i].clear();
rep(i, n) {
v[type[i]].push_back(t[i]);
}
rep(i, m) {
sort(v[i].begin(), v[i].end());
}
MPQ<int> q;
rep(i, m) {
if (v[i].size() > 0) {
q.push(v[i][0]);
for (int j = 1; j + 1 < v[i].size(); j += 2) {
q.push(v[i][j] + v[i][j + 1]);
}
}
}
int ans = 0;
while (!q.empty()) {
int x = q.top();
q.pop();
if (x > k) break;
k -= x;
ans++;
}
cout << ans << '\n';
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #ifndef ONLINE_JUDGE
// freopen("ip2.txt", "r", stdin);
// freopen("out2.txt", "w", stdout);
// #endif
int t = readIntLn(1, 10000);
// deb(t);
for (int i = 1; i <= t; i++) solve(i);
cerr << fixed << setprecision(10);
cerr << "Time taken = " << (clock() - start) / ((double)CLOCKS_PER_SEC) << " s\n";
return 0;
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n, m, k;
cin>>n>>m>>k;
vector<int> a[m + 1];
int c[n], q[n];
for(int i = 0; i < n; i++){
cin>>c[i];
}
for(int i = 0; i < n; i++){
cin>>q[i];
}
for(int i = 0; i < n; i++){
a[c[i]].push_back(q[i]);
}
vector<int> v;
for(int i = 1; i < m + 1; i++){
sort(a[i].begin(), a[i].end());
if(a[i].size()){
v.push_back(a[i][0]);
for(int j = 1; j < a[i].size(); j++){
if(j + 1 != a[i].size()){
v.push_back(a[i][j] + a[i][j + 1]);
}
j++;
}
}
}
sort(v.begin(), v.end());
int ans = 0;
for(int i = 0; i < v.size(); i++){
if(k >= v[i]){
k -= v[i];
ans++;
}
}
cout<<ans<<"\n";
}
return 0;
}
Please comment below if you have any questions, alternate solutions, or suggestions.