A Wild Goose Chase

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.5s
Memory limit: 128M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Recently, geese was murdered! The city has asked you to help Ducktective to figure out who murdered geese. There are N foxes numbered 1 to N suspected to have killed geese. Ducktective is a very patient duck, and he has gotten every fox to say a statement. A fox either accuses another fox or accuses every fox beside themselves. With this information, Ducktective can determine that if exactly T foxes are accusing a fox, that fox is guilty.

Given the list of foxes and their statements, help Ducktective determine who is guilty.

Input Specification

You will receive 1 + N lines of input. The first line of input will contain two positive space-separated integers N (3 \le N \le 10^5), the number of suspects and T (1 \le T \le N).

The next N lines will contain two positive integers. The first integer F (1 \le F \le N), represents the i^{th} fox. The next integer D represents their statement. There are two options for D. It can either be -1, meaning they are accusing every fox beside themselves, or it can be any integer from 1 to N, the number of the fox they are accusing.

Output Specification

On a single line, output the fox(es) who are guilty in increasing order. If it is inconclusive, i.e. no fox seems to be guilty, then print -1.

Sample Input 1

3 1
1 -1
2 3
3 -1

Sample Output 1


Sample Input 2

9 1
1 -1
2 1
3 1
4 1
5 1
6 1
7 8
8 7
9 1

Sample Output 2

2 3 4 5 6 9


  • 1
    faraz123  commented on July 7, 2020, 9:40 a.m.

    Their still has to be some mistake in the sample input. For sample input 1, fox 1 accuses 2 and 3, fox 2 accuses 3, and fox 3 accuses 1 and 2. In this case, fox 1 would have one accusation, fox 2 would have two accusations, and fox 3 would have two accusations. Since T = 1, all three foxes should be guilty (since their accusation amounts are greater than 1). Why is only fox 1 guilty then?

    • 2
      qwertytown4life  commented on July 7, 2020, 1:31 p.m.

      The problem states:

      Ducktective can determine that if 𝑇 foxes are accusing a fox, that fox is guilty.

      What is meant by this is that exactly T foxes must be accusing a fox for Ducktective to consider them guilty. The problem statement has been updated for clarity.

      Regardless, your solution is still wrong.

      (Hint: You don't take into account what happens if no fox seems to be guilty.)

  • 7
    d  commented on April 30, 2020, 10:47 p.m. edited

    It seems that the intended solution is not correct.

    For this test case

    5 2
    1 -1
    2 3
    3 4
    4 5
    5 2

    make sure that your program prints 2 3 4 5.

    Edit: The problem statement has been updated to be correct.

  • 2
    Kevy3030  commented on April 16, 2020, 4:19 p.m. edited

    Great problem!