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>enMon, 12 Jan 2015 22:14:37 +0530Comment by sandy999 on arpanb8's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#61401<p>I am in class 10. And if I wasn't taking INOI, I wouldn't be able to post in this forum :P</p>sandy999Mon, 12 Jan 2015 22:14:37 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#61401Comment by sandy999 on arpanb8's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#61395<p>Any time! I too got a better hold of the algorithm, debugging your code ;)</p>sandy999Mon, 12 Jan 2015 21:55:51 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#61395Comment by sandy999 on arpanb8's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#61351<p>Hello <a href="/users/83891/arpanb8"><a href="/users/83891/arpanb8">@arpanb8</a></a> I have edited your code and got it accepted. Please refer the link below. I have also highlighted the lines where I have edited so that you can compare your previous code with this code and check where you went wrong.</p>
<p><a href="https://www.dropbox.com/s/qv6ghhnyv6zwiea/arpan%27s%20freeticket%20code.cpp?dl=0">https://www.dropbox.com/s/qv6ghhnyv6zwiea/arpan%27s%20freeticket%20code.cpp?dl=0</a></p>
<p>In short, your errors were: You didn't make your infinity in your initialization of the 3D array large enough and there was a slight flaw in your implementation of the algorithm. That's pretty much it.</p>sandy999Mon, 12 Jan 2015 17:11:15 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#61351Comment by superty on vikramnitin9's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#61233<p><a href="http://pastebin.com/tQ02C6Mz">http://pastebin.com/tQ02C6Mz</a>
Note: I have used the wikipedia pseudocode. I believe the one on iarcs site is different, I prefer this implementation.</p>supertySun, 11 Jan 2015 10:59:17 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#61233Comment by superty on idraumr's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#61193<p>If N is the number of vertices, and M is the number of edges in the graph, heap based Dijkstra runs in O(MlogN), whereas the regular implementation runs in O(N^2). </p>
<p>So if the N^2 is too big to run in the time limit, and M is much smaller, then heap-based will work. For example, consider if N <= 10^5, M <= 10^5 (most graph problems with large N seem to have constraints like this). Then clearly N^2 is too big but MlogN works. </p>
<p>You can try this problem to test your heap-based dijkstra implementation: <a href="http://codeforces.com/problemset/problem/20/C">http://codeforces.com/problemset/problem/20/C</a></p>supertySat, 10 Jan 2015 18:03:23 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#61193Comment by sandy999 on idraumr's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#61184<p><a href="/users/83893/idraumr"><a href="/users/83893/idraumr">@idraumr</a></a> I've always had some kind of fear of such graph problems which involve Shortest path algorithms, never have I seen such a simple implementation of the Dijkstra. Thank you so much for taking the pain to comment out every little detail in your code! A code speaks a thousand words! This is the first problem I have attempted using Dijkstra's algorithm and I now feel more confident :) Just a question, when should we use heaps to implement Dijkstra's algorithm?</p>sandy999Sat, 10 Jan 2015 16:18:12 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#61184Answer 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/61144Comment by idraumr on idraumr's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60885<p><a href="/users/81254/pm1511">@pm1511</a> -- I'm an INOI participant myself. All the best to you too!</p>idraumrTue, 06 Jan 2015 13:18:23 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60885Comment by pm1511 on idraumr's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60851<p><a href="/users/83893/idraumr">@idraumr</a> Thanks a ton, bro. Incidentally, I'd solved the problem just a few minutes before you posted your code. But once again, I cannot express how much gratitude I owe you for your great effort in helping a fellow coder. Hope you clear INOI (if you're appearing, or ICPC, in case you're in college) :D</p>pm1511Mon, 05 Jan 2015 23:42:47 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60851Comment by idraumr on idraumr's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60834<p><a href="/users/81254/pm1511">@pm1511</a> -- <a href="http://pastebin.com/0f06pH4e,">http://pastebin.com/0f06pH4e,</a> there you go. I get 100/100 on the grader.</p>idraumrMon, 05 Jan 2015 22:10:51 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60834Comment by pm1511 on idraumr's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60833<p><a href="/users/83893/idraumr"><a href="/users/83893/idraumr">@idraumr</a></a> If you don't mind, can you post a complete solution, with all the input and output like asked in the question (incase you're busy, please don't waste your time by typing this. If not possible, maybe you can look at my code and check the problem in this,it is a direct copy of your code, above, BTW: <a href="http://pastebin.com/rQt8gUXx">http://pastebin.com/rQt8gUXx</a> ).</p>pm1511Mon, 05 Jan 2015 21:36:00 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60833Comment by pm1511 on idraumr's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60832<p><a href="/users/83893/idraumr">@idraumr</a> Thanks a lot mate, I understand how much effort you put into writing this answer, and I really thank you for that. However, I adapted your code as it is into java because I really couldn't figure it out myself, even after using Floyd-Warshall, but even then there seems to be some problem.</p>pm1511Mon, 05 Jan 2015 21:34:40 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60832Comment by pm1511 on vikramnitin9's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60828<p><a href="/users/83916/vikramnitin9">@vikramnitin9</a> Can you please give me the code using Floyd Warshall?
I tried doing it using the Wikipedia pseudo code but it still didn't work :(</p>pm1511Mon, 05 Jan 2015 21:06:36 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60828Comment by idraumr on idraumr's answerhttps://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60744<p><a href="/users/83916/vikramnitin9">@vikramnitin9</a> --- only used Dijkstra's because the OP asked for it! :-)</p>idraumrSun, 04 Jan 2015 19:41:24 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014#60744Answer 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