Guys can you please share your approaches for the problem Chotu and Gang and the proof of Very Noob and Noob Farmer.

# Problem discussion of Dream in Code 2.0

**anmoliiitd**#2

For Chotu and Gang ,

Firstly observe that as sum(Ai) = 0 , hence we can make the whole array non-negative only by making each of the element 0 as we are transferring units , so if there was one element ai>0 then there must also exist an element aj<0 as we need sum(Ai) = 0. Therefore , the problem reduces to making each element 0.

Then observe that if we can make the array elements equal to 0 using a maximum of βKβ units transfer then we can also do the same using βK+1β units.

This hints binary search.

So let us assume that we are allowed to transfer at most K units in each transfer.

Now we propose a greedy strategy to solve by using at most K units ,

We pick the largest element (Why largest element? -> As we know that we need to transfer all its unit to make it 0) ,

Then start transferring βKβ units to the smallest elements one by one till our largest element gets 0 or get <K (in which case we transfer whatever is left to the then small element)

Now we have made at least 1 element 0 (that is the largest one we picked) ,

We continue this for the whole array

If we are able to make the whole array 0 then this βKβ works otherwise we need to increase our value of βKβ.

Time Complexity :- O(N^2 logN) , I think we can do better , so suggestion are most welcomed.

**pk301**#3

Can you explain this part a little more? Does it mean that next time we select a vertex with maximum value we escape the vertices which we have already considered in the previous steps?

And If we escape the previous vertices I know this indeed will make the whole array zero. But how can we conclude that this greedy strategy works?

I mean that it may happen that there is some other way of transferring weights to the vertices such that weight transferred on each edge is less then our current K but as we follow greedy we might have missed that. Can you please provide a rough proof or give some intuition how it is optimal ?

**vishu_pal**#4

For Very Noob Farmer,

Drop a perpendicular on side VW, assume itβs length to be x.

Then the area of triangle UYW will be:

0.5*x*L2=S(Given)=> 0.5*x=S/L2
and the area of triangle UYV will be:
0.5*x

*L1*

The total area will be:

ar(UYW)+ar(UYV)=0.5x*(L1+L2) = S*(L1+L2)/L2

The total area will be:

ar(UYW)+ar(UYV)=0.5

The profit will be:

S*(L1+L2)*p/L2

Thatβs the logic behind the problem. Hope it helps!

Time Complexity will be O(1).

#include <stdio.h>

int main(void) {

int T;

unsigned long long int s,l1,l2,p,ans;

scanf("%d",&T);

for(int i=0;i<T;i++)

{

scanf("%d%d%d",&s,&l1,&l2);

scanf("%d",&p);

ans=p*(l1+l2)*s;

ans=ans/l2;

printf("%d\n",ans);

}

return 0;

}

//what is error in it? It is showing WA.