IPC Trainers CodeChef Solution

Problem -IPC Trainers CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

IPC Trainers CodeChef Solution in C++17

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

class comp
{
public:
    bool operator()(pair<int,int>& a, pair<int,int>& b){
    if(a.second == b.second) return a.first > b.first;
    return a.second > b.second;
    }
};


void solve(){
    
    int n,d; cin>>n>>d;
    //di t s
    
    //priority_queue<pair<int,int>,vector<pair<int,int>>,comp> pq;
    multiset<pair<int,int>,greater<pair<int,int>> > pq;
    //vector<pair<int,int>> v(d+1,{-1,-1});
    map<int,vector<pair<int,int>>> mp;
    for(int i=0; i<n; i++){
        int di,t,s; cin>>di>>t>>s;
        mp[di].push_back({s,t});
    }
    
    long long sum = 0;
    
    for(int i=1; i<=d; i++){
        if(mp.count(i) > 0){
            //pq.insert(v[i]);
            for(int j=0; j<mp[i].size(); j++){
                pq.insert(mp[i][j]);
            }
        }
        if(!pq.empty()){
            pair<int,int> node = *pq.begin(); pq.erase(pq.begin());
            node.second--;
            if(node.second > 0){
                pq.insert(node);
            }
        }
    }
    
    while(!pq.empty()){
        pair<int,int> node = *pq.begin(); pq.erase(pq.begin());
        sum += ((long long)node.first * (long long)node.second);
    }
    cout<<sum<<"\n";
    
}



int main(){
    int t; cin>>t;
    while(t--){
        solve();
    }
}

IPC Trainers CodeChef Solution in C++14

#include<bits/stdc++.h>

using namespace std;



// During the Indian Programming Camp (IPC), there are N trainers. The camp runs for D days. Each day, there can be at most one lecture. The i-th trainer arrives on day Di and then stays till the end of the camp. He also wants to teach exactly Ti lectures. For each lecture that a trainer was not able to teach, he will feel sad and his sadness level will be increased by Si.

// You are the main organizer of the contest. You want to find minimum total sadness of the trainers.

// Input
// The first line of the input contains an integer T, denoting the number of testcases.

// For each test case, the first line contains two space separated integers, N, D.

// The i-th of the next N lines will contain three space separated integers: Di, Ti, Si respectively.

// Output
// For each test case, output a single integer corresponding to the minimum total sadness of the trainers achievable.

// Constraints
// 1 ≤ T ≤ 10
// 1 ≤ N, D ≤ 105
// 1 ≤ Di, Ti ≤ D
// 1 ≤ Si ≤ 105


#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e18
#define nline "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()


typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
#define fori(i,s,n) for (int i = s; i <n; ++i)
#define ford(i,n,e) for (int i = n; i >=e ; i--)


void print(priority_queue<pair<ll,ll>>pq)
{

	while(!pq.empty())
	{
		pair<ll,ll>p=pq.top();

		cout<<p.first<<" "<<p.second;
		pq.pop();
	}
}

void solve()
{
	ll n,d;
	cin>>n>>d;

	map<ll,vector<pair<ll,ll>>>m;


	for (int i = 0; i <n; ++i)
	{
		ll x,y,z;
		cin>>x>>y>>z;
		m[x].pb({z,y});
	}


debug(m)
	priority_queue<pair<ll,ll>>pq;


	

// debug(m)
	
	for (int i =1; i <=d; ++i)
	{
		for (int j = 0; j<m[i].size(); ++j)
		{
			pq.push(m[i][j]);

		}

         // print(pq);

		if(!pq.empty())
		{
			pair<ll,ll>p=pq.top();

			pq.pop();
			p.second--;
			if(p.second!=0)
			{
				pq.push({p.first,p.second});
			}
			
		}
	}


	ll ans=0;


	while(!pq.empty())
	{
		pair<ll,ll>p=pq.top();
		
		ans+=p.first*p.second;
		pq.pop();
	}

	cout<<ans<<endl;

}


int main() {
#ifndef ONLINE_JUDGE
	freopen("Error.txt", "w", stderr);
#endif

	int t;cin>>t;
	while(t--){

		solve();
	}
}

IPC Trainers CodeChef Solution in PYTH 3

# cook your dish here
from heapq import heappush,heappop
def solve():
    n,D=map(int,input().split())
    data={}
    heap=[]
    for i in range(n):
        d,t,s=map(int,input().split())
        if d in data:
            data[d].append([t,s])
        else:
            data[d]=[[t,s]]
    for d in range(1,D+1):
        if d in data:
            for v in data[d]:
                heappush(heap,[-1*v[1],v[0]])
        if len(heap):
            x=heappop(heap)
            x[1]-=1
            if x[1]:
                heappush(heap,x)
    ans=0
    while len(heap):
        x=heappop(heap)
        ans+=-1*x[0]*x[1]
    return ans
for _ in range(int(input())):
    print(solve())

IPC Trainers CodeChef Solution in C

#include <stdio.h>
#define max 100009 
#define lli long long int

typedef struct 
{
    lli d,t,s;
}TRAINER;

//Merge function
void merge(TRAINER A[], lli p, lli q, lli r)
{
    lli i, j, k;
    lli n1 = q - p + 1;
    lli n2 = r - q;
 
    TRAINER L[n1], R[n2];

    for (i = 0; i < n1; i++)
    {
        L[i] = A[p + i];
    }
    for (j = 0; j < n2; j++)
    {
       R[j] = A[q + 1 + j];
    }
    
    i = 0; 
    j = 0;
    k = p;
    while ((i < n1) && (j < n2))
    {
        if (L[i].d <= R[j].d)
        {
            A[k] = L[i];
            i++;
        }
        else
        {
            A[k] = R[j];
            j++;
        }
        k++;
    }
    
    while (i < n1) 
    {
        A[k] = L[i];
        i++;
        k++;
    }
    while (j < n2)
    {
        A[k] = R[j];
        j++;
        k++;
    }
}

//mergesort
void mergeSort(TRAINER A[], lli p, lli r)
{
    if (p<r) {
        lli q = p + (r - p) / 2;
 
        mergeSort(A, p, q);
        mergeSort(A, q + 1, r);
 
        merge(A, p, q, r);
    }
}

void swap(TRAINER *a, TRAINER *b)
{
    TRAINER t;
    t = *a;
    *a = *b;
    *b = t;
    return;
}

//heapify in top-bottom approach.
void heapify(TRAINER A[], lli n, lli i)
{
    lli largest = i;
    lli l = 2*i + 1;
    lli r = 2*i + 2;
    if(l<n && A[l].s > A[largest].s)
    {
        largest = l;
    }
    if(r<n && A[r].s > A[largest].s)
    {
        largest = r;
    }
    if(largest != i)
    {
        swap(&A[i], &A[largest]);
        heapify(A, n, largest);
    }
}

//heapify in bottom-top  approach
void heapify2(TRAINER A[], lli n, lli i)
{
    lli parent = (i - 1) / 2;
    if (A[parent].s > 0)
    {
        if (A[i].s > A[parent].s)
        {
            swap(&A[i], &A[parent]);
            heapify2(A, n, parent);
        }
    }
}

void create_maxHeap(TRAINER A[], lli n)
{
    /*first non leaf node*/
    lli fnl = n/2 - 1;
    lli i;
    for(i=fnl; i>=0; i--)
    {
        heapify(A, n, i);
    }
}

void insertion(TRAINER A[], lli *n, TRAINER key)
{
    *n = *n+1;
    A[*n-1] = key;
    heapify2(A, *n, *n-1);
}

void deletion_top(TRAINER A[], lli *n)
{
    swap(&A[*n-1], &A[0]);
    *n = *n-1;
    heapify(A, *n, 0);
}

void program()
{
    lli N,D;
    scanf("%d%d", &N, &D);
    TRAINER A[N];
    lli i;
    for(i=0; i<N; i++)
    {
        scanf("%lld%lld%lld", &A[i].d, &A[i].t, &A[i].s);
    }
    mergeSort(A, 0, N-1);
    lli j = 0;
    TRAINER Heap[max];
    lli size = 0;
    for ( i = 1; i < D+1; i++)
    {
        while(A[j].d == i)
        {
            insertion(Heap, &size, A[j]);
            //printf("%d %d %d\n", Heap[0].d, Heap[0].t, Heap[0].s);
            j++;
            if(j == N)
                break;
        }
        //max priority person give lecture that day
        if(size != 0)
        {
            Heap[0].t--;
            //printf("%d\n", Heap[0].t);
            if (Heap[0].t == 0)
            {
                deletion_top(Heap, &size);
            }
        }
        //printf("%d\n", size);
    }
    //printf("%d %d %d\n", Heap[0].d, Heap[0].t, Heap[0].s);
    //printf("%d %d %d\n", Heap[1].d, Heap[1].t, Heap[1].s);
    unsigned long long int total_sad = 0;
    for(i=0; i<size; i++)
    {
        //printf("%d\n", Heap[i].s);
        // printf("%d\n", size);
        total_sad += (Heap[i].t)*(Heap[i].s);
    }
    printf("%llu\n", total_sad);
}

int main(void) {
	int T;
    scanf("%d", &T);
    while(T)
    {
        program();
        T--;
    }
	return 0;
}

IPC Trainers CodeChef Solution in JAVA

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static class Trainer{
        int day;
        int numOfLectures;
        int sadness;
        Trainer(int day , int numOfLectures, int sadness){
            this.day =day;
            this.numOfLectures = numOfLectures;
            this.sadness =sadness;
            
        }
    }
    
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T-->0){
		    int n = sc.nextInt();
		    int d=  sc.nextInt();
		    Trainer[] t = new Trainer[n];
		    for(int i=0;i<n ;i++){
		            Trainer temp = new Trainer(sc.nextInt(),sc.nextInt(),sc.nextInt());
		           t[i]=temp;
		            
		          //insert all values in one data structure day, numOfLectures, sadness   
		    }
		    //sort the data structure according to day they come  
		    Arrays.sort(t,(a,b)->(a.day-b.day));//accending
		    //max heap ds for storing sadness
		    
		    PriorityQueue<Trainer> priorityQueue = new PriorityQueue<>((a, b) -> (b.sadness - a.sadness));//decending
		    
		    int index = 0;
		    //traverse the day  from 1 to total days(d)
		    for(int i=1;i<=d;i++){
                // we add all days with cur day(i)		  
		        while(index<t.length&&t[index].day==i){
		            priorityQueue.add(t[index]);
		            index++;
		        }
		        
		        //if pq is not empty then for this day we decrease numOfLectures
		        //by one and that day is finisheed and we move to next day
		        
		        //and remember the pq is max heap of sadness and more sadness trainer coems on top 
		        //so less sadness
		        if(!priorityQueue.isEmpty()){
		            Trainer temp = priorityQueue.peek();
		            temp.numOfLectures--;
		            if(temp.numOfLectures==0){
		                priorityQueue.poll();
		            }
		        }
		    }
		    
		    long min=0;
		    while(!priorityQueue.isEmpty()){
		        Trainer cur=priorityQueue.poll();
		        min+=(long)cur.numOfLectures*cur.sadness;
		    }
		    System.out.println(min);
		    
		}
	}
	
}

IPC Trainers CodeChef Solution in PYPY 3

import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
#######################################

a=int(input())
from heapq import *

for i in range(a):
    n,d=map(int,input().split())
    ans=[]
    total=0
    for i in range(n):
        D,t,s=map(int,input().split())
        ans.append([D,t,s])
        total+=t*s
        
    ans.sort()

    dd=[]
    i=0
    for cnt in range(1,d+1):
        while(i<len(ans) and ans[i][0]==cnt):
            heappush(dd,(-ans[i][2],ans[i][1]))
            i+=1 
        if(len(dd)==0):
            continue
        
        cost,t=heappop(dd)
        t-=1 
        total+=cost
        if(t):
            heappush(dd,(cost,t))

    print(total)
    
        
        
        

IPC Trainers CodeChef Solution in PYTH

from heapq import heapify,heappop,heappush
import sys
input=sys.stdin.readline
from math import sqrt
from collections import defaultdict
def I():return list(map(int,input().split()))

for _ in range(int(input())):
    n,d=I()
    days=defaultdict(list)
    for i in range(n):
        di, ti, si = I()
        days[di].append((si,ti))
    heap=[]
    for day in range(1,d+1):
        for si,ti in days[day]:
            heappush(heap, (-si,-ti))
        if heap:
            si,ti=heappop(heap)
            if ti!=-1:
                heappush(heap, (si,ti+1))
    ans=0
    for si,ti in heap:
        ans += -si*-ti
    print(ans)
    

IPC Trainers CodeChef Solution in C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Test
{
	public static void Main()
	{
		IPCTrainers.Run();
	}
	
	public class IPCTrainers
    {
        public static void Run()
        {
            var solution = new Solution();

            var T = Convert.ToInt32(Console.ReadLine());       
            //var T = 1;
            for (int t = 0; t < T; t++)
            {

                var queue = new PriorityQueueLocal<Trainer>();

                var ND = Console.ReadLine().Split();
                var N = Convert.ToInt32(ND[0]);
                var D = Convert.ToInt32(ND[1]);

                //var N = 100000;
                //var D = 100000;

                var trainers = new List<Trainer>();
                var trainersRem = new List<Trainer>();
                for (int i = 0; i < N; i++)
                {
                    var DTS = Console.ReadLine().Split();
                    var AD = Convert.ToInt32(DTS[0]);
                    var L = Convert.ToInt32(DTS[1]);
                    var S = Convert.ToInt32(DTS[2]);

                    //var AD = i + 1;
                    //var L = 1;
                    //var S = 100;

                    var trainer = new Trainer(AD, L, S);
                    trainers.Add(trainer);
                    trainersRem.Add(trainer);
                }
               
                var trainersStack = new Stack<Trainer>();

                trainers = trainers.OrderByDescending(p => p.ArrivalDay).ToList();
                foreach (var trainer in trainers)
                {
                    trainersStack.Push(trainer);
                }

                var count = 1;
                while (count <= D)
                {                   
                    while (trainersStack.Count > 0 && count == trainersStack.Peek().ArrivalDay)
                    {
                        queue.Enqueue(trainersStack.Pop());                        
                    }

                    if (queue.Count() > 0)
                    {
                        var maxSadnessTrainer = queue.Peek();
                        maxSadnessTrainer.LecturesCount--;
                        if (maxSadnessTrainer.LecturesCount == 0)
                        {
                            queue.Dequeue();
                        }                      
                    }
                    count++;
                }

                long sum = 0;
                foreach (var trainer in trainersRem)
                {
                    sum += (long)trainer.LecturesCount * (long)trainer.SadnessLevel;
                }

                Console.WriteLine(sum);               
            }


            //var N = 2;
            //var D = 3;

            //var trainer1 = new Trainer(1, 2, 300);
            //var trainer2 = new Trainer(2, 2, 100);

            //var N = 2;
            //var D = 3;
            //var trainer1 = new Trainer(1, 1, 100);
            //var trainer2 = new Trainer(2, 2, 300);

            //var trainers = new List<Trainer>();
            //var trainersRem = new List<Trainer>();
            //trainers.Add(trainer1);
            //trainers.Add(trainer2);
        }      

        public class Solution
        {
            public string solution()
            {
                return "";
            }          
        }

        public class Trainer: IComparable<Trainer>
        {
            public int SadnessLevel { get; set; }
            public int ArrivalDay { get; set; }
            public int LecturesCount { get; set; }
            


            public Trainer(int ArrivalDay, int lecturesCount, int sadnessLevel)
            {
                this.ArrivalDay = ArrivalDay;
                this.LecturesCount = lecturesCount;
                this.SadnessLevel = sadnessLevel;
            }

            public int CompareTo(Trainer other)
            {
                return other.SadnessLevel - SadnessLevel;
            }
        }

        public class PriorityQueueLocal<T> where T : IComparable<T>
        {
            private List<T> data;

            public PriorityQueueLocal()
            {
                this.data = new List<T>();
            }

            public void Enqueue(T item)
            {
                data.Add(item);
                int ci = data.Count - 1; 
                while (ci > 0)
                {
                    int pi = (ci - 1) / 2; 
                    if (data[ci].CompareTo(data[pi]) >= 0)
                        break; 
                    T tmp = data[ci];
                    data[ci] = data[pi];
                    data[pi] = tmp;
                    ci = pi;
                }
            }

            public T Dequeue()
            {                
                int li = data.Count - 1; 
                T frontItem = data[0];
                data[0] = data[li];
                data.RemoveAt(li);

                --li;
                int pi = 0;
                while (true)
                {
                    int ci = pi * 2 + 1;
                    if (ci > li)
                        break;
                    int rc = ci + 1; 
                    if (rc <= li && data[rc].CompareTo(data[ci]) < 0)
                        ci = rc;
                    if (data[pi].CompareTo(data[ci]) <= 0)
                        break;
                    T tmp = data[pi];
                    data[pi] = data[ci];
                    data[ci] = tmp; 
                    pi = ci;
                }
                return frontItem;
            }

            public T Peek()
            {
                T frontItem = data[0];
                return frontItem;
            }

            public int Count()
            {
                return data.Count;
            }           
        }
    }
}

IPC Trainers CodeChef Solution Review:

In our experience, we suggest you solve this IPC Trainers CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the IPC Trainers CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this IPC Trainers CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn