4 kyu

Detective, ¡find the suspects!

34Donvito-911
Description
Loading description...
Graphs
Algorithms
Performance
View
AllIssues4Questions2Suggestions1Show Resolved
  • Please sign in or sign up to leave a comment.
  • ahmet_popaj Avatar

    Nice kata, this one is quite challenging indeed.

  • DaveyJH Avatar

    Could someone advise whether I am misinterpreting the instructions, or whether this is an incorrect test:

    # printed args (with multiple lines of the data arg removed to make it more concise)
data = [
    ...,
    (92, 3231),
    (2332, 92),  # used in P  # 2332 is a friend of the prince
    (92, 7178),
    (8138, 8473),
    (92, 2690),
    (9248, 2332),
    (92, 9883),
    (92, 5203),
    (698, 4683),
    (698, 4515),
    (81, 5122),
    (81, 1537),
    (5290, 1858),
    (9782, 5290),  # used in P
    (5290, 698),  # used in P
    (698, 3582),
    (698, 1922),
    (81, 92),  # used in P
    (81, 6645),
    (9782, 2332),  # used in P
    (8138, 4800),
    (81, 6611),
    ...,
]
prince_id = 92
thief_id = 698

    The test result says 81 (among other similar examples) should be included in the output.

    The rows with # used in P noted appear to be used in a path ([698, 5290, 9782, 2332, 92, 81]) which contains a friend of the prince (2332). This leads me to believe the ID of 81 should not be included as per the formula in this section in the instructions:

    To explain this mathematically, denote FF as the set of friends of the prince. Let f∈Ff \in F be the friend of the prince and tt the thief of the treasure. Now, denote Pft=p1,…,pnP^t_f = { p_1, \dots, p_n} as the set of all the people in a friendships path between tt and ff excluding them. ff is a suspect if and only if there is a path between tt and ff:

    t→p1→p2→⋯→pn→ft → p_1 → p_2 → \dots → p_n → f such that for all p∈Pftp \in P^t_f , p∉Fp \notin F

    Is it simply that the end of the formula is not accurate (p∉F p \notin F ), or am I mistaken?

  • Blind4Basics Avatar

    The fixed tests are not fixed, they are relying on the ref solution. Meaning if the ref solution is wrong, there is no guarantee on the specs. At all.

    Also, the fixed tests should hold all the needed data for each test in one place: input data, princ and thief ids, and also the expected output. The sample tests need to also be updated with this.

  • Blind4Basics Avatar

    Who the hell reviewed the random tests and didn't notice THIS:

    def create_subgraph(id_, amount_friends, not_possible = set()):
                                       # ^^^^^^^^^^^^^^^^^^^^
  • Blind4Basics Avatar

    Hi,

    Something isn't specified "correctly", apparently, but more importantly, the efficiency tests are using some outputs that are built entirely differently of all the other tests (edit: that, or the problematic case comes up more frequently when the number of nodes is huge): I currenlty have a solution (fast enough) that is passing all the tests, but returns wrong results on some efficiency tests only. Problem being: how am I supposed to find the hidden spec/stuff I misunderstood on inputs with more than 4000 nodes...?

    • Blind4Basics Avatar

      some other solutions are only passing the tests from time to time (the current top solution, for example) => something is wrong somewhere.

      Note: according to the description ("algorithmic side"), a friendship path thief -> prince -> firend of prince make all of them suspect, while this doesnt look right because the thief himself is a friend (not that problematic), but this also means there is another friend in the friendship path, meaning none can be suspected...? eidt: mmh, the thief is excluded, so I guess that part is ok, but this situation still looks pretty weird. A clarification and a specific fixed test for that is needed, at the very least.

    • KayleighWasTaken Avatar

      Also complete lack of specification regarding expected time complexity etc.

  • wzy1935 Avatar

    This comment has been hidden.

  • Avanta Avatar

    This comment has been hidden.

  • 66 Avatar

    Performance tag should be mentioned?

  • Voile Avatar

    Initial code arguments are missing the other two arguments (the prince and the thief).