Questions asked by sandy999https://inoi15.discuss.codechef.com/questions/asked-by/51588/sandy999/?type=rssQuestions asked by <a href="/users/51588/sandy999" >sandy999</a>enThu, 29 Jan 2015 21:22:58 +0530Adjacency lists & Adjacency matriceshttps://inoi15.discuss.codechef.com/questions/60720/adjacency-lists-adjacency-matrices<p>I recently implemented DFS by making an adjacency list using a vector of vectors and was pretty pleased about that. But yesterday, I read here <a> </a><a href="http://web.stanford.edu/class/cs97si/">http://web.stanford.edu/class/cs97si/</a> on the basic Graph algorithms slide that an array of vectors is slower than plain arrays.</p>
<p>For me, vectors of vectors was pretty easy to code but just arrays was hard as I had trouble just adding an edge and manipulating the 2 arrays. What do the rest of you recommend me to use taking into account time and memory efficiency? If you recommend arrays, could you also give me a good resource which explains how to easily implement it?</p>
<p>Also, I read that we should use an adjacency matrix only when the graph is dense (No. of vertices is almost equal to no. of edges). But what if the constraints (around 10^5 edges) are such that it is too large even for the global scope? What do I use to represent the edge relations in such a case?</p>sandy999Sun, 04 Jan 2015 16:24:04 +0530https://inoi15.discuss.codechef.com/questions/60720/adjacency-lists-adjacency-matricesgraphsTABLESUM WAhttps://inoi15.discuss.codechef.com/questions/60902/tablesum-wa<p>Could someone please tell me what's going wrong with this TABLESUM code? I am getting WA in all except 3 test cases. The algorithm is O(N), so time is not an issue.</p>
<p><a> </a><a href="https://www.dropbox.com/s/im7sjck0z8elukk/TABLESUM.cpp?dl=0">https://www.dropbox.com/s/im7sjck0z8elukk/TABLESUM.cpp?dl=0</a> </p>sandy999Tue, 06 Jan 2015 17:37:16 +0530https://inoi15.discuss.codechef.com/questions/60902/tablesum-watablesumFloyd Warshall Algorithmhttps://inoi15.discuss.codechef.com/questions/61201/floyd-warshall-algorithm<p>Could someone please give me a basic intuition between the Floyd Warshall algorithm like how you would explain it to a layman? In addition to when it is/isn't preferred over Dijakstra's algorithm?</p>
<p>I've tried looking up various sources but it's like, if I read a pseudocode I am able to understand what they are doing but not why they are doing it, which is pretty pointless as that is not the right way to learn.</p>
<p>Could someone please help me out?</p>sandy999Sat, 10 Jan 2015 20:45:57 +0530https://inoi15.discuss.codechef.com/questions/61201/floyd-warshall-algorithmfloyd-warshallHISPDNET algorithmhttps://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm<p>Problem statement: <a> </a><a href="http://opc.iarcs.org.in/index.php/problems/HISPDNET">http://opc.iarcs.org.in/index.php/problems/HISPDNET</a> </p>
<p>I can only think of the following:</p>
<p>1) Brute force: Consider all permutations of 2,3,4,...,N and find which among these gives the minimum cost (where the 1st city of the permutation is connected only to 2nd element, 2nd element to 3rd element and so on). But it is too time consuming and wouldn't give the answer even in a billion years.</p>
<p>2) Use some shortest path algorithm. (As of now, I am only familiar with Dijkstra's and Floyd Warshall). But there is a big restriction, I need to find shortest paths between all pairs of sources and destinations and where the number of intermediate edges is strictly N-2 (excluding source and destination), nothing more or nothing less.</p>
<p>I am really confused as to how to approach the problem with an elegant time efficient algorithm. It would be great if someone could give me a hint.</p>sandy999Tue, 13 Jan 2015 16:16:16 +0530https://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithmhispdnetCULPRO algorithmhttps://inoi15.discuss.codechef.com/questions/63240/culpro-algorithm<p>Well, it's frustrating that I could solve DOMSOL and not this :/</p>
<p>Problem link: <a> </a><a href="http://www.codechef.com/INPR1501/problems/CULPRO">http://www.codechef.com/INPR1501/problems/CULPRO</a> </p>
<p>How do I approach it?</p>sandy999Thu, 29 Jan 2015 21:22:58 +0530https://inoi15.discuss.codechef.com/questions/63240/culpro-algorithmculpro