Problem discussion of Dream in Code 2.0

general
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.5xL1
The total area will be:
ar(UYW)+ar(UYV)=0.5x*(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).

1 Like
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.

7

Time Complexity : O(N^2 logN logMax(Ai))

8

Now that I think of it ,the time complexity should be O(N^2 log(maxAi)+ NlogN) ,
NlogN for sorting the array
Log(maxAi) for the binary search for K and now for each K , we do O(n^2) work.
O(n^2) because now in each iteration we have to iterate over all the rest of the elements in the worst case.

Can you explain how did you got O(NlogN*log(maxAi)) ?

9

Yes each time we select the then maximum and then for it we find the smallest elements out of the remaining elements. We continue doing this until either we are able to make all elements 0 or we aren’t able to transfer units.

10
11