Show all threads Hide all threads Show all messages Hide all messages |
WA 32 ...why this method is wrong | Sagar Goyal | 2034. Caravans | 12 Dec 2022 03:21 | 3 |
Out of all shortest path I am finding min of maximum distance I have to travel for every level. #include<bits/stdc++.h> using namespace std; void bfs(int u,vector<int> &d,const vector<vector<int>> adj){ d[u] = 0; queue<int> q; q.push(u); while(!q.empty()){ int u = q.front(); q.pop(); for(auto v:adj[u]){ if(d[v]>d[u]+1){ d[v]=d[u]+1; q.push(v); } } } } int main(){ int n,m; cin>>n>>m; vector<vector<int>> adj(n); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; adj[u-1].push_back(v-1); adj[v-1].push_back(u-1); } vector<int> ds(n,1e9),df(n,1e9),dr(n,1e9); int s,f,r; cin>>s>>f>>r; s--,f--,r--; bfs(s,ds,adj); bfs(f,df,adj); bfs(r,dr,adj); vector<vector<int>> l(ds[f]+1); for(int i=0;i<n;i++){ if(ds[i]+df[i]==ds[f]){ l[ds[i]].push_back(i); } } int ans = INT_MAX; for(int i=0;i<=ds[f];i++){ int a = INT_MIN; for(auto x: l[i]){ a = max(a,dr[x]); } ans = min(a,ans); } cout<<ans; return 0; } This is wrong because you're assuming that the answer is the minimum distance to the robbers in its unique optimal path, which is not always true. Edited by author 17.08.2022 04:41 Edited by author 17.08.2022 04:41 Consider this test: 9 12 1 2 1 3 2 4 2 5 3 6 3 7 4 6 4 9 5 6 6 8 7 8 7 9 1 9 6 Correct answer: 1 (shortest path is either 1-2-4-9 or 1-3-7-9, so robbers can move 6-4 or 6-3) |
WA on 25 | Rami Ismael | 2034. Caravans | 31 Oct 2022 13:57 | 2 |
if u used min max things and O(n) algorithm. WHEN u have found the point where two shortest paths converge. You need to save distance from this point to r AND when u do MAX(the point,your new path) u need also do min(the point, very old distance in this point). |
if you have #WA 8 ... try this test case... | Adhambek | 2034. Caravans | 22 Apr 2022 13:45 | 5 |
6 6 1 2 2 3 3 4 4 5 1 6 6 5 1 5 6 ans : 0 oh,no!my answer is 0 but WA in test 8...... Actually it's 0. We should stay in 6, since there is only 1 shortest path. I have an another test case: 8 8 1 2 1 6 2 4 6 7 3 4 4 5 7 8 5 8 1 8 3 Answer: 3 |
Weak Test cases | sagsango | 2034. Caravans | 23 Sep 2020 15:44 | 3 |
For this Test case , AC solution gives output 2 which should be 1. 25 28 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 1 5 19 19 20 20 21 21 22 22 23 23 24 24 25 25 14 15 22 6 22 1 10 22 Edited by author 20.02.2020 05:33 Edited by author 20.02.2020 05:33 is 1 the correct answer ? Nvm Edited by author 23.09.2020 15:53 |
test 2 | Arseniy | 2034. Caravans | 16 Sep 2020 21:58 | 3 |
test 2 Arseniy 30 Mar 2016 00:22 I figured out that n == 8 in test 2. It may be useful for somebody. I got my problem I erased from multiset in a wrong way what is the whole test case ? . i am getting wrong answer on test case 2 ! |
What's problem with my algo??? | gio_gio | 2034. Caravans | 16 Sep 2020 21:51 | 7 |
I run 2 bfs. The first bfs starting from node S (that is caravan's distances) and the second starting from node R (that's distances from robbers). Then i recover route for caravan and on each step backward i choose node with maximum robber distance. Minimum of robber distance on the caravans path is the answer. What's wrong? It's because you can't greedily choose the node with the maximum robber distance. One of the other paths might contain a node with a smaller node distance somewhere further along. One such graph is here (this one is rather long, you probably just want to try to generate a graph that violates your greedy strategy yourself): 15 20 1 2 2 4 4 6 6 8 1 3 3 5 5 7 7 6 4 5 2 3 7 8 7 9 9 10 10 11 11 12 12 6 11 14 14 13 13 15 15 3 1 8 11 One strategy that works is to BFS backwards from the finishing vertex, and along each path you maintain the minimum robber distance. When two (or more) paths merge on some vertex, you consider the minimum of this path to be the maximum of the minimums of the two paths. Otrebus, thank you for strategy ! what will be the ans of this case, could you tell me please??? i am also getting 3 for this case but wrong answer on test case #2 .. |
WA8: hint | KostyaRychkov | 2034. Caravans | 3 Aug 2020 17:58 | 1 |
Check that you use only shortest routes. I don't have any tests, but when I started checking this, then I got ACC. |
if you have #WA 13 ... try this test case... | Aristarch | 2034. Caravans | 5 Jul 2020 02:37 | 3 |
15 17 1 2 2 3 3 4 4 5 5 6 6 14 14 15 15 9 9 7 7 5 7 8 8 13 13 12 11 12 10 11 10 4 1 6 1 12 15 ans: 3 @Aristarch I also get 3 as ans. But , still getting WA in test case 13. |
Weak test case | zigzog | 2034. Caravans | 3 Jul 2020 20:12 | 1 |
I checked two accepted solution But They are giving different output in same test case. AC code 1: https://paste.ubuntu.com/p/RwtFH2s4xK/AC code 2: https://paste.ubuntu.com/p/vmrXrdcJN6/ Tese case : 25 28 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 1 5 19 19 20 20 21 21 22 22 23 23 24 24 25 25 14 15 22 6 22 1 10 21 Output in code 1 : 2 Output in code 2 : 3 Answer should be : 2 |
hint | ajay jadhav | 2034. Caravans | 11 May 2020 23:21 | 1 |
hint ajay jadhav 11 May 2020 23:21 robbers dont know the path, so at each point take farthest node from robbers.do these fo for the length of shortest path and in the end take minimum of these. |
TL 12 | Arseniy | 2034. Caravans | 25 Nov 2018 00:30 | 2 |
TL 12 Arseniy 23 Apr 2016 22:06 My O(N * log N + M) solutions gets TL What I'm doing wrong? Have somebody any tests? please! |
Hint. | ag2cidk | 2034. Caravans | 14 Jul 2018 05:22 | 1 |
Hint. ag2cidk 14 Jul 2018 05:22 BinSearch. Edited by author 14.07.2018 05:22 |
Test case 2 | Wei Zhang | 2034. Caravans | 20 Feb 2018 22:49 | 1 |
What is the second test case? |
WA on Case#14 | Iftekher Toufique Imam | 2034. Caravans | 23 Jan 2018 20:14 | 1 |
Passed all the test given in the discussion I ran 1 bfs from 'r' and another bfs from 's' where i also kept data for those nodes who can have multiple parents. than I while restoring path from destination to source I selected the node who has higher level from 'r' (that selection occurs if only the node has possibility multiple parents) returned the ans which is the minimum among the final path |
WA 5 any test example pls/ | shota | 2034. Caravans | 18 Oct 2017 22:40 | 2 |
Just invent some algorithm and prove your algorithm is correct That is prove that your algorithm finds the answer I remember initially my algorithm was correct but consumed too much memory So final algorithm was different |
Try to consider vertices with the same distance to f from s | Mahilewets Nikita [BSUIR] | 2034. Caravans | 10 Aug 2017 10:54 | 1 |
|
I was waiting for this task for tzwo years | Kergan | 2034. Caravans | 8 Feb 2016 20:19 | 2 |
Where did you see it before? |
TLE at test case #9 | jacketinsysu | 2034. Caravans | 27 Aug 2015 14:57 | 1 |
I use bfs...but record the route in a map, and maybe the copy of the map cost too much time... How can I get all the routes in another good way? |
WA #3 | Elias | 2034. Caravans | 3 Jun 2015 23:30 | 1 |
WA #3 Elias 3 Jun 2015 23:30 Does someone have any idea what's test 3? |
Momory limit! | kerpoo | 2034. Caravans | 21 Mar 2015 14:18 | 1 |
The memory limit is terrible! so small! Increase it plz!!! Edited by author 21.03.2015 14:43 |