TASKTIME - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

EASY

PREREQUISITES:

Ceil function, Heaps

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

8 Likes
#include <bits/stdc++.h>
#define all(c) (c).begin(), (c).end()
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c),x) != (c).end())
#define fi first
#define se second
#define print(arr) for(int num : (arr)) cout << num << ' '; cout << '\n';
#define read(arr) for(int &i : (arr)) cin >> i;
using namespace std;


int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);
    int t; cin >> t;
    while(t--){
        int n, m, k; cin >> n >> m >> k;
        vector<int> c(n);
        vector<int> t(n);
        read(c);
        read(t);
        map<int,vector<int>> maper;
        for(int i=0;i<n;++i){
            int key = c[i];
            int val = t[i];
            maper[key].push_back(val);
        }
        for(auto p : maper){
            sort(p.second.begin(), p.second.end());
        }
        vector<int> temp;
        for(pair<int, vector<int>> p : maper){
            vector<int> nums = p.second;
            temp.push_back(nums[0]);
            for(int i=2;i<nums.size();i+=2) temp.push_back(nums[i]+nums[i-1]);
        }
        sort(all(temp));
        int val = 0;
        int count = 0;
        for(int i=0;i<temp.size();++i){
            if(val + temp[i] <= k){
                val += temp[i];
                count++;
            }
        }
        cout << count << '\n';
    }
    return 0;
}

Can someone point me where I might be going wrong. My algo:

  1. sort each time taken for each subject topics.
  2. then calculate the time taken to consume odd numbers of the topics from a subject.
  3. sort these values and pick the topics till you are within the permissible value of k
1 Like

//i think this is right

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector;
using vvb = vector;
using vi = vector;
using vvi = vector;
using vl = vector;
using vvl = vector;
using vc = vector;
using vvc = vector;
using vs = vector;
#define fo(i,k,n) for(ll i=k;i<n;i++)
#define Fo(i,k,n) for(ll i=k;i>n;i-=1)
const ll mod = 998244353,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
fast;
#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
#endif
}

void solve(){

ll n,m,k;
cin>>n>>m>>k;
ll c[n],t[n];
for(ll i=0;i<n;i++)
cin>>c[i];
for(ll i=0;i<n;i++)
cin>>t[i];
vector< pair <ll,ll> > s;
for(ll i=0;i<n;i++)
{
s.pb({t[i],c[i]});
}
sort(s.begin(),s.end());
ll ans[n+1]={0};
for (ll i=0;i<n;i++) {

   ll index=s[i].second;
   ll time=s[i].first;
    if(k-time>=0&&(ans[index]%2==0||(s[i+2].second==s[i].second&&i<n-2))){
    ans[index]++;
    k-=time;
    }

}

ll res=0;
for(ll i=1;i<=n;i++){
// cout<<ans[i]<<" “;
if(ans[i]%2!=0)
ans[i]++;
res+=ans[i]/2;
}
cout<<res<<”\n";

}

int main(){
ll tn;
cin>>tn;
while (tn–)
{
solve();
}

}

I think calculating time to consume odd number of topics may not always give the maximum value.

take long int instead of int

pls provide at least one code solution in java also not all three in c++ :pray:

Can someone have a look on my submission and give me a test case where it fails.
Link

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define MP make_pair

#define PB push_back

#define MOD 1000000007

#define fi first

#define se second

typedef pair<int, int> PII;

typedef vector VI;

typedef vector VPII;

typedef vector VVI;

typedef map<int, int> MPII;

typedef set SETI;

typedef multiset MSETI;

int32_t main()

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

#ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

#endif

int t;

cin >> t;

while (t--)

{

    int n, m, k;

    cin >> n >> m >> k;

    vector<multiset<int>> vm(m + 1);

    vector<pair<int, int>> vp(n);

    for (int i = 0; i < n; i++)

    {

        int temp;

        cin >> temp;

        vp[i].first = temp;

    }

    for (int i = 0; i < n; i++)

    {

        int temp;

        cin >> temp;

        vp[i].second = temp;

    }

    for (auto x : vp)

    {

        vm[x.first].insert(x.second);

    }

    vector<pair<int, int>> vpp;

    unordered_map<int, int> mp;

    int p = 0;

    int temp = 0;

    for (int i = 1; i <= m; i++)

    {

        int cnt = 0;

        for (auto y : vm[i])

        {

            cnt++;

            if (cnt == 1)

            {

                vpp.push_back({y, i});

                continue;

            }

            temp += y;

            p++;

            if (p == 2)

            {

                vpp.push_back({temp, i});

                p = 0;

                temp = 0;

            }

        }

    }

    sort(vpp.begin(), vpp.end());

    for (auto x : vpp)

    {

        


        if (x.first <= k)

        {

            mp[x.second]++;

            k = k - x.first;

            // cout<<x.second<<" ";

        }

        else

            break;

    }

    int ans = 0;

    for (auto x : mp)

    {

        cout<<x.second<<" ";

        ans += x.second;

    }

    cout << ans << endl;

}

return 0;

}

what’s Wrong i this solution ?
can someone tell me?

@qwerty29 your solution logic is similar to tester’s solution but tester implemented using array of vectors while you implemented using a map.

The vectors in the map cannot be sorted it seems.
Try compiling the following code (I have added just a few print statements and comment lines):

#include <bits/stdc++.h>
#define all(c) (c).begin(), (c).end()
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c),x) != (c).end())
#define fi first
#define se second
#define print(arr) for(int num : (arr)) cout << num << ’ '; cout << ‘\n’;
#define read(arr) for(int &i : (arr)) cin >> i;
using namespace std;

int main(){
ios::sync_with_stdio(false); cin.tie(NULL);
int t; cin >> t;
while(t–){
int n, m, k; cin >> n >> m >> k;
vector c(n);
vector t(n);
read(c);
read(t);
map<int,vector> maper;
for(int i=0;i<n;++i){
int key = c[i];
int val = t[i];
maper[key].push_back(val);
}
for(auto p : maper){
sort(p.second.begin(), p.second.end());
cout<<p.first<<": “;
for(int i=0;i<p.second.size();i++){ //displays sorted vector here
cout<<p.second[i]<<” “;
}
cout<<”\n";
}
for(auto p : maper){
cout<<p.first<<": “;
for(int i=0;i<p.second.size();i++){ //vectors no longer seem to be sorted
cout<<p.second[i]<<” “;
}
cout<<”\n";
}

    vector<int> temp;
    for(auto p : maper){
        temp.push_back(p.second[0]);
        for(int i=2;i<p.second.size();i+=2) temp.push_back(p.second[i]+p.second[i-1]);
    }
    
    sort(all(temp));
    int val = 0;
    int count = 0;
    for(int i=0;i<temp.size();++i){
        if((val + temp[i] )<= k){
            val += temp[i];
            count++;
        }
    }
    cout << count << '\n';
}
return 0;

}

1
4 2 3
1 1 1 2
1 1 3 2

correct answer is 2.

bro can you provide more test cases please

can somebody provide good test cases…all my test cases are giving right answer but submission is giving WA.
please provide some good test cases