Show all threads Hide all threads Show all messages Hide all messages |
How can this be solved? Can anyone help?(+) | asif | 1227. Rally Championship | 8 Oct 2020 20:56 | 11 |
Is there any polynomial time solution? I can WAZZAP 14 Nov 2002 16:52 > Is there any polynomial time solution? yes. - if there is a cycle the answer is always "yes" - if there is a knot (ex. 2 2 edges), the answer is also "yes" - if graph is multigraph, yes too if all above is false just find the longest path in a tree and play with it's value in comparsion with route length > > Is there any polynomial time solution? > yes. > > - if there is a cycle the answer is always "yes" > - if there is a knot (ex. 2 2 edges), the answer is also "yes" > - if graph is multigraph, yes too "multigraph" : what is it? I got WA so many times,any trick? > > if all above is false just find the longest path in a tree and > play with it's value in comparsion with route length > > Thanks. I did not read the question well enough and thought that the race must start and end on vertices. How stupid of me! That is why I asked that stupid polynomial question. > > > Is there any polynomial time solution? > > yes. > > > > - if there is a cycle the answer is always "yes" > > - if there is a knot (ex. 2 2 edges), the answer is also "yes" > > - if graph is multigraph, yes too > "multigraph" : what is it? I got WA so many times,any trick? > > > > if all above is false just find the longest path in a tree and > > play with it's value in comparsion with route length > > > > Edited by author 23.07.2008 05:54 > "multigraph" : what is it? I got WA so many times,any trick? multigraph can have more than one edge connecting 2 vertices. Those edges can have different length. So, if there are two or more edges, connecting 2 vertices, this is just another cycle. This task is quite tricky and not well-right from the point of diskrete maths. For example, non-oriented graph can not have knots (by the difinition), but in this problem this is one of the "triks". but how to judge whether there's a cycle? do DFs and if there a return edge than u have a circle or do n Dijkstra's and if u can get back to the point than u have a circle I can't understand why if there is cycle, the answer is always yes -> what about this test: 3 3 1000 1 2 3 2 3 3 1 3 3 Edited by author 21.07.2009 12:43 Why YES? Petr Huggy (Pskov) 21 Nov 2010 12:32 Because there is a cycle with length 9, and we can ride this path unlimited number of times. "The race may start and finish anyplace on the road" |
WA 3 | So Sui Ming | 1227. Rally Championship | 18 Dec 2019 12:00 | 3 |
WA 3 So Sui Ming 6 Sep 2017 11:01 I passed all test cases mentioned in the discussion. There are 4 tests in my algorithm: - is there a loop (from M and N) ? - is the graph connected ? - is there a cycle? - for each component of the graph: find the longest path and compare the length with S any hint? Edited by author 06.09.2017 11:02 Edited by author 06.09.2017 11:02 i had problems with 3rd test case. this input should help you: 1 1 5 1 1 2 the key here was to look closely at restrictions: 1 ≤ M ≤ 100; 1 ≤ N ≤ 10 000 assuming there could not be several ways from different x and y, and no loops from x to x, there should be at most 4950 connections between cities 3rd test contains road from X to X, so answer is "YES" |
In case you have WA7 | Ilistratov | 1227. Rally Championship | 28 Oct 2019 20:09 | 1 |
Graph can have loops and multiple edges. Edited by author 28.10.2019 20:10 |
WA#17 Help, please | Ann | 1227. Rally Championship | 19 Mar 2019 00:15 | 1 |
An example from other discussions: input: 4 3 12 1 2 5 1 3 4 3 4 4 output: YES displays the correct answer. Tell me more examples, please. In the algorithm, I check loops, two-way roads, cycles, and then look for a way longer than necessary. UPD: WA#18 Edited by author 20.03.2019 19:17 |
WA#18 | Bogolyubkiy | 1227. Rally Championship | 17 Sep 2017 19:32 | 2 |
WA#18 Bogolyubkiy 4 May 2010 19:20 Can you suggest an example for this test? 4 3 40 1 2 10 2 3 20 2 4 20 Right answer: YES |
Some Hint : | Adhambek | 1227. Rally Championship | 10 Nov 2014 13:58 | 1 |
you can use to check "YES" that simple DSU algorithm. because DSU algorithm gives us all cycle, knot, multigraph ... so on
|
If you have WA 11 or WA 17 | Mamuka Sakhelashvili [Freeuni] | 1227. Rally Championship | 16 Feb 2014 22:46 | 1 |
try this test input: 4 3 12 1 2 5 1 3 4 3 4 4 output: YES |
WA 12 | Hristian Hristov | 1227. Rally Championship | 4 Oct 2011 02:23 | 1 |
WA 12 Hristian Hristov 4 Oct 2011 02:23 Can you give me some tests. I check if it is multigraph and if there are cycles. After that I get the longest path and if it is lower than S I ouput NO. But still WA :( |
Why WA#9? | Lucifer | 1227. Rally Championship | 1 Dec 2010 19:49 | 2 |
try this: input: 3 2 12 1 2 10 2 3 5 output: YES if you WA#17 try this: input: 4 3 12 1 2 5 1 3 4 3 4 4 output: YES GOOD LUCK!!! |
Pls answer me! | Rostislav | 1227. Rally Championship | 5 Nov 2008 19:47 | 5 |
What is the output? 1 1 3 1 1 2 |
To admins | Loky_Yuri [USTU] | 1227. Rally Championship | 13 Jul 2007 01:45 | 2 |
Rather simple tests… For this test my AC program gives “NO”: 4 2 13 1 2 15 3 4 10 But the correct answer is YES. So as I understood, in all your tests, if graph is unconnected and there is no cycle in it, then the max length of path always contain the last (m) vertex… So all programs which use this algorithm passed all your tests: First, check knots, multigraph; Second, for (I, 1, n) - check is the i vertex is in the circle; Third, find the max length of path of that tree, which contain the last vertex; and compare it with s. INSTEAD: Third, find the max length of paths ALL TREES, and all of them compare with s. Sorry for my English. |
Be careful that the graph isn't necessarily connected! | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1227. Rally Championship | 22 Oct 2004 05:03 | 1 |
|