|
|
back to boardShow all messages Hide all messagesi'm sad Two-Eight-Nine [[ §289]] 2 Jan 2014 15:27 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 Evgeniy_Chernobrovkin(MUCTR-2013) 21 Jan 2014 06:15 1.031 for O(NxM) with pre-exit after left coordinate of segment > coordinate of point.
Any idea for modifications? 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. Well, okay, there is a O(mlogn) solution with sorting only and 0.125s execution time. Can you please write some more details for sorting based algorithm? I think you can search for red-black trees algo, it has O(nlogm) but its realy hard as for me. 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: i'm sad Dmytro Dziuma (DixonD) [Lviv NU] 24 Apr 2014 04:06 Since the input is sorted already, there is a O(n+m) solution |
|
|
