Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя hello_hell

Code Jam 2020 — Problem 3

Автор hello_hell, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Check for the multiple occurrences of same time activities.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    what do u mean by same time activities?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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;

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thanks , but brute force solution works for this testcase.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

      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$$$

      → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить