Unable to understand the problem with my code. pls help
ide : https://ide.codingblocks.com/s/188430
Valentine Magic
I will suggest you to use greedy approach
I’ll try my best to explain this to you.
So 1st lets consider a brute force solution.There are M girls with g1,g2…,gm candies and n boys with b1,b2…,bn chocolates. We can simply check all possible assignments of boys to girls. The 1st boy has m girls available, 2nd boy has m-1 girls available and last boy has m - n + 1 girls available. So the total possible assignments are X = m*(m-1)(m-2)…(m-n+1). so whichever of these X assignments has the minimum sum of abs(bi - gj) is our answer.
Now consider the best possible assignment of all boys to N girls will have the following N girls :
gi1, gi2, gi3, … gin. now think to minimize the absolute differences of candies and chocolates of a couple. Which boy will you assign to the girl with the largest amount of candies?
Take an example :
boys : 10, 5, 8, 6, 12
girls : 1, 8, 5, 12, 9, 16, 13
Now let us say I randomly pick 5 girls out of the above 7 girls to pair with 5 boys and they are:
1, 5, 9, 16, 13
Now you have 5 girls and 5 boys. All we need is an assignment that gives minimum sum of abs arrangements for these 5 selected girls.
which boy would you like to pair the girl with 16 candies to? To me it feels intuitive that I will pair her with the boy having 12 candies as abs(16 - 12) = 4 which will lead to a better ans than if I had paired her with someone else. So out of all 5! possible arrangements, the best arrangement will the one in which girl with most candies is paired with boy with most chocolates and so on.
This is just exactly what sorting does in the DP solution.
we first sort the candies and chocolates. if the boy with most candies is assigned to the kth girl(in sorted order) then all other boys will be assigned to girls in the range 1 to k - 1th.
Short explanation : if you had n boys and n girls you will always assign them in order of increasing candies and chocolates otherwise answer will not be minimum. The image below tries to prove this for 2 boys and 2 girls in which boy with lesser chocolate is assigned to girl with lesser candies which leads to an optimal solution. If you understand this it will be easy to prove for n boys and n girls as well.
if this solves your doubt, please mark it as solved
But what is the error in my code ?
I followed the approach suggested by you, but still getting wrong answer in 2 cases. Kindly help. IDE : https://ide.codingblocks.com/s/199239
hi, I am unable to view your code
import java.util.*; public class valentine2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int boys[] = new int[n]; int girls[] = new int[m]; int i; for(i=0;i<n;i++) boys[i] = sc.nextInt(); for(i=0;i<m;i++) girls[i] = sc.nextInt(); Arrays.sort(boys); Arrays.sort(girls); int ans=0; int j=n-1; for(i=m-1;i>=0;i–) { if(j<0) break; if(boys[j]==girls[i] || j==i) { ans += Math.abs(girls[i]-boys[j]); j–; } else if( (Math.abs(girls[i]-boys[j])) < (Math.abs(girls[i-1]-boys[j]) )) { ans += Math.abs(girls[i]-boys[j]); j–; } } System.out.println(ans); } }
I am unable to understand the problem with my code. pls help. Ide : https://ide.codingblocks.com/s/215563
It worked. But may i know the reason why we changed it to 100000000 instead of INT_MAX ?
@seemantanishth
In line 19 you were adding diff to result of solve
What if solve return INT_MAX
In that case INT_MAX + ( Any positive value ) overflows and becomes negative
If your query is resolved please close the doubt