Discussion @ 1541. Chase @ Timus Online Judge

2<m/n<3

Posted by Mehas (PSU #1) 5 Sep 2007 00:04

I got AC on this problem with normal solution, when 0<m/n<2, and with search when 2<=m/n<=3. Is there some smart solution in that case?

Re: 2<m/n<3

Posted by Mehas (PSU #1) 5 Sep 2007 00:50

Hm... Now the main problem is constraint of v<100000...

Re: 2<m/n<3

Posted by Mehas (PSU #1) 5 Sep 2007 00:50

Hm... Now the main problem is constraint of v<100000...

Re: 2<m/n<3

Posted by Vedernikoff Sergey 5 Sep 2007 01:06

My brute-force solution process any test with constraint v < 5000. So, in you algo you can also assume that v <= 5000. Amazingly, but this will speed up your algo dramatically...

Re: 2<m/n<3

Posted by Denis Koshman 15 Jul 2008 02:18

In case of my algo decreasing the limit slows things down (fair AC w/o tables as it meets TL for every pair or M/N)

Discussion of Problem 1541. Chase