# How to solve Single Point of Failure (Failure) from November Long 2019

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

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

A Simple solution for LSTBF using backtracking : https://www.codechef.com/viewsolution/27732112

4 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