You are not logged in. Please login at www.codechef.com to post your questions!

×

CULPRO algorithm

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

sandy999's gravatar image

3★sandy999
39111437
accept rate: 10%

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

}

(29 Jan '15, 23:44) arpanb83★

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

(30 Jan '15, 00:07) superty3★

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

(30 Jan '15, 00:24) arpanb83★

@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

(30 Jan '15, 12:01) sandy9993★

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

(30 Jan '15, 12:42) nibnalin6★

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

(30 Jan '15, 13:15) sandy9993★

@sandy999 my bad, had to tag @arpanb8, not you... ;)

(30 Jan '15, 13:26) nibnalin6★
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.

link

answered 29 Jan '15, 21:56

superty's gravatar image

3★superty
3647
accept rate: 31%

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) sandy9993★
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) superty3★
1

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

(30 Jan '15, 11:39) sandy9993★

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

answered 30 Jan '15, 08:57

nibnalin's gravatar image

6★nibnalin
1611414
accept rate: 0%

@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) sandy9993★

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

(30 Jan '15, 11:53) superty3★

@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) nibnalin6★

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) superty3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×10

question asked: 29 Jan '15, 21:22

question was seen: 1,249 times

last updated: 30 Jan '15, 13:26

Related questions