Abacus-17-ABCS03- Please Help.

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? :slight_smile:

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! :slight_smile:

No it sets the entire array to zero

That was initialisation done once. Please see my code to get a clearer picture :slight_smile:

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. :slight_smile:

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 :slight_smile:

1 Like

If it proved helpful to you, I am most glad dear :slight_smile:

the method used by you…n*(n-1)