Help in Shifting Spoons (Lunchtime Jan 2021)

I made observation that till some pile is shorter than first pile , we will keep increasing the first pile . If at some point height of all piles are greater than height of first pile then we will make some other pile i , i≠1 height equal to the first pile by transferring it’s content so some pile j , j≠1 . Then again we can increase height of first pile .

I didn’t knew how to do second point optimally . Could someone explain their solution if it was on similar lane of thought .

Problem Link

1 Like

Well mine was a similar
You can store the array index and array value in pair of set . Iterate in the set Now till the time the height of 1st is larger than the height of the new one just keep deleting that element from set and keep adding its value to the 1st one, then when you encounter the case that value in set is greater than 1st one then just add the extra value to the next element in the set (if there is no next element there is no answer ) and remove the make the current value = value of 1st and make value of 1st twice . Link to my AC submission

1 Like

Thanks.I exactly thought same.How to justify this solution ?

See I can tell you my thought process
Since we have to remove element from the smallest element so we cannot make 1st one as empty and then shift all to it .
The next thing was that since we want all elements in 1 so we will have yo transfer them regularly and keep on increasing it . And if at the end we are not able to transfer then the Answer is No. I know that this is in no way a proof

1 Like

where is the mistake ?? anyone

if i work according to your logic then there can be this way too.
if i select the largest element , then put all elements one by one to this except the first one and later on put one to the largest one.

but i am not getting thats wrong since it have been asked to put in first one at last but neither , nor mine solution , nor your way does that ,
we need to put elements to the first at last .

#include <bits/stdc++.h>
using namespace std;
int main() {
	long long int t;std::cin >> t;
	while(t--){
	priority_queue<pair<long long int,long long int>, vector<pair<long long int,long long int>>, greater<pair<long long int,long long int>>>heap; 
	long long int n;std::cin >> n;
	long long int bada;
	std::cin >> bada;
	
	for(long long int i=1;i<n;i++){
	    long long int x;std::cin >> x;
	    heap.push({x,i});
	}
	std::vector<pair<long long int,pair<long long int,long long int>>>answer;//kahas , kahatak , kitna
	bool canbe=true;
	while(heap.size()){
	    long long int hel = heap.top().first;long long int kaha=heap.top().second;
	    heap.pop();
	    if(hel<=bada){
	        bada+=hel;
	        answer.push_back({kaha,{0,hel}});
	    }
	    else{
	        if(heap.size()){
	            long long int a1=heap.top().first;long long int b1=heap.top().second;
	            heap.pop();
	            int dif=a1-hel;
	            a1+=dif;
	            hel-=dif;
	            answer.push_back({kaha,{b1,dif}});
	            heap.push({hel,kaha});
	            heap.push({a1,b1});
	        }
	        else{
	            canbe=false;break;
	        }
	    }
	}
	if(canbe==false){
	    std::cout << -1 << std::endl;
	}
	else{
	    for(long long int i=0;i<answer.size();i++){
	        std::cout << (answer[i].first)+1<<" "<<(answer[i].second.first)+1<<" "<<answer[i].second.second << std::endl;
	    }
	}
	}
	return 0;
}

finally got the actual way but still getting TLE , anyone can help where i am getting more time