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

×

Count of maximum : wrong answer[Closed] but looking for a faster method.

Here is my attempt : http://ideone.com/FIMwbF which is giving wrong answer, it happens to answer all the test cases and I proceed in such a way that it always gives the minimum value with the maximum count. Are there any other corner cases where it fails ? I can't happen to find one. Thanks :)

EDIT : Now I'm trying to get 0.00 execution time,managed 0.08 so far.

asked 21 Dec '14, 16:20

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2802319
accept rate: 10%

edited 22 Dec '14, 02:12


See this. Your code fails for this test case. The problem is in line 24 i.e.

for(int i=0;i<10000;i++)

It should be for(int i=0;i<=10000;i++). See constraints, A[i]<=10000

link

answered 21 Dec '14, 16:54

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

hey @h1ashdr@gon ..

Just change the size of array from 10000 to 10010 for safe side and you'll get AC'ed. Reason as you are incrementing the count at index of number so if number is 10000 then your code will fail as last index of your array will be 9999

Change to be made:

vector<int>array(10010);


Check your modified AC code: http://www.codechef.com/viewsolution/5627031 :)

EDIT: For better complexity,

APPROACH 1:
Using that single hash approach while taking input i stored value in hash and at the same time i counted the max value in hash.
Then I iterate over hash and checked for that max number and as soon as i found that number i printed the index of hash and the max number.
This approach decreased execution time to 0.08 sec using fast io.
Link for this approach: http://www.codechef.com/viewsolution/5632916

and

APPROACH 2:
Again using single hash approach while taking input i stored value in hash and at the same time i counted the max value in hash but this time i checked that

if hash(inputValue)==currMaxValue :
    if inputValue < answer:
        then currMaxValue =hash(inputValue)
        answer=inputValue

and after iteration i printed answer and currMaxValue.
This approach took 0.09 sec for execution.
Link for this apporach: http://www.codechef.com/viewsolution/5632968

link

answered 21 Dec '14, 20:36

rishabhprsd7's gravatar image

2★rishabhprsd7
1.9k11242
accept rate: 14%

edited 22 Dec '14, 01:35

I see,thanks! :) both of you,I see how very minute details can cause WA!

(21 Dec '14, 20:45) h1ashdr@gon3★

and most welcome.. :)

(21 Dec '14, 20:52) rishabhprsd72★

haha.. I know each minute details cause problem, coz i just faced it...!!

(21 Dec '14, 20:52) rishabhprsd72★

0.08 is attainable even using my for loop! I was wondering for a way to 0.00 Thanks though :)

(22 Dec '14, 02:11) h1ashdr@gon3★

Actually i didn't understood what are those macros in best solution.
so i am unable to figure it out what actually is happening in that code..
Btw welcome.. :)

(22 Dec '14, 02:17) rishabhprsd72★

hey @h1ashdr@gon
View this solution: http://www.codechef.com/viewsolution/814448
On observing this solution i found that approach is same but coder has used really fast input method..!

(22 Dec '14, 02:22) rishabhprsd72★
showing 5 of 6 show all

@damn_me I tried that and it still gives WA.

link

answered 21 Dec '14, 20:20

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2802319
accept rate: 10%

@h1ashdr@gon Please try mentioning doubts/problems to someone's answer as a comment, not as a separate answer. It's a good practise and even keeps your question's forum organised.

(21 Dec '14, 22:55) damn_me3★

The problem is solved, another possible question I have in mind is that is there any way of reducing the time complexity further using the same approach ?

link

answered 21 Dec '14, 20:48

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2802319
accept rate: 10%

let me try to solve this problem, if i'll be able to get AC in less time i'll definitely post it here.. :)

(21 Dec '14, 20:54) rishabhprsd72★

I think we can, I used two hashes. One for counting the occurrences and other I hashed the count values. That is stored the element for its corresponding count. Something like this: http://ideone.com/kZMnhq. Simultaneously, I inserted the count in a set and found the maximum count. This becomes logarithmic in time complexity. And then I output the number for which I have that count. But it's giving TLE.

(21 Dec '14, 22:58) damn_me3★

@damn_me , I managed to get AC (your solution) with faster I/O. http://www.codechef.com/viewsolution/5632824 but its 5 seconds!! its almost 5 times as bad. I don't think its a good idea to use 2 hashes somehow.

(22 Dec '14, 01:01) h1ashdr@gon3★

Using fast io my exec. time was .16 sec!!

(22 Dec '14, 01:05) rishabhprsd72★

After several optimizations,my execution time is reducing by 0.02 :P I am on 0.08 now.I guess to get 0.00 I need to remove the for loop! That would change the whole method but.

(22 Dec '14, 01:21) h1ashdr@gon3★

read the edits on my post, and yes i managed to optimize my code to run in 0.08 sec.

(22 Dec '14, 01:38) rishabhprsd72★

@h1ashdr@gon I don't understand why that hash is taking so much of time!!

(22 Dec '14, 11:52) damn_me3★
showing 5 of 7 show all
toggle preview
Preview

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:

×832
×323
×84
×41
×13

question asked: 21 Dec '14, 16:20

question was seen: 1,333 times

last updated: 22 Dec '14, 11:52