Search found 22 matches
- Thu Apr 02, 2015 3:43 pm
- Forum: Volume 101 (10100-10199)
- Topic: 10199 - Tourist Guide
- Replies: 57
- Views: 31037
Re: 10199 - Tourist Guide
i am stil getting WA even after considering graph as disconnected here is my code #include <iostream> #include <stdlib.h> #include <algorithm> #include <string.h> #include <sstream> #include <map> #include <vector> #define max 110 using namespace std; map<string,int> mp; vector<int> adj[max]; int di...
- Wed Apr 01, 2015 1:38 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10029 - Edit Step Ladders
- Replies: 70
- Views: 20883
Re: 10029 - Edit Step Ladders
this is a irritating problem here is my code instead of checking all possible string set find all the edit steps of a string and apply binary search #include <iostream> #include <stdlib.h> #include <string.h> #include <map> #include <vector> #define max 26000 using namespace std; int dp[max]; vector...
- Wed Jul 09, 2014 8:11 am
- Forum: Volume 108 (10800-10899)
- Topic: 10816 - Travel in Desert
- Replies: 49
- Views: 22396
Re: 10816 - Travel in Desert
#include<iostream> #include<stdio.h> #include<vector> #include<queue> #include<string.h> #include<algorithm> #include<iomanip> #define max 110 using namespace std; int n,e,sv,ev,x,y; float r,d,tmin; float dist[max]; int pred[max]; int status[max]; struct set { int parent; int rank; }; struct st { in...
- Wed Jul 09, 2014 8:10 am
- Forum: Volume 108 (10800-10899)
- Topic: 10816 - Travel in Desert
- Replies: 49
- Views: 22396
Re: 10816 - Travel in Desert
#include<iostream> #include<stdio.h> #include<vector> #include<queue> #include<string.h> #include<algorithm> #include<iomanip> #define max 110 using namespace std; int n,e,sv,ev,x,y; float r,d,tmin; float dist[max]; int pred[max]; int status[max]; struct set { int parent; int rank; }; struct st { in...
- Sat Jul 05, 2014 9:07 am
- Forum: Volume 106 (10600-10699)
- Topic: 10600 - ACM Contest and Blackout
- Replies: 34
- Views: 13283
Re: 10600 - ACM Contest and Blackout
#include<iostream> #include<stdio.h> #include<vector> #include<queue> #include<string.h> #include<algorithm> #define infinity 999999999 #define max 110 int cost; int table[max][max]; using namespace std; int t,n,m,c1,c2,d,sv; int status[max]; struct set { int parent; int rank; }; struct st { int u; ...
- Wed Jun 18, 2014 8:16 am
- Forum: Volume 109 (10900-10999)
- Topic: 10917 - Walk Through the Forest
- Replies: 19
- Views: 10241
Re: 10917 - A Walk Through the Forest
here u must not use adjacency matrix for representaiom use array of vectors because there can be more than one undirected edges bw two nodes first run dijkstra sssp with STL heap and get distances from node 2 create dag using dist[a]>dist in dag also u can have more than one edges between two nodes ...
- Tue Jun 17, 2014 12:27 pm
- Forum: Volume 103 (10300-10399)
- Topic: 10342 - Always Late
- Replies: 25
- Views: 10987
Re: 10342 - Always Late
i tried a lot using dijkstra and STL priority queue
had the lengths provided>0,there is nothing in problm
but in this case the code may get stuck into local loops and u ll get TLE
i used eppstein algorithm and got AC
had the lengths provided>0,there is nothing in problm
but in this case the code may get stuck into local loops and u ll get TLE
i used eppstein algorithm and got AC

- Mon Jun 16, 2014 10:12 pm
- Forum: Volume 115 (11500-11599)
- Topic: 11573 - Ocean Currents
- Replies: 12
- Views: 3685
Re: 11573 - Ocean Currents
i used dijkstra with heap
u can also use c++ stl priority queue
here is my AC code
http://ideone.com/EO771i
u can also use c++ stl priority queue
here is my AC code
http://ideone.com/EO771i
- Mon Jun 16, 2014 7:30 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10986 - Sending email
- Replies: 65
- Views: 26915
Re: 10986 - Sending email
here naive dijksra will get TLE
so use dijkstra with heap
u can also use STL priority queue
here is my AC code
http://ideone.com/fEGjgN
so use dijkstra with heap
u can also use STL priority queue
here is my AC code
http://ideone.com/fEGjgN
- Sat Jun 14, 2014 9:26 pm
- Forum: Volume 7 (700-799)
- Topic: 796 - Critical Links
- Replies: 54
- Views: 22554
Re: 796 - Critical Links
a cut edge or bridge edge is not the part of any cycle so for each edge u-v if there exists any desecdant of v (inclusive) which has a back edge on the ancestors of u (inclusive) then that edge is not back edge http://ideone.com/rpPQdQ i m getting WA need hellp.... need to know wat AC soln gives for...
- Sat Jun 14, 2014 6:49 am
- Forum: Volume 114 (11400-11499)
- Topic: 11463 - Commandos
- Replies: 18
- Views: 10193
Re: 11463 - Commandos
here u have to travel all the vertices
but in bfs tree where there a branching occurs then return the max depth incurred bcoz by that tym other fleet would have completed the other branch
so u just find the max(dist[root]+dist[s]) after floyd warshall
but in bfs tree where there a branching occurs then return the max depth incurred bcoz by that tym other fleet would have completed the other branch
so u just find the max(dist[root]+dist[s]) after floyd warshall
- Tue Jun 10, 2014 3:02 pm
- Forum: Volume 5 (500-599)
- Topic: 562 - Dividing coins
- Replies: 73
- Views: 30058
Re: 562 - Dividing Coins
dp is usefull only when knapsack capacity is not too large
here in worst case W=100*500
how dp can be usefull here
here in worst case W=100*500
how dp can be usefull here
- Sun Jun 08, 2014 2:01 pm
- Forum: Volume 113 (11300-11399)
- Topic: 11374 - Airport Express
- Replies: 15
- Views: 6612
Re: 11374 - Airport Express
the problem doesnt have the optimal substructure property so how can one use greedy algorithm(dijkstra),
i think we can modify dijkstra algo by keeping track of the minimum distance from both economical and express rails
and then we can find shortest route
i think we can modify dijkstra algo by keeping track of the minimum distance from both economical and express rails
and then we can find shortest route
- Sat Jun 07, 2014 3:38 pm
- Forum: Volume 5 (500-599)
- Topic: 534 - Frogger
- Replies: 41
- Views: 17745
Re: 534 - Frogger help
it is an application of floyd warshal algo
finding the minimax path.
here we have to minimise the maximum edge value in all path
for(k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[j]=min(dp[j],max(dp[k],dp[k][j])
finding the minimax path.
here we have to minimise the maximum edge value in all path
for(k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[j]=min(dp[j],max(dp[k],dp[k][j])
- Sat Jun 07, 2014 12:38 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10099 - The Tourist Guide
- Replies: 91
- Views: 28700
Re: 10099 - The Tourist Guide
the question is simply a modification of floyd warshal algo for maximin path a maximin path =we maximise the path in which edge length is minimum for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) dist [j]=max(dist [j],min(dist [k],dist[k][j]) http://ideone.com/Gjv9Bo is my AC code :roll: