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
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
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
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
thank you ;)
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
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
Thank You so much. It really helped :)
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.
Thank you very much for answers! I was very close to L but I dont Know why I didnt use segment tree :D
How to solve F.Travelling Salesman?
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.
I built an MST and each time printed the maximum edge (largest) used in the MST.
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
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).
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!
I really don't know, but that graph isn't same with MST, and that shouldn't be correct solution.
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 ;)
can u explain for me about detail of your solution: Binary search + DFS. I haven't understood yet :(?
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]
How to solve I?
http://mirror.codeforces.com/blog/entry/19115