Well, it's frustrating that I could solve DOMSOL and not this :/ Problem link: http://www.codechef.com/INPR1501/problems/CULPRO How do I approach it? asked 29 Jan '15, 21:22
showing 5 of 7
show all

Make an array of pairs. The first integer is the time, and the second denotes whether it's entry or exit. Sort it. Maintain a variable telling the number of people currently in the hall. Iterate through the sorted array. If exit, decrement. If entry, increment. The answer is the maximum cur at any point of time. answered 29 Jan '15, 21:56
Whoa! You made it so simple and intuitive, wish I had thought of it in the contest. And btw, just checked your solution, you seem to have done something different (maybe not entirely), what exactly is it? Just curious.
(29 Jan '15, 22:46)
1
I do the same thing essentially, but I didn't think of keeping them in the same array. I keep two different arrays: one for entry and one for exit. If you know how to merge two sorted arrays, what I did is quite similar to that. I go through the elements of both the arrays in ascending order of time, but it's a bit more involved because there are two arrays. Let me know if you need me to explain in detail Edit: If you're looking at my code look at my first submission, it's simpler, wrong only because the array wasn't big enough. http://www.codechef.com/viewsolution/6035356
(30 Jan '15, 00:06)
1
Ah! Now I see what you have done in there. Thanks :)
(30 Jan '15, 11:39)

[My first answer on Codechef] I was also unable to solve it last night but solved DOMSOL. Actually, I just sat down later and thought, and came to the realisation that the question is quite simple. Here's a solution that's a little different than @superty (you rock dude) 's solution.
answered 30 Jan '15, 08:57
@nibnalin Umm.. I don't see how different your solution is from that of @superty. And it is clearly stated in the problem that entry and exit times are distinct so there is no question of repetitions. Thanks anyway. :)
(30 Jan '15, 11:37)
Note: Sorting is O(nlogn) so that's your complexity, not O(n).
(30 Jan '15, 11:53)
@sandy999 ya, youré right, din't read his soln with patience. Also had the soln of using a stack in mind... @superty I won't really be sorting in code, and rather just use a set to have an inbuilt sorted array. And insertion in set is O(lg N) in current array size, and that would initially be near zero and increment to 12 after a long time, hence it's a factor that can be forgotten about...
(30 Jan '15, 12:46)
No, it really can't. And using a set is worse than having an array and sorting because set has a huge constant factor due to it being a balanced binary search tree and rebalancing operations are really time consuming. Please never use a set unless you actually need all the features it provides. If you just want to sort just use sort. With regard to lgN being small: it really isn't. lg1 + lg2 + ... + lg10^5 = 1.516*10^6 (may not be accurate. wolfram alpha wasn't working for me so I got a friend to find out for me) 10^5lg(10^5) ~ 10^517 = 1.7*10^6
(30 Jan '15, 13:26)

@sandy999, please tell me what's wrong with my DOMSOL code???
include "iostream"
include "algorithm"
include "cmath"
using namespace std;
int main()
{
}
I'm actually wondering why my solution didn't work as well. Really weird. Edit: It was a misplaced bracket
And sample output should be 22 and not 12...very sure>>>
@arpanb8 I don't see how sample input should give 22 instead of 12. And secondly, abs is a function of cstdlib library, not cmath
@arpanb8 there are a number of mistakes in your code. The first being youré not taking input correctly. the first line contains elements x[i][0] for all i < n and second line contains x[i][1] for all i < n. Secondly, the correct way to solve the question using DP would work from right to left, unlike your code. If you dont understand what I mean, see my code at http://www.codechef.com/viewsolution/6037067 . Also, @superty, I also got WA thrice due to misplaced brackets(may they die!).And @arpanb8 , the answer of sample input is correct.
@nibnalin What are you saying? My input method seems right to me and my DP is also from right to left. And moreover, it fetched an AC. Please check again.
@sandy999 my bad, had to tag @arpanb8, not you... ;)