beginner_610's blog

Stuck in a problem.
By beginner_610, history, 5 years ago, In English

This problem was asked in online round to my friend.I am not able to get how to approach the problem using which technique, if someone could help me?, Thanks.

Problem:

****Alice has decided to publish X different comic books.****

****For this Purpose , He has Y printing machines and Z binding machines.****

****The ith printing machine takes print[i] minutes to print all pages of a comic book. Each binding machine takes K minutes to bind all the pages of a comic book.**

****At a single point of time ,each machine(a printing or a binding) can process at most the pages of a single comic book.**

****For publishing comic books , these steps have to be followed.**

****1. An unoccupied printing machine i starts printing the pages of a comic book.**

****2. After print[i] minutes , the printed pages are taken out of the ith printing machine.**

****3. After non-negative amount of time , the printed pages of comic book are placed in an unoccupied binding machine.**

****4. After K minutes, the pages are taken out of the binding machine.**

****Assume that the time is negligible for placing the pages into or removing from the machines.**

****You need to help alice , find out the minimum time in order to publish X comics.**

Input:

1.first line consists of the no of testcases.

2.Second line consists of X,Y,Z,K.

3.Y space separted integers which denote the printing time print[i] of ith printing machine.

OUTPUT:

For each test case , print the minimum time to publish all X comics. Constraints:

1<=t<=10

1<=X<=10^6

1<=Y<=10^5

1<=Z<=10^9

1<=K<=10^9

1<=print[i]<=10^9

Sample Test Cases:

input:

3

2 1 1 34

1100

2 3 2 10

10 16 1

3 2 2 5

5 7

output:

2234

12

15

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by beginner_610 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by beginner_610 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by beginner_610 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

You can check here, some points may be useful.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No , like from where to start?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      is it to be done with dp , or some binary search

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        From reading it looks like binary search, has a role to play. Sort the print[i] array then apply binary search. This will give us the minimum time for printing comics, but it will not include the binding time.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can anyone help please? , or its just for people with higher ratings?

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is just a weird variation of IOI Job Processing. Maybe looking at that sol will help you.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sir , can you help me with its code? , i wasnt able to code it and the given test cases didnt work

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Hey I recently came across this question and implemented a solution with time complexity O(xLog(x)+yLog(y)+zLog(z)) so basically the time complexity is nLog(n) where n = max(x,y,z); Ideone Solution Link Feel Free to comment in case you have any doubt.

#include <bits/stdc++.h>
using namespace std;
int main() {
	int test;
	cin>>test;
	while(test--)
	{
		int x,y,z,k,i;
		cin>>x>>y>>z>>k;
		vector<int>vec(y);
		vector<int>printed;
		for(int i=0;i<y;++i)
		cin>>vec[i];
		sort(vec.begin(),vec.end());
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
		int currtime = 0;
		i=0;
		int j=0;
		while(i<x)
		{
			if(pq.empty())
			{
			pq.push(make_pair(vec[j],j));
			++j;
			++i;
			}
			else
			{
				if(j<y && pq.top().first>vec[j])
				{
					pq.push(make_pair(vec[j],j));
					++j;
					++i;
				}
				else
				{
					int currtime=pq.top().first;
					int currmachine=pq.top().second;
					printed.push_back(currtime);
					pq.pop();
					pq.push(make_pair(currtime+vec[currmachine],currmachine));
					++i;
				}
			}
		}
		while(!pq.empty())
		{
			printed.push_back(pq.top().first);
			pq.pop();
		}
		i=0;
		vector<int>finalvec;
		for(i=0;i<min((int)printed.size(),z);++i)
			pq.push(make_pair(printed[i]+k,1));
		while(i<printed.size())
		{
			finalvec.push_back(pq.top().first);
			currtime = max(pq.top().first,printed[i]);
			pq.pop();
			pq.push(make_pair(currtime+k,1));
			++i;
		}
		while(!pq.empty())
		{
			finalvec.push_back(pq.top().first);
			pq.pop();
		}
		cout<<"answer is "<<finalvec[finalvec.size()-1]<<endl;
	}
	return 0;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bro can you explain a bit , what your pq, printed and finalvec are storing?

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code is not correct. 

    1
2 2 2 1
2 3

    Answer should be 4, but this code outputs 5.

    				if(j<y && pq.top().first>vec[j])
				{
					pq.push(make_pair(vec[j],j));
					++j;
					++i;
				}

    Here is the mistake. If you selected 2, then instead of selecting 3 it will select 2.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      This gives the correct answer.

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

#define ll long long int
long minTime(vector<ll> machines, ll goal) {
    
    ll s=1;
    ll e=machines[0]*goal;
    while(s<e)
    {
        ll m=s+(e-s)/2;
        ll temp=0;
        for(auto &xx : machines)
        {
            temp+=(m/xx);
            if(temp>=goal) break;
        }
        if(temp>=goal)
        {
            e=m;
        }
        else{
            s=m+1;
        }        
    }
    
    return e;

}

int main() {
	int test;
	cin>>test;
	while(test--)
	{
		ll x,y,z,k,i;
		cin>>x>>y>>z>>k;
		vector<ll>vec(y);
		ll currtime = 0;
		vector<ll>printed;
		for(int i=0;i<y;++i)
		cin>>vec[i];
		sort(vec.begin(),vec.end());
		
		ll mnTime=minTime(vec,x);
		for(auto xx : vec)
		{
			ll temp=xx;
			while(temp<=mnTime)
			{
				printed.push_back(temp);
				temp+=xx;
			}
		}
		sort(printed.begin(),printed.end());
		i=0;
		
		vector<ll> ans;
		priority_queue<ll,vector<ll> ,greater<ll> > pq;
		for(i=0;i<min(x,z);i++)
		{
			pq.push(printed[i]+k);
		}
		while(i<printed.size())
		{
			ans.push_back(pq.top());
			currtime = max(pq.top(),printed[i]);
			pq.pop();
			pq.push(currtime+k);
			i++;
		}
		while(!pq.empty())
		{
			ans.push_back(pq.top());
			pq.pop();
		}
		cout<<ans.back()<<endl;
	}
	return 0;
}
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can check my code in the below comment. It is much simpler and intuitive.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Imagine if the question was to calculate if it's possible to publish X books in a given time t, this can be solved by considering all printing machines and binding machines. Now you just have to binary search for the time t

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This question can be solved greedily. - In a set(multiset to be specific), the printing finish time will be stored for each printing machine. Initially, all printing machines will be available so if we take any machine its ending time will be the time it takes to print a book. Suppose we take 1st machine with time 5, then if we take it next time its task will end at 10. So, we will replace the finishing time for 1st machine to be 10. - Similar logic is used for binding machine's job.

Here is my code.

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

using ll = long long int;

void solve() {
	int x, y, z, k;
	cin >> x >> y >> z >> k;
	multiset<pair<ll,ll>> print;
	for(int i=0, t; i<y; i++) {
		cin >> t;
		print.insert({t, t});
	}
	multiset<ll> bound;
	for(int i=0; i<min(x, z); i++)
		bound.insert(0);
	ll ans, cur, t;
	for(int i=0; i<x; i++) {
		cur = print.begin()->first;
		t = print.begin()->second;
		print.erase(print.begin());
		print.insert({cur+t, t});
		ans = max(cur, *bound.begin())+k;
		bound.erase(bound.begin());
		bound.insert(ans);
	}
	cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int _t; cin >> _t; while(_t--)
    solve();
}
→ Reply