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 
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 
1 Like
Nice! It is good to see people mostly liked this puzzle, except for the two people who really really hated it 
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.]
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 
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