You are not logged in. Please login at www.codechef.com to post your questions!

×

Can someone solve FREETICKET from INOI 2014?

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 (here).

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.

Also, if you could review my pseudo code once, I'll be very grateful.

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

I realize this is a tedious work but please help me, it's really important.

Thank you all for your help, guys.

Note: when I'm trying the sample case, it returns maximum int value, which means the relaxation is not being done properly.

asked 04 Jan '15, 00:47

pm1511's gravatar image

1★pm1511
3156
accept rate: 0%

edited 04 Jan '15, 00:48


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...

#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;
}
link

answered 09 Jan '15, 23:37

arpanb8's gravatar image

3★arpanb8
120310
accept rate: 13%

Hello @arpanb8 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.

https://www.dropbox.com/s/qv6ghhnyv6zwiea/arpan%27s%20freeticket%20code.cpp?dl=0

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.

(12 Jan '15, 17:11) sandy9993★

Any time! I too got a better hold of the algorithm, debugging your code ;)

(12 Jan '15, 21:55) sandy9993★

I am in class 10. And if I wasn't taking INOI, I wouldn't be able to post in this forum :P

(12 Jan '15, 22:14) sandy9993★

An easier way is to use Dynamic Programming based Floyd-Warshall algorithm for 'all pairs shortest distances'.

link

answered 04 Jan '15, 19:06

vikramnitin9's gravatar image

2★vikramnitin9
1313
accept rate: 0%

@vikramnitin9 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 :(

(05 Jan '15, 21:06) pm15111★

http://pastebin.com/tQ02C6Mz Note: I have used the wikipedia pseudocode. I believe the one on iarcs site is different, I prefer this implementation.

(11 Jan '15, 10:59) superty3★

Hi!

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.

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.

int max_flight = INT_MIN;
for (i = 0; i < C; i++) {
    max_flight = max(max_flight, run_dijkstra_algorithm(i /* start node*/*));

Where run_dijkstra_algorithm returns the cost of the cheapest flight to the "farthest node".

Here's a simple solution in C, which I've hacked together with comments so the syntax isn't an issue:

// 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];
                }
            }
        }
    }
}

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.

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! :-)

Hope I could help, Cheers.

link

answered 04 Jan '15, 01:47

idraumr's gravatar image

0★idraumr
2463
accept rate: 45%

edited 04 Jan '15, 02:01

@vikramnitin9 --- only used Dijkstra's because the OP asked for it! :-)

(04 Jan '15, 19:41) idraumr0★

@idraumr 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.

(05 Jan '15, 21:34) pm15111★

@idraumr 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: http://pastebin.com/rQt8gUXx ).

(05 Jan '15, 21:36) pm15111★

@pm1511 -- http://pastebin.com/0f06pH4e, there you go. I get 100/100 on the grader.

(05 Jan '15, 22:10) idraumr0★

@idraumr 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

(05 Jan '15, 23:42) pm15111★

@pm1511 -- I'm an INOI participant myself. All the best to you too!

(06 Jan '15, 13:18) idraumr0★

@idraumr 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?

(10 Jan '15, 16:18) sandy9993★
1

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).

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.

You can try this problem to test your heap-based dijkstra implementation: http://codeforces.com/problemset/problem/20/C

(10 Jan '15, 18:03) superty3★
showing 5 of 8 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,158
×463
×116

question asked: 04 Jan '15, 00:47

question was seen: 4,031 times

last updated: 28 Jan '15, 15:22