beginner_610's blog

By beginner_610, history, 5 months 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 months 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).

»
5 months 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).

»
5 months 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).

»
5 months ago, # |
  Vote: I like it +12 Vote: I do not like it

You can check here, some points may be useful.

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

    No , like from where to start?

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

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

      • »
        »
        »
        »
        4 months 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.

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

          Bro can you try to code it and run the given testcases, i wasnt able to code it.

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

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

»
4 months 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.

  • »
    »
    4 months 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

»
4 weeks 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;
}
  • »
    »
    8 days 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?

»
8 days 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