sepiosky's blog

Solutions for Gym problems
By sepiosky, history, 9 years ago, In English

Hello :) from where I cant see solutions for problems that I hadnt solve , I want to ask solutions from peoples who solved this problems: 2015 ACM Amman Collegiate Programming Contest Problems :H,L . thanks :D

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

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

My solution for H:

First, find all bridges in the given graph, then remove them from the graph and find all components of the resulting graph.
Consider each component as a single vertex and add the bridges again, now you have a tree where all edges are bridges (in the original graph).
In the resulting tree, to make an edge not a bridge, it has to be in a cycle, and since all edges in this cycle won't become bridges anymore, you have to create the largest possible cycle, so find the longest path in the tree, and connect it's endpoints. Final answer is : Total number of bridges — length of resulting cycle + 1
Which is equal to : Total number of bridges — longest path in tree

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

    thank you ;)

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

    I implemented your solution, but it keeps getting wrong answer. Could you help me figure out the mistake in the code? It would be very helpful.

    Here is the link : http://ideone.com/XNdmzK

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

      Hello

      You are calculating the longest path incorrectly, for each node, you should find the farthest two nodes, then the longest path will be the maximum of the sum of these two paths for all nodes

      with this modification,your code gives AC now

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

H: build tree of biconnected components (2-edge-connected); after adding a single edge A-B to your original graph all bridges on path C(A)-C(B) in a tree (where C(X) is component in our tree which corresponds to X in original graph) will not be bridges anymore) Therefore you need to find such pair of vertices in a tree that distance between them is maximal, it can be done with two DFS. And you may not build a tree, but simply mark bridges in original graph and run Dijkstra instead of DFS. UPD. Or 0-1 bfs to reach better complexity, but Dijkstra also fits well :)

L: start with O(N^2) dp first. DP[i] — what is answer for prefix of length i. Transitions — try all possible positions of last cutpoint. Now let's improve it to NlogN. In order to reach NlogN it is enough to notice that valid cutpoints for position i form contiguous segment (except maybe one, i-1, which can be updated trivially). There should be "11" or "00" to the right from your cut (and this sets right border) and you can't cut at distance more than i-k (which sets left border). Now you should simply take minimum value among DP[l]...DP[r], which can be done with segment tree.

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

    Thank you very much for answers! I was very close to L but I dont Know why I didnt use segment tree :D

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

How to solve F.Travelling Salesman?

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

    You can use binary search. Try with number x, you can use every edge with Ci smaller or equal x. Now you build new graph with that edges and use dfs. If you mark all nodes try with smaller value else with higher.

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

    I built an MST and each time printed the maximum edge (largest) used in the MST.

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

This is my F: Traveling salesman submission 11947059, I use Dijkstra with priority queue,Why I always get TLE, can any friends please view my code 11947059 and debug help me! :) It mean this code: http://ideone.com/uwgIxL

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

    I am not expert for graph theory, but I don't understand why you use Dijkstra ? Only I see that maybe you try Dijkstra from every node, but it's so slow (n^2 log n).

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

      Oh, allllekssssa ,this problem mean we must visit every node and every node are connected, according to problem statment, I find one min path from node 1 to other node, and result is max cost between two node, together!

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

        I really don't know, but that graph isn't same with MST, and that shouldn't be correct solution.

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

    I didnt look at your code very careful but I thik you have missed a very important array and thats bool mark for vertices :/ But as you can see This you can easily solve this problem with a simple binary search and easy dfs ;)

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

      can u explain for me about detail of your solution: Binary search + DFS. I haven't understood yet :(?

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

        Consider that you want too check that answer can be an integer like ans Or not . For checking this case it is clear that you cant use an edge with weight bigger than ans and also you can use each edge that its weight is not greater than ans so you can check with dfs with condition : usin edges with weights not greater than ans after dfs if all vertices are marked ans can be the answer else not . From where if x can be answer numbers greater than x can be too you can find minimum answer with binary search on interval [0, 100000]

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

How to solve I?

→ Reply