Answers to: Can 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>enFri, 09 Jan 2015 23:37:34 +0530Answer by arpanb8https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014/61144<p>I worked out a Floyd-Warshall solution to this prob. and am getting a WA in 4/20 testcases. So, my score is 30/100. Please Help...</p>
<pre><code>#include "iostream"
#include "algorithm"
using namespace std;
int main()
{
int n;
cin >> n;
int x[300][300][300];
int f;
cin >> f;
int temp1, temp2, temp3;
for (int a = 1; a<=n; a++)
for (int b = 1; b<=n; b++)
{
x[1][a][b]=100005;
x[1][a][a]=0;
}
for (int i = 1; i<=f; i++)
{
cin>>temp1>>temp2>>temp3;
x[1][temp1][temp2]=temp3;
x[1][temp2][temp1]=temp3;
}
int xyz;
for (int p = 2; p<=n-1; p++)
for (int q = 1; q<=n; q++)
for (int r = 1; r<=n; r++)
{
x[p][q][q]=0;
xyz=min(x[p-1][q][r], (x[p-1][q][p]+x[p-1][p][r]));
x[p][q][r]=xyz;
}
int m = 0;
for (int X=1; X<=n; X++)
{
for (int Y = 1; Y<=n; Y++)
if (x[n-1][X][Y]>m && x[n-1][X][Y]<100005 && x[n-1][X][Y]!=0)
m=x[n-1][X][Y];
}
cout << m;
return 0;
}
</code></pre>arpanb8Fri, 09 Jan 2015 23:37:34 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014/61144Answer by vikramnitin9https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014/60738<p>An easier way is to use Dynamic Programming based Floyd-Warshall algorithm for 'all pairs shortest distances'.</p>vikramnitin9Sun, 04 Jan 2015 19:06:20 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014/60738Answer by idraumrhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014/60663<p>Hi!</p>
<p>Firstly, I hope you understand the motivation behind Dijkstra's algorithm. It's good to look through the proof (so you know why negative edges can't be handled), but just a understanding behind the motivation is enough for tackling simple problems. Imagine you put some water at the first node, and let it flow. Each edge's cost is represented by its length. Now, at each iteration of the main loop in Dijkstra's algorithm, you mark the node which the water would touch next. Try drawing this on a whiteboard or piece of paper, visualizing the water flowing through.</p>
<p>Secondly, in plaintext, the solution of the "freeticket" problem is as follows---for each node, you find the farthest node that can be reached by starting from it. For all such "farthest nodes", you take the most costly one. It is like putting water in each node, one at a time, and marking the node where it reaches last. You do this for every node, and then take a maximum over all such values.</p>
<pre><code>int max_flight = INT_MIN;
for (i = 0; i < C; i++) {
max_flight = max(max_flight, run_dijkstra_algorithm(i /* start node*/*));
</code></pre>
<p>Where <code>run_dijkstra_algorithm</code> returns the cost of the cheapest flight to the "farthest node".</p>
<p>Here's a simple solution in C, which I've hacked together with comments so the syntax isn't an issue:</p>
<pre><code>// flights[i][j] is the cost of the flight from i to j. -1 means no such flight.
// For each node from 0 to C - 1, you make this the "first node".
for (i = 0; i < C; i++) {
long long distance[C]; int visited[C];
// This is the inner loop, basically the Dijkstra's algorithm.
// visited[i] is set to 1 if water has "reached" the node, else 0.
// distance[i] marks the current cheapest distance to a node.
// From i, by just taking one flight, you mark the cost to reach each node. Water hasn't
// yet reached any node, except i (because you started from it).
for (j = 0; j < C; j++)
distance[j] = flights[i][j], visited[j] = 0;
visited[i] = 1;
while (1) {
// Now you find the next node that water would reach.
// This translates to the next minimum value of distance[i].
int min_flight = -1, min_distance = INT_MAX;
for (j = 0; j < C; j++)
if (distance[j] != -1 && !visited[j]
&& distance[j] < min_distance) {
min_distance = distance[j];
min_flight = j;
}
// If you've reached all nodes you could, then you've visited
// the "farthest node". Now go start from another node.
if (min_flight == -1)
break;
visited[min_flight] = 1;
// Is this the costliest flight trip you've taken yet? Mark it!
if (min_distance > max_cost) max_cost = min_distance;
// Now this is some updating time of the distance array.
// How this works is simple. If, from the newly visited node, you can visit
// some other node cheaper, or some other node you couldn't visit before,
// you mark it so.
for (j = 0; j < C; j++) {
if (flights[min_flight][j] != -1) {
if (distance[j] == -1 ||
distance[j] > min_distance + flights[min_flight][j]) {
distance[j] = min_distance + flights[min_flight][j];
}
}
}
}
}
</code></pre>
<p>Lastly, your code. I didn't take a deep look, but if I'm not wrong, for each node, you're just marking the maximum "first flight" it could take. </p>
<p>EDIT: Oops. Forgot some motivation jumbo mumbo. If everyone solved all problems in their first go, surely they'd be no need for competitions to motivate us to learn more? It's okay. You'll soon solve one. Then another. Then all. What's important is to enjoy the process, to struggle through the problem while you can---and most importantly, to know when's the right time to give up and ask on CodeChef! :-)</p>
<p>Hope I could help,
Cheers.</p>idraumrSun, 04 Jan 2015 01:47:30 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014/60663