TRAINPLN - Editorial

PROBLEM LINK:

Contest - Division 4
Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY

PREREQUISITES:

Greedy, Priority Queue

PROBLEM:

There are N training plans. Training plan i has effectiveness A_i, but requires that atleast B_i other training plans have been performed before selecting this plan.

If training plans p_1, p_2,\dots,p_k are performed, the score is equal to \frac{\sum A_{p_i}}{k}. Determine the maximum possible score attainable.

EXPLANATION:

We proceed greedily.

Let S represent the set of all (previously unselected) training plans that we can select currently. Initially, S consists of all plans i where B_i=0.
Also, let set K comprise all plans that we have selected. Initially, K is empty. Finally, let ans represent the maximum score we have attained so far. Initially, ans=0.

In each move, do the following:

  • select the plan in S with the largest effectiveness value; break if S is empty.
  • insert this plan into K and remove it from S.
  • update ans := \max(ans, \frac{\sum A_{K_i}}{|K|}).
  • insert all plans i with B_i=|K| to S.

It is easy to see why this works. We pick plans one by one (till we can select no more). By the greedy criteria, it is optimal to always select a selectable plan with the highest effectiveness value. Finally, we update the best answer with the current score.

TIME COMPLEXITY:

Since each training plan is inserted/removed from the priority queue atmost once, the time complexity is therefore

O(N\log N)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here.

Author's solution
To be added.
Tester's solution
// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
int arr[100005];
int brr[100005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		rep(x,0,n) cin>>arr[x];
		rep(x,0,n) cin>>brr[x];
		
		vector<int> idx;
		rep(x,0,n) idx.pub(x);
		sort(all(idx),[](int i,int j){
			return brr[i]>brr[j];
		});
		
		double ans=0;
		
		int tot=0;
		priority_queue<int> pq;
		rep(x,0,n){
			while (!idx.empty() && brr[idx.back()]==x){
				pq.push(arr[idx.back()]);
				idx.pob();
			}
			
			if (pq.empty()) break;
			
			tot+=pq.top();
			pq.pop();
			
			ans=max(ans,(double)tot/(x+1));
		}
		
		cout<<fixed<<setprecision(12)<<ans<<endl;
	}
}
3 Likes

what do you mean by insert all plan i with Bi = K ? Integer Bi = set K ? what this means ?

difficulty cakewalk/easy/mediam/hard what should we conclude from that ?

4 Likes

Can someone help me find out the test case which would fail for Solution: 61694023 | CodeChef or let me know the 3rd test case ?

1 Like

It simply indicates that the format in use isn’t updated with the actual difficulty level finalised for this problem. I can see the same difficulty status in some other editorials of this contest as well

I think this means insert all plan i with Bi = size of set(K), because set K contains values that are taken, so all values with Bi = |K| can now be a part a S.

can anyone explain me this question approach please???

My solution is passing sample testcase but while submitting it is giving segmentation error please help
link to code → Solution: 61697230 | CodeChef
I sorted elements plan requirement wise means by base on array B
then created map to store element which are valid and choose best element after it so I checked on all testcase but it is giving segmentation fault please help

Typo fixed. Thanks.

Can someone tell what is wrong in my code?? Submission Link

a = [ 18 9 -4 14 -7 ]
b = [ 2 3 0 3 0 ]
Expected 6.00000000
Found 5.2500000000

1 Like

Hey, thanks a lot man @ps47 , appreciate it.

#pragma GCC optimize(“Ofast”)

#pragma GCC target(“sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma”)

#pragma GCC optimize(“unroll-loops”)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector vi;

ll MOD = 998244353;

double eps = 1e-12;

#define forq(i,e) for(ll i = 0; i < e; i++)

#define fors(i,s,e) for(ll i = s; i < e; i++)

#define rforn(i,s) for(ll i = s; i >= 0; i–)

#define rforsn(i,s,e) for(ll i = s; i >= e; i–)

#define ln “\n”

#define dbg(x) cout<<#x<<" = "<<x<<ln

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define INF 2e18

#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

#define all(x) (x).begin(), (x).end()

#define sz(x) ((ll)(x).size())

#define MXE(a) *max_element(all(a))

#define MNE(a) *min_element(all(a))

#define sort1(a) sort(all(a))

#define rev(a) reverse(all(a))

#define revsort(a) sort(all(a),greater<>())

//bitset section*****

#define cset(x) __builtin_popcountll(x)

#define pairty(x) __builtin_parityll(x)

#define lz(x) __builtin_clzll(x)

#define tz(x) __builtin_ctzll(x)

int main()

{

fast_cin();

ll t;

cin>>t;

while(t–){

double ans=0.0;

ll n;cin>>n;

priority_queueq;

vector<pair<ll,ll>>a(n);

forq(i,n){

  cin>>a[i].second;

}

forq(i,n){

  cin>>a[i].first;

}

sort1(a);

double training=0;

double queue_size=0;

double total_sum=0;

forq(i,n){

  if(a[i].first>training){

      ll rr=a[i].first-training;

    if(queue_size>=rr){

        while(rr--){

        queue_size--;

        training++;

        total_sum+=q.top();

        q.pop();

        }

         ll pp=a[i].first;

  while(a[i].first==pp&&i<n){

      q.push(a[i].second);

      queue_size++;

  i++;

  }

    total_sum+=q.top();

 i--;

 q.pop();

queue_size--;

training++;

      if(ans<(total_sum/training))ans=total_sum/training;

    }

    else

      break;

}

else{

  ll pp=a[i].first;

  while(a[i].first==pp&&i<n){

      q.push(a[i].second);

      queue_size++;

  i++;

  }

 total_sum+=q.top();

 i--;

 q.pop();

queue_size--;

training++;

if(ans<(total_sum/training))ans=total_sum/training;

}

}

while(queue_size–){

total_sum+=q.top();

training++;

q.pop();

if(ans<(total_sum/training))ans=total_sum/training;

}

cout << fixed << setprecision(6) << ans

     << endl;

}

return 0;

}

i used the same logic i used priority queue can you tell me what is the counter case

for people who are looking for a more readable code:-

#include "bits/stdc++.h"
#define ll long long int
#define MOD 1000000007
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
       vector<pair<ll,ll>> arr(n);
       for(ll i=0;i<n;i++)
           cin>>arr[i].first;
       
       for(ll i=0;i<n;i++)
           cin>>arr[i].second;

    // for keeping track of tasks with prerequisite i
    // tasks_pre[i] will represent all tasks with prerequisites i
      vector<vector<ll>> tasks_pre(n+1);
      for(ll i=0;i<n;i++)
      {
          ll x=arr[i].first;
          ll y=arr[i].second;
          tasks_pre[y].push_back(x);
      }

      long double ans=0.0, sum=0;
      priority_queue<ll> best;
      for(ll i=0;i<n;i++){
          for(auto x:tasks_pre[i])
          {
            best.push(x);
          }

          if(best.empty())
          break;
          sum+=best.top();
          best.pop();
          ans =max(ans,sum/(long double)(i+1));

      }       
      cout<<fixed<<setprecision(6)<<ans<<endl;

    }
    return 0;
}
1 Like

can you please tell why we need to break when our heap is empty?
what will be the problem if heap is empty?
and when will that case arise?
if we are already sure that loop will run only n times, doesn’t it already implies that we will apply push operation to heap n times and pop is also applied n times?

  1. The heap contains all values we can select currently, if it is empty - we cannot take any more values, hence we break.
  2. The problem with an empty heap is that now we cannot add any more elements to set K, and as the heap updates only when we add more elements to K (point 4 in editorial’s algorithm), this also suggests the heap will never have any more elements in future, so we just have to stop picking.
  3. We are sure the loop runs “at max” n times, but just by simple observation, if at any time heap becomes empty, there is no point continuing.

thanks for such a clear explanation

Hey @ghost331 :wave:
I think in your code there might be missing the case of all element being 0 in array of b.