Problem link
My Submissions here
My logic-
Use Array to store how many buildings of a particular height exist.
Use formula n*(n-1) to calculate all possible pairs.
Eg-
Let there be 5 buildings of height one. I had already defined an array “height[1000001]={0}” to store number of buildings of a particular height. So, it will store 5 for 1.
Now, say our array is like- 1 1 1 1 1
I can pair 1 at I=0 with 1 at I=1,2,3,4. Similarly I can pair 1 at I=1 with 1 at 1=0,2,3,4.
So I derive the formula- Number of Pairs = n(n-1) (via mathematical induction)
But its giving me WA. Can someone help?
Hello @vijju123 I too faced the same problem
My solution link :My solution
I thought maybe I was doing something wrong then I went on to check some AC and I found this in one of the AC’s another AC
@admin I think there might be something wrong while checking the test cases. Please look into this.
1 Like
Overflow mistake
Since you have declared height[] array as int and you are doing height[i]*height[i] which is atmax 10^10 and height[i] is int
2 Likes
i think you should change the data type to long long and the use the above method…
1 Like
Thanks to all of you, I got correct answer. Yes, the problem was overflow, I should be more careful next time. Thanks again!
No it sets the entire array to zero
That was initialisation done once. Please see my code to get a clearer picture
Possible. I see your point. I was under impression that since I declared ans “long long int”, it would get promted. (I know it doesn’t happen in case of float and double but still…:3 FML XD)
That answer used maps. I am ineligible to comment since I don’t know that concept. If you feel that there is something wrong, then mail it at bugs@codechef.com and they’d confirm the issue.
which “Above method” ? The method which I used or the method linked by @monalshadi?
It doesn’t matter, map is just another way to store data. Main thing is about the logic or algorithm.
I guess I did the same mistake too with overflow, I used long int in place of long long int. Thanks for pointing out this post
1 Like
If it proved helpful to you, I am most glad dear
the method used by you…n*(n-1)