CULPRO algorithm

general
1

Well, it’s frustrating that I could solve DOMSOL and not this :confused:

Problem link: http://www.codechef.com/INPR1501/problems/CULPRO

How do I approach it?

2

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.

2 Likes
3

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.

4

@sandy999, please tell me what’s wrong with my DOMSOL code???

include “iostream”

include “algorithm”

include “cmath”

using namespace std;

int main()

{

int n;
cin >> n;
int x[n][2];
int best[n];
for (int i = 0; i<=n-1; i++)
{
	cin >> x[i][0] >> x[i][1];
	if (i==0)
	best[i]=abs(x[i][0]-x[i][1]);
	else if (i==1)
	best[i]=max(best[0]+abs(x[i][0]-x[i][1]), abs(x[i][0]-x[i-1][0])+abs(x[i][1]-x[i-1][1]));
	else
	best[i]=max(best[i-2]+abs(x[i][0]-x[i-1][0])+abs(x[i][1]-x[i-1][1]), best[i-1]+abs(x[i][0]-x[i][1]));
}
cout << best[n-1];
return 0;

}

5

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

1 Like
6

I’m actually wondering why my solution didn’t work as well. Really weird.
Edit: It was a misplaced bracket

7

And sample output should be 22 and not 12…very sure>>>

8

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

  1. Create array ALL[n] and store all exit and entry as pairs of the form Time, action. For example, store all entries as time, 0 (0 to suggest entry) and exits as time, 1(1 to suggest exit).
  2. Sort array, iterate from lowest value to highest time value, and add or subtract people depending on the boolean value in ALL[i].second .
  3. To ensure no duple’s(duplicates?) take place, keep seperate counters for out and in, subtract all possible repetitions from final answer and print.
  4. Complexity???
    O(n) where n is highest time - lowest time. I don’t think we need to get any better than this as there’s only one testcase per check and 2 secs are more than enough for that.
1 Like
9

@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. :slight_smile:

10

Ah! Now I see what you have done in there. Thanks :slight_smile:

1 Like
11

Note: Sorting is O(nlogn) so that’s your complexity, not O(n).

12

@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

13

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

14

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

15

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

16

@sandy999 my bad, had to tag @arpanb8, not you… :wink:

17

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