Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Ccc 2009 S4
Index -> Contests
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
zero-impact




PostPosted: Wed Mar 04, 2009 10:44 pm   Post subject: Ccc 2009 S4

This is my solution for S4.
It works perfectly as far as I can tell. The problem is that it is way to slow.
I used the Floyd?Warshall algorithm.
Is there any way to get an acceptable performance using this approach? If not what should I have done?

I/O files can be found here

c++:

#include <iostream>
#include <fstream>

using namespace std;

int dist [5001][5001];   //Distance between cities
int pencilC [5001];      //Cost of pencil at city [a]
int pencilCities [5001]; //Cities that sell pencils
int nCities,nTradeRoutes,nPencils,dest;             

int main()
{
        ifstream fin ("s4.3.in");
       
        for (int i = 0; i < 5001; i++)               //
                for (int k = 0; k < 5001; k++)       //Set distance between cities to infinity
                        dist [i][k] = 20000000;      //
                       
        fin >> nCities >> nTradeRoutes;
       
        int x,y,cost;
        for (int i = 0; i < nTradeRoutes; i++)      //
        {                                           //
                fin >> x >> y >> cost;              //Cost of trvelling
                dist [x][y] = cost;                 //
                dist [y][x] = cost;                 //
        }
                       
        fin >> nPencils;
        int city, price;
        for (int i = 0; i < nPencils; i++)       //
        {                                        //Cost of pencil
                fin >> city >> price;            //
                pencilC [city] = price;          //
                pencilCities [i] = city;
        }
       
        fin >> dest;
       
        for (int k = 0; k < nCities; k++)                                               //
                for (int i = 0; i < nCities; i++)                                       //Floyd Warshall implementation.
                        for (int j = 0; j < nCities; j++)                               //Finds cheapest shipping fee between all cities.
                                if (dist [i][k] + dist [k][j] < dist [i][j])            //
                                        dist [i][j] = dist [i][k] + dist [k][j];        //

                                       
        int temp,cheapest = 20000001;                                                        //
        for (int i = 0; i < nPencils; i++)                                                   //For every city that sells pencils
        {                                                                                    //
                if (dest == pencilCities[i])                                                 //If the destination is the city selling pencils then
                        temp = 0 + pencilC [pencilCities[i]];                                //Free shipping plus cost of pencil
                else                                                                         //else
                        temp = dist [dest][pencilCities[i]] + pencilC [pencilCities[i]];     //Cost of shipping plus cost of pencil
                                                                                             //
                cheapest = min (cheapest,temp);                                              //Keep track of best solution so far
        }                                                                                    //
       
        cout << cheapest;
        return 0;
}
Sponsor
Sponsor
Sponsor
sponsor
A.J




PostPosted: Wed Mar 04, 2009 11:09 pm   Post subject: RE:Ccc 2009 S4

You must realize that since the time complexity for Floyd Warshall is O(n^3), and since n (i.e. the # of cities) can go up to 5000...there is a worst case of O(125000000000), which is way too slow.

I would advise you to look at Dijkstra's algorithm, as it is much faster and also easy to understand.

The solution on the unofficial solution site is pretty good. I can give you the code I gave him (I coded it in C++...he just changed it to Java for the sake of the site eventhough Java is slower Laughing)
Analysis Mode




PostPosted: Wed Mar 04, 2009 11:49 pm   Post subject: Re: Ccc 2009 S4

Dijkstra's without a heap is O(E + V^2). Dijkstra's with a heap is O(E log V + V log V). BEcause V can equal E^2, the tiem complexity can be worst case ( O(V^2 log V) ) which is worse than without heap. So you're better off without it.

Even though the test data only goes to 5000 nodes and 5,000,000 edges.
A.J




PostPosted: Thu Mar 05, 2009 12:02 am   Post subject: RE:Ccc 2009 S4

I coded Dijkstra without a heap and it worked for the worst testcases in under 9 s (including input and everything) in C++.

The algorithm is pretty straight forward. There are some cool visualizations (if thats even a word :S) of the algo on the net.
DanielG




PostPosted: Thu Mar 05, 2009 2:13 am   Post subject: RE:Ccc 2009 S4

I tried using the heap method, it failed... (due to inefficiency)
zero-impact




PostPosted: Thu Mar 05, 2009 3:18 pm   Post subject: RE:Ccc 2009 S4

Ok thanks for the tip. I saw your Java code A.J. Would you mind pm-ing me your c++ verison?
bbi5291




PostPosted: Thu Mar 05, 2009 4:31 pm   Post subject: Re: Ccc 2009 S4

Analysis Mode wrote:
Quote:
Dijkstra's without a heap is O(E + V^2). Dijkstra's with a heap is O(E log V + V log V). BEcause V can equal E^2, the tiem complexity can be worst case ( O(V^2 log V) ) which is worse than without heap. So you're better off without it.


A small typo here: E is O(V^2) (and not "V can equal E^2").

Many programmers, after learning Dijkstra's with a priority queue/heap, forget how to do it the "easy" way with an array. This leads to much weeping and gnashing of teeth in cases such as this in which E is not O(V log V). I myself had never coded it prior to this year's CCC, and took a long time to code it. Analysis Mode also couldn't figure it out...

If you're wondering where these time bounds come from:

For Dijkstra's without a heap, each vertex is considered once, and each time a vertex is visited it takes O(V) time to decide which one to visit (by iterating through the array). Each edge is also considered once - O(E + V^2) time.

With a heap, each edge is pushed onto the queue O(1) times (you can reduce the constant using optimizations, which are sometimes quite necessary) and for each vertex it is necessary to pop once from the heap - so O(log E) time per edge and O(log E) time per vertex, O((E+V) log E) total. But E is at most V^2 and usually at least V (it's not too hard to make it run more quickly if E is smaller), so log E = O(log V) and we generally write O((E+V) log V).

There are also special priority queue implementations that support constant time insertion, but are still logarithmic in deletion (if they were constant time in both then we would have a linear time heapsort, which is impossible). This gives the bound of O(E + V log V). Still faster solutions exist, if one doesn't use Dijkstra's algorithm. They are close to linear, such as O(E log(log V)) but you generally have to read research papers if you want to find out about them.
saltpro15




PostPosted: Thu Apr 09, 2009 5:43 pm   Post subject: RE:Ccc 2009 S4

holy huge input files, can someone please post a perfect solution to help me learn dijkstra's? or P.M. it please
Sponsor
Sponsor
Sponsor
sponsor
zero-impact




PostPosted: Thu Apr 09, 2009 7:35 pm   Post subject: RE:Ccc 2009 S4

http://access.mmhs.ca/ccc/index.htm

Unofficial solutions
saltpro15




PostPosted: Thu Apr 09, 2009 7:43 pm   Post subject: RE:Ccc 2009 S4

yeah but it's in Java zero_impact, I know who's solution it is too Wink
nike52




PostPosted: Fri Apr 10, 2009 12:48 am   Post subject: Re: Ccc 2009 S4

even though it's in java, you're still able to learn dijkstra's from it
saltpro15




PostPosted: Fri Apr 10, 2009 7:33 am   Post subject: RE:Ccc 2009 S4

yeah true, I found a nice article on wiki about it also that will help.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 12 Posts ]
Jump to:   


Style:  
Search: