| ENG RUS | Timus Online Judge |
Discussion of Problem 2017. Best of a bad lotOrfest (Novosibirsk SU) Problem statement clarification // Problem 2017. Best of a bad lot 17 Jan 2021 16:10 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. Md sabbir Rahman WA 14 // Problem 2017. Best of a bad lot 2 Aug 2018 15:42 Getting wa @ 14, can somebody please give me test cases for test 14? IgorKoval [PskovSU] WA5 WA22 [6] // Problem 2017. Best of a bad lot 21 Oct 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 bsu.mmf.team Re: WA5 WA22 [5] // Problem 2017. Best of a bad lot 21 Oct 2014 03:01 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. IgorKoval [PskovSU] Re: WA5 WA22 [4] // Problem 2017. Best of a bad lot 21 Oct 2014 03:13 "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:22 bsu.mmf.team Re: WA5 WA22 [3] // Problem 2017. Best of a bad lot 22 Oct 2014 01:25 It'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. Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: WA5 WA22 [2] // Problem 2017. Best of a bad lot 22 Oct 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 Flipped Re: WA5 WA22 [1] // Problem 2017. Best of a bad lot 23 Oct 2014 16:10 Sad!I was failed in the test 32... ilya trofimov Re: WA5 WA22 // Problem 2017. Best of a bad lot 31 Oct 2014 12:36 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!!!
|