Someone mind sharing their approach. @ssjgz
2 Likes
I used tarjan’s bridge finding algorithm to remove bridges. Then find the node with max degree and lowest value…remove it then…if the graph becomes acyclic… that’s the node…else -1
7 Likes
Its quite simple, really.
Step 1: Does the graph have a cycle? If not print -1.
Step 2: Remove all bridges. Then each and every edge will be part of a cycle.
Step 3: Find out the vertex with most .edges. If there are multiple choose the smallest such vertex
Step 4: Delete the vertex and remove all its edges.
Step 5: Does graph still have a cycle? If so, print -1. If not, print vertex number.
7 Likes
Here’s all of mine - the write-ups are a bit rushed this time, alas, and I’m quite certain my approach to FAILURE is more complex than it should be.
Nonetheless:
FAILURE - “Single Point of Failure” - documented code; Editorial-style overview
WEIRDO - “From Zero to Infinity” - documented code; Editorial-style overview
CAMC - “Chef and Minimum Colouring” - documented code; Editorial-style overview
LSTBTF - “Smallest Beautiful Number” - documented code; 95% complete Editorial-style overview (missing full explanation of why it terminates as quickly as it does, though contains plenty of hints :))
PHCUL - “Physical Exercise” - documented code; Editorial-style overview
12 Likes
Will your idea work for this input:
nodes = 10, edges = 11
1 - 4
2 - 4
3 - 4
4 - 10
4 - 8
8 - 10
8 - 9
9 - 10
9 - 5
9 - 6
9 - 7
1 Like
Yes. Remove node number 8.
Another approach: To check if a connected component has a cycle or not, #edges should be more than n-1. Then find the smallest articulation point after removing which the graph can be decomposed into atleast one component having cycles. This can be done using a dfs which stores the number of edges and vertices in its dfs-subtree.
2 Likes
Ya, I got it. edge 8 - 10 won’t be removed.
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