|
|
back to boardi'm sad Algo O(nm) works for 1.046 sec, but O(2n) uses more than 65536kb. Edited by author 02.01.2014 15:28 Re: i'm sad 1.031 for O(NxM) with pre-exit after left coordinate of segment > coordinate of point. Any idea for modifications? Re: i'm sad Posted by adamant 22 Jan 2014 16:37 0.625 for O(mlogn) solution using C++ STL set... I think the problem is harder, than its difficulty score if there is no easier solution. Re: i'm sad Posted by adamant 24 Jan 2014 14:18 Well, okay, there is a O(mlogn) solution with sorting only and 0.125s execution time. Re: any detailed algorithm? Can you please write some more details for sorting based algorithm? Re: any detailed algorithm? I think you can search for red-black trees algo, it has O(nlogm) but its realy hard as for me. Small(?) hint Posted by Leonid 14 Mar 2014 11:03 This problem can be solved fast, if you'll try not to consider common solution, but only this ( there is some useful limits in statement, also order is very convenient ) case. Small hint, that I promised: Imagine a big-length wall, like in old platformers, where segments are vertical levels and segment's coords are horizontal coords. Example: 4 2 10 2 3 5 7 6 7 00000011000 00110111000 00111111111 1 are bricks in our wall. Edited by author 14.03.2014 11:03 Re: Small(?) hint Posted by a6 14 Mar 2014 13:38 FUCKING PIGS SUCK A DICK Re: i'm sad Since the input is sorted already, there is a O(n+m) solution |
|
|