Problem discussion of Dream in Code 2.0

discussion

#1

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


#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.


#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 ?


#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.5xL2=S(Given)=> 0.5x=S/L2
and the area of triangle UYV will be:
0.5
xL1
The total area will be:
ar(UYW)+ar(UYV)=0.5
x*(L1+L2) = S*(L1+L2)/L2
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).


#5

#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.


#6

ans will overflow, you can solve this with the use of gcd concept here.