Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

hello_hell's blog

By hello_hell, history, 2 months 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

»
2 months 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

»
2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Check for the multiple occurrences of same time activities.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what do u mean by same time activities?

    • »
      »
      »
      2 months 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;

»
2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    u also went in order of start time sorted order.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this seems similar to maintaining two pointers and move forward the pointer which is less then or equal to current event's starting time. if you find there is no pointer with such condition then there exit no solution.

»
2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks , but brute force solution works for this testcase.

    • »
      »
      »
      2 months 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$$$

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 months 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.