How to solve it fast ?

Binary search over A such that Z(A) = 0 gives TL 30.

Is it necessary to use sparsification or other sophisticated methods?

When m = 500000, n = 1000 reading of input data (~10mb) takes about 2.5 sec. I'm wonder how could people to solve it in 0.6 sec..

Just ideas or links what should i read to solve it.

or at least your solution complexity..

*Edited by author 20.04.2007 02:42*

Re: How to solve it fast ?

hm.. I think your solution correct

can you explain how to use bs

I can send to you c++ prog wich read 10Mb ~ 0.6-0.7 sec

Re: How to solve it fast ?

Assign with each edge weight function w(x) = a - bx, where a = numerator, b - denominator. Let z(x) weight of minimal spanning tree at point x. If we find such x, that z(x) = 0 (such value always exists), x will be answer.

Re: How to solve it fast ?

Thank you

but why it works, is it standart method?

Re: How to solve it fast ?

Re: How to solve it fast ?

I think only optimisation is needed

You will call SpanTree O(n^2) not more then 50 times

It takes less then 2 sec

You can speed up input several times

If write like this

scanf("%d%d%d%d\n",&a,&b,&c,&d);

on 10Mb it will work ~3 sec

Re: How to solve it fast ?

TLE 34 :(

I used mix of binary search and Mediggo's approach.

>>You will call SpanTree O(n^2) not more then 50 times

And how to solve MST in O(n^2)?

*Edited by author 28.04.2007 16:05*

Re: How to solve it fast ?

I used just plain binary search and computed the MST with Prim's algorithm. No complicated data structures or Megiddo's aproach are needed here. Just some small optimizations on the code.

Re: How to solve it fast ?

Thanks a lot! I finally solved it in 0.375. But can't optimize to your 0.359 :)

Re: How to solve it fast ?

*Edited by author 04.09.2008 20:32*

Re: How to solve it fast ?

I constantly got with binary search TL6. Then I replaced binary search with iterative approach. I.e. build MST tree for x=1e+6, then build MST with whatever ratio previous tree had. Proceed until improvement is >1e-8. Now AC :)

Re: How to solve it fast ?

Binary search works VERY fast if you combine it with disjoint sets

Re: How to solve it fast ?

It does not matter here because edge-sorting step consumes O(N^2*log(N)) time.