[Community Puzzle] Drug Interactions

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @Westicles,validated by @romain.wg,@abbecool and @Miki09.
If you have any issues, feel free to ping them.

1 Like

Is ‘A’ and ‘a’ regarded as “common”? It is undefined.

1 Like

There was the same question in contribution, without answer.

Yes, ‘a’ and ‘A’ are indeed the same letter. Surely you knew :slight_smile:

Edit: Joking aside, I clarified it in the text.

Surely you knew it should have been written.

3 Likes

Maybe it is a language thing? In English it is very clear as originally written… they are the same letter, but different characters.

If people ask for it, here and in the contribution page, it’s because it’s not clear.
It’s not because it’s clear for you that it’s clear for anybody else. You don’t publish a puzzle only for you.

Moreover, I don’t know if a common repeated letter is counted only once or not. It’s not in the statement.
One last thing: it does not seem to me that it’s a medium puzzle.

Maybe you kept your tab open and didn’t see it but the statement has been updated yesterday evening about repeating letters and now it’s fine.

I think it would be medium without a doubt with a slightly smaller n but with the current n I couldn’t complete it in python with a basic algo, I had to use additionnal tricks to pass testcase 5 (sorting and early breaks).
So it makes it medium++ for “slow” languages.

3 Likes

I solve it with python3 and c++ with the same basic approach, without sorting or early breaks.
But I agree, it’s between medium and hard problem.

1 Like

I you don’t mind sharing your solution - not here ofc but in the dedicated section, I’ll take a look at it.
Edit : I found a faster solution than my previous one that uses set intersection, it might be what you were thinking of. It doesn’t require sorting and early break indeed and is quite short.

1 Like

Done, I used only one simple recursive function :slightly_smiling_face:

1 Like

Nice! It is good to see people mostly liked this puzzle, except for the two people who really really hated it :stuck_out_tongue:

It’s not a question of hate but a question of clarity.

Cool problem! I do agree that it was harder than the majority of medium-level problems.

My solution uses a recursive greedy approach with memoization. Though I basically had the correct approach early on, I kept failing on the final validator despite the fact that all of the tests were passing. If anyone else is having this issue, try the following test case:

9
abcxxx
defyyy
ghizzz
abcdefghi
xxxyyyzzz
xxxyyyzzz
xxxyyyzzz
xxxyyyzzz
xxxyyyzzz

The output should be 3 (my original algorithm would output 2).

2 Likes

I used greedy principle to re-order and trim off less possible nodes so as to reduce search space. It reduced processing time from some seconds to a flash. However it tends to give only an approximation of the correct answer when the data set is large.

After some days and nights of trial, finally I found that the easiest way is still to bruteforce it. Focus on optimizing the data structure, heavy use of hashing to reduce search time, and preventing re-calculation of intermediate results, combined to reduce processing time to stay well below the time limit.

Quite a nice exercise.

2 Likes

I think it would be a good idea to mention clique problem anywhere in the problem, so that learners wont be so lost:

Hello,

I search a long time and reach 80% with two different algorithm.

Some documentations about clique:

(same site (can’t put more than 2 links in my post) → /bron-kerbosch-algorithm/ )

Honestly, I think it is a hard problem!

Unless I’m mistaken, I’m not sure there is an optimal solution for any data set.
For me, everything will depend on the order in which we run our algorithm.

Can you help ?
→ [Forum thread for this problem] [Mod edit: Don’t open a separate thread when a thread already exists for a puzzle.]

@Ryuuk
@java_coffee_cup

Thank you in advance

1 Like

Hello!

I have been looking for a long time for a solution to the following problem without success.

I search about clique (graph theory).
For me the problem is to find the biggest complete sub-graph from the graph.
Graph is composed from vertices (drug) and undirected edges (link to other compatible drug).

The only algorithm that works for me (bruteforce) is bron-kerbosch algorithm, O(3^(V/3)) : Using Bron Kerbosch algorithm to find maximal cliques in O(3^(N/3))
Of course, for V=100 (Test 5) it is impossible to process in convenable time.

The second algorithm (greedy approach) miss some solution, O(V^2).
(same site → /greedy-approach-to-find-single-maximal-clique/ )

I eliminate node with 0 edges ; and try to sort (reverse) to have the vertices with the most edges.
I reached 80% with greedy approach but for me it is not robust, it depend on the order.

If you have some leads or/and you can help for this puzzle, it would be great!!

Thank you in advance :slight_smile:

1 Like

Outstanding puzzle! Don’t give up if you’re still working on it. I understood almost none of what I read about maximal clique problems. I couldn’t figure out how to use memoization or the Bron Kerbosch algorithm. Somehow I got lucky early on and passed all the test cases, but I could only pass 60% of the validators and I had to start over. Then I got to 80% of the validators and I realized I had to start over again.

I finally had success when I focused on my looping technique and my recursion. There are a lot of combinations that can be explored. I eventually passed everything when I made sure I was pruning my options as much as possible before every recursive call used to add one more drug to the compatible group.

1 Like