solved it after googling for some help. warning to all - this kata is basically a "trick" question. the answer isn't particularly interesting, and you won't learn anything, really. this is niche, pure computer science problem rooted in mathematics.

no problem. just a crappy kata with a single correct answer. there is no creativity involved in solving this. thanks for your response, i appreciate you volunteering your time to the community and responding to my complaint.

From your complaint I cannot really figure out what is the problem here. Your solution does not pass tests, so it is not valid. It consistently fails the "Efficiency tests (up to 2^30)" group. It seems to be simply too slow.

So what is the problem here?

it is not necesary to iterate over the input array in any way. i literally del cycle_list and run my code. (python). even imported gc and did a garbage collect after deleting the input list.

i have my code passing fixed, random and both efficiency tests (2^20 and 2^30). so clearly the algo i've hit upon is valid.

however i get
STDERR
Execution Timed Out (12000 ms)

overall, a pretty crap exercise for a 7 kyu rating. this is a platform limitation.

Nice kata, this one is quite challenging indeed.

I like these sorts of katas very much.

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 $F$ as the set of friends of the prince.
Let $f \in F$ be the friend of the prince and $t$ the thief of the treasure. Now,
denote $P^t_f = { p_1, \dots, p_n}$ as the set of all the people in a
friendships path between $t$ and $f$ excluding them. $f$ is a suspect if and
only if there is a path between $t$ and $f$:

$t → p_1 → p_2 → \dots → p_n → f$ such that for all $p \in P^t_f$ , $p \notin F$

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

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.

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

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

Also complete lack of specification regarding expected time complexity etc.

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.

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...?

Sad that this is still lingering in beta. This is an awesome kata! You have to be willing to do the research into the solution. If you can't figure it out on your own -- I couldn't! -- go looking for the "Futurama Theorem." I found a PDF from a teacher who demonstrated the solution by using their students in a live demo. Then I just turned the teacher's live demo into code. I won't say any more, or I'll be flamed for saying too much.

Some dissatisfied with the task, because in the tests there is a performance test for 7 kyu kata, with a very large number of items. Unlike the actual implementation of the algorithm, which is described in detail, you need to do the math. It takes away the ability to implement The algorithm.