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

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

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

1 Like

@damn_me I tried that and it still gives WA.

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:


vectorarray(10010);

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

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

1 Like

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

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 ?

and most welcome… :slight_smile:

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

let me try to solve this problem, if i’ll be able to get AC in less time i’ll definitely post it here… :slight_smile:

@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.

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.

@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.

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

After several optimizations,my execution time is reducing by 0.02 :stuck_out_tongue:
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.

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

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

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

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…!

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