ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1447. Portkey Network

How to solve it fast ?
Posted by diver_ru 19 Apr 2007 18:45
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..

or at least your solution complexity..

Edited by author 20.04.2007 02:42
Re: How to solve it fast ?
Posted by KIRILL(ArcSTU) 20 Apr 2007 04:10
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 ?
Posted by diver_ru 20 Apr 2007 09:40
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 ?
Posted by KIRILL(ArcSTU) 20 Apr 2007 13:48
Thank you
but why it works, is it standart method?
Re: How to solve it fast ?
Posted by diver_ru 20 Apr 2007 17:36
Problem called Minimal Ratio Spanning Tree, and brute binary search got TLE. But i think, using Mediggo method it's possible to solve it in time.

http://theory.stanford.edu/~megiddo/pdf/rational.html
Re: How to solve it fast ?
Posted by KIRILL(ArcSTU) 20 Apr 2007 18:46
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 ?
Posted by diver_ru 28 Apr 2007 15:35
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 ?
Posted by Furtuna Dan Emanuel 28 Apr 2007 17:18
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 ?
Posted by diver_ru 28 Apr 2007 20:26
Thanks a lot! I finally solved it in 0.375. But can't optimize to your 0.359 :)
Re: How to solve it fast ?
Posted by Denis Koshman 4 Sep 2008 12:13

Edited by author 04.09.2008 20:32
Re: How to solve it fast ?
Posted by Denis Koshman 4 Sep 2008 20:44
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 ?
Posted by Denis Koshman 10 Sep 2008 03:03
It does not matter here because edge-sorting step consumes O(N^2*log(N)) time.