stould's blog

Can you find an easier way to solve ?
By stould, history, 9 years ago, In English

Hello guys. I'm trying to solve the problem Circuits from spoj. After think a lot, I found a greedy solution to solve this problem, follow

'Supposing all components have no cycles yet'
1) Separate all components
2) Get the component with less vertices and the component with most vertices.
3) Merge this two componentes this way:
A = first component
B = second component
From A, get the two vertices (may be the same vertex) that have the greater distante.
From B, the same thing.
4) Create a link (connect the vertices from A and B) between this four vertices:
graph[A[0]].push_back(B[0]);
graph[B[0]].push_back(A[0]);
graph[A[1]].push_back(B[1]);
graph[B[1]].push_back(A[1]);
5) Find the formed cycle (and all vertices on the cycle)
6) For each node in the cycle:
If the node have all the neighbors in the cycle, I just remove it.
7) Generate again the componentes, and the process repeats until I find nodes without a cycle.

I guess this algorithm above work fine (at least I tested in several cases). But it is very complicated.

Does anyone agree with this solution or I can do something easier ? Sorry for the long text and my poor english.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

40 hours passed and nobody got interested! I think, you should change the blog title to get the answer.

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

I think to the condition be fulfilled every vertex must be connected to at least 2 edges. This way, we only need to store the ones with less than 2 edges into a container and add edges to them (just increase their degree). Note that it's always good to add a edge between vertices in this condition (less than 2 edges). The final answer should be the number of added edges.

I haven't coded the problem, so my thinking may be wrong. Any suggestions/thoughts are welcome.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I guess this problem is not so simple, look at this test case:

    6 4
1 2
1 3
3 4
5 6

    The answer is 2(linking vertex 2-6 and 4-5). Using your strategy, what vertex should I choose to do that ?

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wrote this algorithm Solution, my solution fails in the first test case (the answer should be 1).

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 10   Vote: I like it +3 Vote: I do not like it

    I Think your solution is wrong because I have a counter example in which every vertex has degree 2 or 3 but answer is not 0

    n = 7

    m = 8

    edges :

      1 , 2

     2 , 3

    1 , 3

    3 , 4

    4 , 5

    5 , 6

    6 , 7

    7 , 5

    UP : It was really interesting when I read the comments in problem page on spoj ! because some one said my example in comments there ! but I really didn't copy the example from there !

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yeah, the strategy is definitely wrong.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      Oh yes, this solution is wrong. I found a test case that it never works. Also, me and a friend, we find the solution. Haha it is amazing.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Could you explain how the correct strategy works?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Yes, I just need to implement, but I'm almost sure that it works: The first thing is to see that the bridges is the key to solve. After get the bridges, you have to separate the componentes and compress them (if a edge is not a bridge, compress). After this, you have a tree. Now I guess you can get the answer.

          → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I generated several test cases, a little later I send the expected answers for those tests.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried to solve this problem for a couple of hours and couldn't come up with anything. I thought max-flow, greedy, I even thought of that "degree of at least 2" solution, but none of them worked.

Moreover, this problem is from Argentinian National Tournament 2011, and no one solved it there either, so it looks like it's indeed pretty hard.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is not too hard as you think. :) I've spent a lot of hours in this problem too..

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Try something involving 'bridges'.. I hope it help. See my comment above.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The correct answers: http://pastebin.com/h1thArsT

→ Reply