|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Problem statement clarification | Orfest (Novosibirsk SU) | 2017. Меньшее из зол | 17 янв 2021 16:10 | 1 | I'm confused by this sentence in the problem statement:
"the murderers have agreed that their testimonies will have no contradictions between them"
Does that mean that tests like this are invalid?
3
A 1 2
B 1 3
C 1 1
In this test there are 3 people and each one conflicts with at least one another. If one person is declared a murderer, there is still a contradiction between the other two.
No 2 people can be declared murderers because there is always a contradiction between any 2 of them. | | WA 14 | Md sabbir Rahman | 2017. Меньшее из зол | 2 авг 2018 15:42 | 1 | WA 14 Md sabbir Rahman 2 авг 2018 15:42 Getting wa @ 14, can somebody please give me test cases for test 14? | | WA5 WA22 | IgorKoval [PskovSU] | 2017. Меньшее из зол | 31 окт 2014 12:36 | 7 | WA5 WA22 IgorKoval [PskovSU] 21 окт 2014 02:40 My solution:
Let's build graph. There are undirected edge between vertex A and B if and only between passengers A and B exist contradictions.
Let's color each compenent of graph in two color. Then let's add ALL vertexS with same color(with min count) from each component to answer.
Why i get WA?
P.S.: between passengers A and B exist contradictions if and only if A was in placeA but B was in placeB and detected A there.
Edited by author 21.10.2014 03:02
Edited by author 21.10.2014 03:47 Do you add only one vertex per component that has color with less vertices count than the other? If so, you should add all vertices from each component instead.
Also I'd recommend you to check what you do with isolated vertices. "Do you add only one vertex per component that has color with less vertices count than the other? If so, you should add all vertices from each component instead." Yes. My pure English. =) I add all verticeS. "Also I'd recommend you to check what you do with isolated vertices." If component consist from one isolated vertices than I add to answer no vertex. If graph consist only from isolated vertices (sample test 2) than I add to answer vertex #1. After +100500 submit I get test #5: ============== 3 A 1 3 WC 1 3 WC 0 ============== I just go mad =) My code: http://ideone.com/a9EPDj Edited by author 21.10.2014 18:05 Edited by author 21.10.2014 18:22It's hard to say what's wrong in your code. But after fast looking at it I would start with checking a condition if two person's statements contradict each other. It may be slightly incorrect. Re: WA5 WA22 Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 22 окт 2014 03:24 I found the reason for WA5. The problem is that when a person ***doesn't contradict***, the info still can influence the answer. Example:
3
A 1 2
B 1 1
A 1 1
So, your prog finds 1 contradicting pair 1-2 and may think the guy 1 is the bad one, but this gives you 2 bad guys in total (because the guy 3 says he saw the guy 1 in place A), so the only right answer is #2. The test can be fixed a bit to make guy 1 the only bad guy.
So, first check for your prog is the following 2 tests:
3
A 1 2
B 1 1
A 1 1
=> answer 1 2
3
A 1 2
B 1 1
B 1 2
=> answer 1 1
Sad!I was failed in the test 32... It is a maximum independent set problem ( NP problem). Greedy or random gives wa14. Method of branches and borders gives TL6. Help to choose algo!!! |
|
|
|
