Search found 22 matches

by prashantharshi
Thu Apr 02, 2015 3:43 pm
Forum: Volume 101 (10100-10199)
Topic: 10199 - Tourist Guide
Replies: 57
Views: 30685

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...
by prashantharshi
Wed Apr 01, 2015 1:38 pm
Forum: Volume 100 (10000-10099)
Topic: 10029 - Edit Step Ladders
Replies: 70
Views: 20471

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...
by prashantharshi
Wed Jul 09, 2014 8:11 am
Forum: Volume 108 (10800-10899)
Topic: 10816 - Travel in Desert
Replies: 49
Views: 22114

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...
by prashantharshi
Wed Jul 09, 2014 8:10 am
Forum: Volume 108 (10800-10899)
Topic: 10816 - Travel in Desert
Replies: 49
Views: 22114

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...
by prashantharshi
Sat Jul 05, 2014 9:07 am
Forum: Volume 106 (10600-10699)
Topic: 10600 - ACM Contest and Blackout
Replies: 34
Views: 13008

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; ...
by prashantharshi
Wed Jun 18, 2014 8:16 am
Forum: Volume 109 (10900-10999)
Topic: 10917 - Walk Through the Forest
Replies: 19
Views: 10111

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 ...
by prashantharshi
Tue Jun 17, 2014 12:27 pm
Forum: Volume 103 (10300-10399)
Topic: 10342 - Always Late
Replies: 25
Views: 10825

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 :)
by prashantharshi
Mon Jun 16, 2014 10:12 pm
Forum: Volume 115 (11500-11599)
Topic: 11573 - Ocean Currents
Replies: 12
Views: 3566

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
by prashantharshi
Mon Jun 16, 2014 7:30 pm
Forum: Volume 109 (10900-10999)
Topic: 10986 - Sending email
Replies: 65
Views: 26442

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
by prashantharshi
Sat Jun 14, 2014 9:26 pm
Forum: Volume 7 (700-799)
Topic: 796 - Critical Links
Replies: 54
Views: 22229

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...
by prashantharshi
Sat Jun 14, 2014 6:49 am
Forum: Volume 114 (11400-11499)
Topic: 11463 - Commandos
Replies: 18
Views: 10050

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
by prashantharshi
Tue Jun 10, 2014 3:02 pm
Forum: Volume 5 (500-599)
Topic: 562 - Dividing coins
Replies: 73
Views: 29567

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
by prashantharshi
Sun Jun 08, 2014 2:01 pm
Forum: Volume 113 (11300-11399)
Topic: 11374 - Airport Express
Replies: 15
Views: 6472

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
by prashantharshi
Sat Jun 07, 2014 3:38 pm
Forum: Volume 5 (500-599)
Topic: 534 - Frogger
Replies: 41
Views: 17552

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])
by prashantharshi
Sat Jun 07, 2014 12:38 pm
Forum: Volume 100 (10000-10099)
Topic: 10099 - The Tourist Guide
Replies: 91
Views: 28156

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:

Go to advanced search