hello_hell's blog

Code Jam 2020 — Problem 3

By hello_hell, history, 5 years ago, In English

In this problem i sorted the activities by their ending time. With this solution i got Wrong Answer 6 times. I got so much frustrated that i implemented this brute force solution & even it gave me a wrong answer. Would you please point out my mistake.

  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
5 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Does your code handle this case ?

2

1 2

1 2

for this case, your first solution is giving this output : JJ ( which is wrong ), the correct output must be either CJ or JC

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    explain ur case in a bit more detail.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes i think, end time time sorting order should give AC for this test case.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i sorted it by start time and it worked. Sorting by start time is correct. But I couldn't think, why sorting by end time is giving wrong answer.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Check for the multiple occurrences of same time activities.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what do u mean by same time activities?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      let's say Activity A occurs at [1 , 10] , Activity B also occur at same time i.e. [1 , 10]. Then in that case we have to print "CJ" or "JC" as our answer;

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not sure how your code is supposed to work.

I implemented event based solution. Every activity start is $$$1$$$ event, every end a $$$-1$$$ event. Sort events by time.

Put the two persons on a stack. For every start event, pop a person, for end event push the person used before for that activity.

Every push contributes to the answer. If you need to pop but there is no person on the stack then there is no solution.

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Greedy works if you sort by the starting time of each activity. Your program will say that "something is wrong" for this testcase:

1 4
0 200
50 100
150 300
250 270

When solving this problem, my first idea was to check for bipartite graph, so I stuck with it. The analysis of the problem is already available on the link you posted.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks , but brute force solution works for this testcase.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      Brute-forcing would be testing every possible division of activities. The second code you linked is a greedy solution that doesn’t work.

      Notice that while reading, you attribute the activities in input order, which is not necessarily the best and can be easily broken. Brute-forcing everything should be done in $$$2^n$$$

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ya, end time sorting would fail for this test case.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it is the use of the none_of(begin, end) function. End should be position on after the last, but is not in the code.

→ Reply