Nice @ssjgz, looks like LSTBTF required a lot of manual analysis. I thought there is some celever optimisation over DP as DP would have obviously time out.
1 Like
The analysis is mainly complexity analysis - someone who just trusted their intuition about how quickly it would terminate would probably get AC without doing any of it 
2 Likes
You can do it using dp too. Give atleast one to each digit. Next check the smallest square can be represented by some linear combination of 1,3,8,15,24,35,48,63 and 80. To optimize it you can use dp on length of the sequences. Suppose if a got a combination using 1,3,8 then I dont have to look for length more than 3.
1 Like
Yup, it now makes sense as you don’t have to move too forward, as per @ssjgz 's solution, the next square would be found very quickly. So, I think it would work if we start checking for next squares.
1 Like
thanks,your codes are always clean.
2 Likes
Has anyone solved MDSWIN by finding the basis of the vector space, if we represent thresholds as a vector over Z3.
I first solved it first using the brute force approach that gave 50 points. First of all the graph needs to be robust, else the answer is -1. Then to optimise it
1.The intuitive approach is to reduce the graph, which means you can remove the portions which are not in the cycle. For this I used BFS, by pushing all the leaf nodes first in the queue. Leaf nodes are the ones which have degree one.
2. After the step 1, you can find the vertex with maximum degree, obviously you can update the degree at the same time during graph reduction.
3. Check the naive brute force cycle check on this single vertex, if you want to get the minimum number with max degree you can iterate all the N vertices and if you get the graph non robust then you can terminate, else the answer is -1.
Hope this helps.
Basically i also used the same three nested loop technique but getting a TLE so is there any good method without three nested loops
You are doing a great job. Thanks…!
3 Likes
Wow - that is simple - there’s hardly any code there at all!
3 Likes
Beautiful editorials man !
Brilliant performance as always! Congratulations on getting to 6 stars! 2 months and you’re red!
3 Likes
Red is way beyond me unless I get a heck of a lot smarter
Many thanks for the kind words! 
2 Likes
Very elegant, so cool. This is should be the official editorial.
2 Likes
@ritik_gajjar let’s take this graph:
1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> 1
According to you every node is contributing in two cycles? Or am i missing something?
Got it. By the way my intension was to ask if there is a way to find for a node in exactly how many cycles it belongs to.
I solved this problem by removing bridges.
most of people solved by removing bridges.
My idea is - find a cycle (any if found - O(E) ) our SPF must be in this cycle (if present) remove the edges involved in this cycle and for every vertex in this cycle run DFS by a common visited check-up array .
This may lead to ( for each vertex in cycle)
1. a rooted tree with this vertex as root
2. may end-up visiting some vertex(s) in this cycle
3. may lead to a a sub-graph with cycle
(-guess the checks in these cases)
this total time - O(E) 
(not implemented)
Is this weak test cases or correct solution.
For “Failure”.
What I did was find all biconnected components. And use DSU to check if two edges are in same biconnected component or not.
Then for each node we need to find the number of connected components the graph will have if we remove current node.
For finding that we find number of different biconnected components beside current node.
Then it’s just logical check ( each tree will have n-1 edges property)
This will be Delta of initial connected component for each node.