Discussion @ 1263. Elections @ Timus Online Judge

Megakrit Timing results [2] // Problem 1263. Elections 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!

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: Timing results // Problem 1263. Elections 15 Jan 2013 00:23

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.

Vasiliy Kobozev Re: Timing results // Problem 1263. Elections 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.

Discussion of Problem 1263. Elections