i couldn't understand, why my programm got Runtime error 15. When i increased MAXN from 1e4 + 10 to 1e5 + 10, i got AC. So the vertices number are in the range [1, 1e5], but not in [1, 1e4], as written in the statement I got stuck with RE#15 (dp+dfs). Non-recursive algo with same idea got AC. Hope this information helped. Maybe someone could explain why I'm still getting WA 13? On all of tests in this forum i get right answers. Can anyone give more tests? I just figured out that I got WA13 because I assumed that if I get to each node with the minimum steps,I can eventually got to the end point with minimum steps.But this is not always true. Try This test 9 1 2 3 4 1 3 5 6 4 The answers is obviously 1 2 3 4.But my WA13 programme gave the answer 1 3 5 6 4 Hope this helps. I have WA 13 too, but i have correct answer for this test For WA3 try this: 3 1 2 1 Ans: 1 For WA12 try this: 5 1 2 3 1 5 Ans: 1 5 We have correct answers but on test 7 we have wrong answer Edited by author 08.05.2020 21:50 17 1 2 3 4 5 6 7 2 8 9 5 10 8 9 11 3 9 1 2 8 9 1 2 3 9 ?????????????????????????????????????? Give me this test My solution give correct answer on all test in topic WA test 7, but i have WA test 5 from judge system. 12 1 2 3 4 2 1 5 8 9 2 10 6 Correct answer: 1 2 10 6 8 1 2 3 4 5 2 3 6 answer: 1 2 3 6 Please help #include <bits/stdc++.h> using namespace std; const int infInt = 1<<30; vector<int>adj[100010]; pair<int,int> edges[100010]; int parent[100010],dist[100010]; map< pair<int,int> ,int> Map; bool mark[100010]; void path(int u){ if(parent[u]==u){ cout<<edges[u].first<<" "<<edges[u].second; return; } path(parent[u]); cout<<" "<<edges[u].second; } int main(){ int ant,curr,root,n; cin>>n; for(int i=0;i<n;i++){ cin>>curr; if(i>0){ edges[i].first=ant; edges[i].second=curr; adj[ant].push_back(curr); Map[make_pair(ant,curr)]=i; } if(i==0) root=curr; ant=curr; } if(root==curr){ cout<<root<<endl; return 0; } queue<int> q; for(int i=1;i<n;i++){ parent[i]=i; dist[i]=infInt; if(edges[i].first==root){ q.push(i); dist[i]=0; } if(edges[i].second==curr) mark[i]=true; }
while(!q.empty()){ int u=q.front(); q.pop(); int x=edges[u].first; int y=edges[u].second; for(auto z: adj[y]){ int v=Map[make_pair(y,z)]; if(v>u and dist[v]>dist[u]+1){ dist[v]=dist[u]+1; parent[v]=u; q.push(v); } } } int best=infInt,bestInd=-1; for(int i=1;i<n;i++){ if(dist[i]<best and mark[i]){ bestInd=i; best=dist[i]; } } path(bestInd); cout<<endl; return 0; } Or this, aldo wa 15 What´s the problem?? #include <bits/stdc++.h> using namespace std; const int infInt = 1e9; vector<int>adj[100010]; pair<int,int> edges[100010]; int final; map< pair<int,int> ,int> Map; bool mark[100010]; bool vis[100010]; int dp[100010]; int f(int u){ if(edges[u].second==final)return 0; if(vis[u])return dp[u]; vis[u]=true; int x=edges[u].first; int y=edges[u].second; int ans=infInt; for(auto z:adj[y]){ int v=Map[make_pair(y,z)]; if(v>u) ans=min(ans,1+f(v)); } return dp[u]=ans; } void rec(int u){ if(edges[u].second==final){ cout<<" "<<final<<endl; return; } int x=edges[u].first; int y=edges[u].second; for(auto z:adj[y]){ int v=Map[make_pair(y,z)]; if(v>u and dp[u]==1+f(v)){ cout<<" "<<y; rec(v); break; } } } int main(){ int ant,curr,root,n; cin>>n; for(int i=0;i<n;i++){ cin>>curr; if(i>0){ edges[i].first=ant; edges[i].second=curr; adj[ant].push_back(curr); Map[make_pair(ant,curr)]=i; } if(i==0) root=curr; ant=curr; if(i==n-1) final=curr; } if(root==curr){ cout<<root<<endl; return 0; } int best=infInt,bestInd=-1; for(int i=1;i<n;i++){ if(edges[i].first==root){ int ans=f(i); if(ans < best){ best=ans; bestInd=i; } } } cout<<edges[bestInd].first; rec(bestInd); } Please help #include <bits/stdc++.h> using namespace std; const int infInt = 1<<30; vector<int>adj[100010]; pair<int,int> edges[100010]; int parent[100010],dist[100010]; map< pair<int,int> ,int> Map; bool mark[100010]; void path(int u){ if(parent[u]==u){ cout<<edges[u].first<<" "<<edges[u].second; return; } path(parent[u]); cout<<" "<<edges[u].second; } int main(){ int ant,curr,root,n; cin>>n; for(int i=0;i<n;i++){ cin>>curr; if(i>0){ edges[i].first=ant; edges[i].second=curr; adj[ant].push_back(curr); Map[make_pair(ant,curr)]=i; } if(i==0) root=curr; ant=curr; } if(root==curr){ cout<<root<<endl; return 0; } queue<int> q; for(int i=1;i<n;i++){ parent[i]=i; dist[i]=infInt; if(edges[i].first==root){ q.push(i); dist[i]=0; } if(edges[i].second==curr) mark[i]=true; }
while(!q.empty()){ int u=q.front(); q.pop(); int x=edges[u].first; int y=edges[u].second; for(auto z: adj[y]){ int v=Map[make_pair(y,z)]; if(v>u and dist[v]>dist[u]+1){ dist[v]=dist[u]+1; parent[v]=u; q.push(v); } } } int best=infInt,bestInd=-1; for(int i=1;i<n;i++){ if(dist[i]<best and mark[i]){ bestInd=i; best=dist[i]; } } path(bestInd); cout<<endl; return 0; } Could anyone provide me with an O(n) solution? My works O(n log(n)) My solution is O(n) and I can prove it. All tests from forum were successfully passed. Solution's body is 31 strings (without var declaratoins, etc.) and I am looking for mistakes more than an hour. So I suppose, there is no bug..( But I have WA5. Mabe some incorrect input ? Or some thing I didn't notice ? If u have got any idea or maybe test, please, help.. Edited by author 14.08.2009 05:39 what's is the wrong with this solution ?: i find the shortest path from the first vertx in the chain to the last ( with bfs) an print that path.i read my code , and I think it's correct ,say if I misunderstood the problem You have. I can not understand any thing else that I said , I read the problem description many times !! * the initial and final vertices of the chains p and q coincide; * the edges in the chain q are in the same order as in the chain p; * the chain q has the minimal possible number of edges under the given conditions. means that , it should be a path from first vertex to last ,and should use only the chains edges and should be minimal . so is the shortest path between first and last!! could you pleas give me a test, that my algorithm crashs? Yes after the contest is finished ;-) thnx! ;-) the edges in the chain q are in the same order as in the chain p; BFS breaks this rule Can you share tests now? I also want to know, what was in the 7th test:) something like that 13 1 2 3 4 5 6 7 6 2 6 8 9 7 my answer is 1 2 6 7,I think it's right,but still Wa test 7 Edited by author 11.07.2012 20:55 Edited by author 11.07.2012 20:55 Edited by author 03.04.2013 23:29 Right answer for 15 1 2 3 4 5 6 7 6 2 5 2 8 9 10 7 is 1 2 8 9 10 7 Edited by author 27.01.2016 19:11 Edited by author 27.01.2016 19:11 That is not right. Edges should be in the same order as the initial path. In your answer edges are not in the same order. Here is the right one: [1 2 8 9 10 7] try this test 17 1 2 3 4 5 6 7 2 8 9 5 10 8 9 11 3 9 1 2 6 7 - is not correct answer check yourself 1 2 6 8 9 7 - correct to Piratek-(akaDK) : Please said me why 1 2 8 9 is not correct? thx My program says 1 2 8 9 for 17 1 2 3 4 5 6 7 2 8 9 5 10 8 9 11 3 9 and 1 2 6 8 9 7 for 13 1 2 3 4 5 6 7 6 2 6 8 9 7 both answers seem correct, but i'm still getting WA7. What is the problem with it? This test helped me to pass 7 13 1 2 3 4 5 6 7 3 6 11 12 10 7 (1 2 3 4 5 6 7) However, I got WA 12 :-( Then I invented this one 15 1 2 3 12 4 5 6 7 3 6 11 12 10 7 6 (1 2 3 6) And finally got AC.. 13 1 2 3 4 5 6 7 6 2 6 8 9 7 Why not (1 2 6 7) ?? For input 13 1 2 3 4 5 6 7 6 2 6 8 9 7 the output 1 2 6 7 is wrong, because here edge (6,7) comes after (2,6), but in input edge (6,7) comes before edge (2,6). Hint: Don't use BFS, there is a simple O(n) solution, you don't need to construct graph. thanks But if decided to use BFS? It is important to know: 1. Can vertex be used multiply in BFS search- Yes. 2.Can edge be used multiply in BFS search-Yes. Thus what objects should we use in BFS constructing and how avoid loop in BFS. Good mastering in BFS more important than cleverness by the chance. P.S. Ac with BFS. 18 bad submissions on test 3 were answer: v1- I think that it is stupid trick. Case v1=v2 should be processed as common. BFS: 1)used pair(r1,r2) adjacent edges and r2 after r1 as object of layers of BFS because this pair can be meet in searching uniquely. And must use set<pair> to defining that pair is new. 2) used vector<int> sloi1,sloi2 for layers of BFS and struct pair data[1000000] as store of all items of BFS. Time Ac is bad but approach is in standard layout. After first Ac I had got Tle 17 because of new redjudjement. Wanted to have Ac throught BFS and no DP. I recoded BFS radically: 1) foud all states on reading data stage and stored its in array data[3000000] 2) used char met[3000000] to control uniquness of new states on searchind in BFS These helped to take AC 0.640c. Edited by author 08.11.2008 12:55 Infinity, i've produced correct answer to your test, but WA12 anyway :( give more tests, please I think you have just a bug somewhere.. Because I had. If you've passed 7, the idea seems to be right.. Try to check your code better.. I don't have more good tests I think test 12 contains something like that: 4 1 2 1 3 At least, such test helps in my WA12 :) My program works for all the test cases given in this thread, but it is giving WA#6, can you please give me this test case? Mine was wrong because of the test: 17 1 2 12 3 4 7 4 1 5 4 7 8 4 9 10 11 8 (Correct answer is "1 5 4 7 8") Can anybody give me test #7? Edited by author 18.12.2008 20:57 Please, give me test 7. hello to all i could'nt pass test 7 but i've a good test 9 1 2 3 4 1 3 5 6 4 Try to use this one for test 12: 13 1 4 5 13 8 6 4 8 17 11 12 8 7 Answer: 1 4 8 7 please help!I can't find the bug. Edited by author 10.09.2015 07:36 My code got WA7. const Nmax=100500; var Dp:array[1..Nmax] of longint; A,V:array[1..Nmax] of longint; N,i:longint;
BEGIN readln(N); for i:=1 to N do begin read(A[i]); Dp[a[i]]:=Nmax+5; end;
Dp[a[n]]:=0; V[a[n]]:=0; for i:=N-1 downto 1 do begin if(Dp[a[i]]>Dp[a[i+1]]+1) then begin Dp[a[i]]:=Dp[a[i+1]]+1; V[a[i]]:=a[i+1]; end; end;
write(a[1],' '); i:=V[a[1]]; while(i<>0) do begin write(i,' '); i:=V[i]; end; END. Hi I can pass my test case on every test in this forum, but it fails on #16. Can someone give me the testcase? I use dp code. /////////////////// import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.StreamTokenizer; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; public class Timus_1651 { static StreamTokenizer st; public static void main(String[] args) throws IOException{ st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); int n = nextInt(); int []a = new int [n+1]; for (int i = 1; i <=n; i++) { a[i] = nextInt(); } int []dp = new int [100001]; int []p = new int [100001]; int INF = (int)1e8; Arrays.fill(dp, INF); dp[a[1]] = 0; for (int i = 2; i <=n; i++) { if (dp[a[i]] > dp[a[i-1]]+1){ dp[a[i]] = dp[a[i-1]]+1; p[a[i]] = a[i-1]; } } int cur = a[n]; ArrayList<Integer> ans = new ArrayList<Integer>(); while (true){ ans.add(cur); if (cur == a[1]) break; cur = p[cur]; } Collections.reverse(ans); for (int i = 0; i < ans.size(); i++) { out.write(ans.get(i)+" "); } out.close(); } private static int nextInt() throws IOException{ st.nextToken(); return (int) st.nval; } } who can help me? I use bfs. use dynamic programming seq:1 2 7 3 2 8 4 8 5 dp :1 2 3 4 2 3 4 3 4 dp[i] -> dp[i+1] or dp[i] -> dp[j] while seq[i] == seq[j] Notice that if much j exists, just goto the smallest j the algorithm is O(N) P.S : why netflow doesn't work now ? :) AC in 0.14... but on my tests my program works > 2 sec. If I understand statements right, this test is correct: #include <cstdio> int main() { int n = 10000, sum = 0; printf("%d\n", 99951); for (int i = 6; i <= n; i++) { printf("1 %d 2 %d 3 %d 4 %d 5 %d ", i, i, i, i, i); sum += 10; } puts("1"); sum++; fprintf(stderr, "%d\n", sum); return 0; } Your test was added. Solutions were rejudged. I think any of them are accepted I think this picture is more confusing than explanatory, because there is no edges order, so one may solve it as standard minimal path problem. |
|