| ENG RUS | Timus Online Judge |
Discussion of Problem 1424. MinibusFyodor Menshikov Simple problem or weak tests? [20] // Problem 1424. Minibus 15 May 2007 02:19 My solution should use 2 * M * K indexations of linear array in the worst case (100 000 000 for max M and K) but works about 0.5s, twice less than time limit, and it is Java! Does it mean that so simple algorithm is enough or that tests are weak? Edited by author 15.05.2007 02:27 Alexander Kouprin Re: Simple problem or weak tests? [19] // Problem 1424. Minibus 15 May 2007 03:57 I used greedy algo, pascal, 0.265sec works, O(2*M*K) too. svr Re: Simple problem or weak tests? [18] // Problem 1424. Minibus 15 May 2007 10:47 For such strong authors request of failed solver! Give us short clarification of this great optimization problem! What is more simple prototipe of it? What class of the problem? Graphs?DP? May be.... Dmitry 'Diman_YES' Kovalioff. Retired O(M*K) solution is ok (+) [3] // Problem 1424. Minibus 15 May 2007 11:54 Timus Online Judge server is fast enough to perform more than 100000000 operations per second. The problem is based on the Activity Selection problem. Fyodor Menshikov About server speed [1] // Problem 1424. Minibus 15 May 2007 12:08 Dmitry 'Diman_YES' Kovalioff. Retired wrote 15 May 2007 11:54 Timus Online Judge server is fast enough to perform more than 100000000 operations per second. The truth of this statement depends on operation kind. Recently I solved problem in which 50 000 000 operations * and % on 64-bit integers worked 2s. Dmitry, do you know more precise numbers, how many operations of each kind the server can execute per second? For example linear array indexations - 180 bln, long multiplication - 100 bln and so on... Dmitry 'Diman_YES' Kovalioff. Retired I think one can find the performance rate himself (+) // Problem 1424. Minibus 15 May 2007 16:53 Just write a kind of performance mark program, submit it and you will get exactly what you want. Then you may post the results here and everyone will appreciate your work. svr Re: O(M*K) solution is ok (+) // Problem 1424. Minibus 16 May 2007 22:37 Is Activity Selection problem standard internet term? Fyodor Menshikov Re: Simple problem or weak tests? [2] // Problem 1424. Minibus 15 May 2007 12:01 svr wrote 15 May 2007 10:47 What is more simple prototipe of it? I don't know. svr wrote 15 May 2007 10:47 What class of the problem? Graphs?DP? May be.... I'd said simulation. And I think Alexander Kouprin's definition "greedy" is right. The problem gets simpler if you change its model. You can allow driver to debus any boarded passenger at any stop < F[i] refunding the passenger all her money P. The driver in this case would get the same amound of money as if he would not board that debussed half-way passengers at all. Edited by author 15.05.2007 14:09 Alexander Kouprin Re: Simple problem or weak tests? [1] // Problem 1424. Minibus 15 May 2007 12:29 I'd said it's sorting problem. :) You have segments of way: first point and last. Your task is how to combinate maximum of segment in K lines. This lines can be severed inside of itself and have big holes. Fyodor Menshikov Re: Simple problem or weak tests? // Problem 1424. Minibus 15 May 2007 14:16 Alexander Kouprin wrote 15 May 2007 12:29 I'd said it's sorting problem. :) I used sorting too, but I think the main problem is to devise what to do after sorting. SPIRiT Re: Simple problem or weak tests? [10] // Problem 1424. Minibus 27 Jun 2007 14:00 I think it's a lecture hall assignment problem. One thing is that number of lecture halls here is limited by M... svr Re: Simple problem or weak tests? // Problem 1424. Minibus 27 Jun 2007 14:08 Thank for "lecture hall assignment" brand! SPIRiT Re: Simple problem or weak tests? [8] // Problem 1424. Minibus 4 Jul 2007 17:57 I tried to solve it running Greedy-Activity-Selector M times. But WA at test 4. What is wrong with such approach? svr Re: Simple problem or weak tests? [7] // Problem 1424. Minibus 29 Sep 2007 14:34 Gready _Activity_Selector of course. But with auxiliary subproblem: Let we have a set S={[ai,bi]} intervals chosen to some moment and according with greedy should include in S new segment [c,d]. Can we do it without excess of M. For, we must solve the problem of maximal overlapping value. I used augmented red-black tree as in Cormen but have very bad time 0.843 AC. Intuition says that good times taken due better ways of solving auxiliary problem. Edited by author 29.09.2007 14:41 SPIRiT Re: Simple problem or weak tests? // Problem 1424. Minibus 3 Oct 2007 21:35 Thanks, I realised that. I simply store now all stations beginnings in an array (maximum K). I initialise it with M value for each element. Now, for each request I go from start to end and check if all elements are non-zero (not including the end). If that requirement is met, I add the request to the result and decrement all checked elements SPIRiT Re: Simple problem or weak tests? [5] // Problem 1424. Minibus 9 Oct 2007 18:55 By the way. Should we sort just time ending of the activity? In that case I get WA#4, If I sort beginnings in decreasing order in case of end equals, I get TLE #4 marius dumitran Re: Simple problem or weak tests? [4] // Problem 1424. Minibus 29 Oct 2007 12:50 my algo is O(N + K *log(M)) -> AC in 0.1 Denis Koshman Re: Simple problem or weak tests? [3] // Problem 1424. Minibus 20 Aug 2008 12:02 Mine too :) hoan Re: Simple problem or weak tests? [2] // Problem 1424. Minibus 29 Dec 2010 20:35 i use segment tree and got AC in 0.109. what's the best algo? order of my algo is O((n+m)logn + klogk). GOOD LUCK!!! Solver Re: Simple problem or weak tests? [1] // Problem 1424. Minibus 2 Jul 2026 06:52 Segment tree with lazy propagation for amount of passengers at each station, so M is irrelevant. Passengers are bucket-sorted. O(K*log(N)+(N+K)) 0.062sec Edited by author 02.07.2026 06:52 LLM_AI_Testing Re: Simple problem or weak tests? // Problem 1424. Minibus 6 Jul 2026 19:39 (LLM-written, always verify, but AC 0.015s) Bucket passengers by start stop and sweep stops left to right; keep the currently accepted riding passengers in a structure that can return the one with maximum finish stop. When a passenger starts, accept him tentatively; if active accepted count becomes M + 1, delete from the active set the passenger with largest F. This greedy is safe because among simultaneously riding passengers, rejecting the latest-ending one frees capacity earliest for all future events compared with rejecting any earlier-ending one. With buckets plus a max-heap this is O(N + K log K); with a segment tree over finish stops it can be written as O(N + K log N). |