Questions Tagged With graphhttps://inoi15.discuss.codechef.com/tags/graph/?type=rssquestions tagged <span class="tag">graph</span>enFri, 30 Jan 2015 20:01:32 +0530Help me with this graph problemhttps://inoi15.discuss.codechef.com/questions/60367/help-me-with-this-graph-problem<p>Someone mentioned in an answer that the following problem can be solved using only DFS/BFS: <a href="http://www.spoj.com/problems/PRATA/">http://www.spoj.com/problems/PRATA/</a></p>
<p>I am not getting any idea on how to solve this problem without using Dijkstra's algo/ MST. Binary Search is another approach. Can anyone tell how to solve this using only BFS/DFS?</p>ketanhwrWed, 31 Dec 2014 21:54:18 +0530https://inoi15.discuss.codechef.com/questions/60367/help-me-with-this-graph-problembfsgraphdijkstramstdfsHere'e a prob. I've been struggling with...Plz. help!!!https://inoi15.discuss.codechef.com/questions/60384/heree-a-prob-ive-been-struggling-withplz-help<p>Can someone explain the statement of the HYPERSPACEPATHS prob. from the INOI Practice Server..
If possible, please describe the solution...</p>arpanb8Thu, 01 Jan 2015 02:28:22 +0530https://inoi15.discuss.codechef.com/questions/60384/heree-a-prob-ive-been-struggling-withplz-helpgraphCan someone solve FREETICKET from INOI 2014?https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014<p>Hi everyone.
I've been practicing on the INOI server lately, however I've not yet solved even a single question. I studied Graph Theory for the first time last week and decided to do the FREETICKET problem using Djikstra's Algorithm (<a href="http://www.iarcs.org.in/inoi/2014/inoi2014/inoi2014-qpaper.pdf">here</a>).</p>
<p>I've tried to solve the problem innumerable times, but am still not able to do so. If someone could please tell me the pseudocode, it'll be of great help. I'm asking for the pseudo code as I program in Java and am sometimes not able to understand c++ syntax. </p>
<p>Also, if you could review my pseudo code once, I'll be very grateful.
<code></code></p><code>
<p>int[] max = new int[vertices]
for each vertex u = 1 -> v:
int[] dist = new int[vertices]
dist[u] = 0
for each int i = 1 -> v:
if i != u:
dist[i] = INFINITY
for each int i = 0 -> v:
if edge exists from u->i:
int tmp = dist[u] + weight[u][i]
if tmp < dist[i]:
dist[i] = tmp
max[u] = maximum(dist)
int f = maximum(max)
return f //here max is an array and maximum is the
//function for finding maximum value</p>
</code><p><code></code></p>
<p>I realize this is a tedious work but please help me, it's really important.</p>
<p>Thank you all for your help, guys.</p>
<p>Note: when I'm trying the sample case, it returns maximum int value, which means the relaxation is not being done properly.</p>pm1511Sun, 04 Jan 2015 00:47:17 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014bfsgraphshortest-pathINOI 2010 Twin Robotshttps://inoi15.discuss.codechef.com/questions/63361/inoi-2010-twin-robots<p>Hi people,
During the current INOI practice contest, i saw that INOI 2010 question 2 has been asked. Can someone help me formulate a Dp solution for it. I don't wish to cheat, rather I wish to learn how to solve a graph + DP type problem. The contest ends at 10:00 pm, and by then it'll be too late to learn anything new, so I request help right now and also request others not to cheat during the 'practice ' contest using any solutions below...</p>
<p>This is my current DP formulation, yet I believe the following recurrence relation might just go on and my base case(s) are incorrect. Yet, here goes:</p>
<pre><code>sum(i, j, k, l) = grid[i][j] + grid[k][l] + max(sum(i-1, j, k, l-1),sum(i, j-1, k-1, l))
if(i > 0 & l > 0) if(j > 0 & k > 0)
sum(0, 0, 0, n-1) = grid[0][0] + grid[0][n-1]
</code></pre>
<p>I tried <a href="http://pastebin.com/RmJHheKw">implementing this DP</a>, but there are loads of bugs and it does'nt yield any results... Help creating a better reccurence and/or in debugging my code will be appreciatted. thanks in advance...</p>nibnalinFri, 30 Jan 2015 20:01:32 +0530https://inoi15.discuss.codechef.com/questions/63361/inoi-2010-twin-robotsdynamic-programminggraphinoi