You are not logged in. Please login at www.codechef.com to post your questions!

×

[closed] 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? :)

asked 18 Mar '17, 00:12

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

closed 18 Mar '17, 11:27

No it sets the entire array to zero

(18 Mar '17, 00:26) tihorsharma1232★

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

(18 Mar '17, 00:33) vijju123 ♦♦5★

The question has been closed for the following reason "The question is answered, right answer was accepted" by vijju123 18 Mar '17, 11:27


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

link

answered 18 Mar '17, 00:21

tihorsharma123's gravatar image

2★tihorsharma123
49918
accept rate: 15%

edited 18 Mar '17, 00:22

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)

(18 Mar '17, 00:34) vijju123 ♦♦5★

i think you should change the data type to long long and the use the above method..

link

answered 18 Mar '17, 00:32

viralivora's gravatar image

4★viralivora
1838
accept rate: 14%

which "Above method" ? The method which I used or the method linked by @monalshadi?

(18 Mar '17, 00:39) vijju123 ♦♦5★

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

(18 Mar '17, 11:15) viralivora4★

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.

link

answered 18 Mar '17, 00:20

monalshadi's gravatar image

2★monalshadi
524
accept rate: 16%

edited 18 Mar '17, 00:28

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

(18 Mar '17, 00:35) vijju123 ♦♦5★
1

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

(18 Mar '17, 00:43) monalshadi2★

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

(18 Mar '17, 00:44) vijju123 ♦♦5★

Thanks to all of you, I got correct answer. Yes, the problem was overflow, I should be more careful next time. Thanks again! :)

link

answered 18 Mar '17, 11:26

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,070

question asked: 18 Mar '17, 00:12

question was seen: 457 times

last updated: 18 Mar '17, 11:27