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.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.11.2024 08:39:14 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
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
explain ur case in a bit more detail.
yes i think, end time time sorting order should give AC for this test case.
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.
Check for the multiple occurrences of same time activities.
what do u mean by same time activities?
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;
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.
u also went in order of start time sorted order.
Greedy works if you sort by the starting time of each activity. Your program will say that "something is wrong" for this testcase:
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.
thanks , but brute force solution works for this testcase.
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$$$
ya, end time sorting would fail for this test case.
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.