ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1263. Elections

Timing results
Posted by Megakrit 14 Jan 2013 22:19
Hi, folks!

Can anyone give me the source code in C# of this task (mine is already AC) when the timing is less than 0.1 sec?
Or can anyone give me the key notes how it can be decreased in almost ten times?

Thanks in advance!
Re: Timing results
I presume your sol is O(NM), right?
Think a bit. There is O(N+M) solution which definitely has time better than 0.1 sec.
Re: Timing results
Posted by Vasiliy Kobozev 9 Dec 2016 02:10
1) Be sure that your algorithm is O(N+M)
2) When calculating percents you should not do: value * 100 / number inside cycle,
it is better to calculate "100.0 / number" one time before cycle and then just perfom multiplying.
3) I used float for keeping values, not int. I think it saves time of casting from int to float.

When I used 2 and 3 my time for c# decreased from 0.109 to 0.046.