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.
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.
It should be
for(int i=0;i<=10000;i++). See constraints,
@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:
Check your modified AC code: http://www.codechef.com/viewsolution/5627031
EDIT: For better complexity,
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
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)
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
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 ?
I see,thanks! both of you,I see how very minute details can cause WA!
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…
@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.
I managed to get AC (your solution) with faster I/O.
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
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
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…
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!!