|
|
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 |
|
|
