Intel® Software Network

Hello,

I have a question concerning the range of the values :
- are weights positive integers ?
- do the longest path length fit into an unsigned integer (32bits) ?

Thanks in advance.

Other questions concerning the output

- if some paths have the same weight how do we keep the 20 first ?
- when outputting "srcName dstName weight", do we have to have srcName - idem for equivalent weight, we could sort them by srcName ?

Best regards.

dgeld:

- are weights positive integers ?

Yes. A distance is positive integer. 

Positive (>=0) or strictly positive (>0) ?

Weights will be strictly positive (> 0). 

If a path exists, the shortest length of the path will fit into 32-bit integer. (Of course, if no path exists that length would be infinite.  Since it takes a few bits more than 32 to represent infinity, you may need to devise a means of representing that value.)

For output of node pairs whose paths have the same weight and fall within the top or bottom 20, any valid pair that fit the criteria will be accepted.  That is, if 2 paths have weight 5 and 30 others have weight 6, the 2 paths of weight 5 and any 18 of the 30 with weight 6 would be correct to output.  (It's up to the judges to either ensure the data has unique path weights or know all of the possible node pair paths that will have the same weight to be output.)

Since the data is an undirected graph, the output of

abc*efgh12  zyXWVuts09  345678

is the same as

zyXWVuts09  abc*efgh12  345678

and only one of these lines should appear in the output.  The output order of one of the above lines with

mnopqrkl56  Moscow2,ID  345678

is irrelevant. 

--clay

---

"It's all very complicated and would take a scientist to explain it." -- MST3K

Thanks clay for the clarification.

What is the maximum number of nodes to expect for the input files?

May we assume that the input is case-insensitive ... so that "Harrisburg" is the same as "harrisburg"?

Oh and is the following a valid entry (self-loop):

Harrisburg Harrisburg 1

And is zero (0) a valid distance?

Thanks

s1g1ll:

What is the maximum number of nodes to expect for the input files?

Good question.  dgeld posted a 6000 node file, so it would have to be something that size or bigger.  To fit in memory, some back of the envelope calculations say an upper bound of 28377 nodes.  So, let us set a maximum number of nodes at 25000 to leave some head room.

--clay 

---

"It's all very complicated and would take a scientist to explain it." -- MST3K

DweeberlyLoom:

May we assume that the input is case-insensitive ... so that "Harrisburg" is the same as "harrisburg"?

No, node names are case-sensitive.  Your example would correspond to two different nodes.

DweeberlyLoom:

Oh and is the following a valid entry (self-loop):

Harrisburg Harrisburg 1

And is zero (0) a valid distance?

No and No.  There will be no self-referential lines in the input data and there will be no zero distances within the input data.  The only zero value that should be considered is the non-existent edge from the node to itself.  In the words of one rock and roll physicist, "No matter where you go, there you are." And it takes no distance/weight/cost to get there from there.  Of course, these semi-fictional zero weights would not be listed in the lowest 20 path weights since there are no edges to traverse. They should merely prevent the algorithm from attempting to find a path from point A back to point A longer than zero.

--clay

---

"It's all very complicated and would take a scientist to explain it." -- MST3K

Hello clay,

what is the maximum memory size we are allowed to use ?

How much memory will have the test machine ? Do you compile our programs in 64bits ?

Thanks in advance.

Am I correct in the following two assumptions?

1)  The distance value is expressed as a 32 bit unsigned int?

2) The following input:

AAAAAAAAAA BBBBBBBBBB 7
AAAAAAAAAA CCCCCCCCCC 8
AAAAAAAAAA DDDDDDDDDD 4
CCCCCCCCCC DDDDDDDDDD 2

Would produce (only top and bottom three shown):

Smallest:
------------------------------
CCCCCCCCCC DDDDDDDDDD       2
AAAAAAAAAA DDDDDDDDDD       4
AAAAAAAAAA CCCCCCCCCC       6

Largest:
------------------------------
BBBBBBBBBB CCCCCCCCCC      13
BBBBBBBBBB DDDDDDDDDD      11
AAAAAAAAAA BBBBBBBBBB       7

There are 0 node pairs that have no path.

Another way to ask this is when there are cycles we always take the 'minimum' path between any two nodes even when calculating the largest values (in the above example there are two paths from BBBBBBBBBB to DDDDDDDDDD, one is 11 and one is 17 ... always choose the smallest ... 11). Correct?

dgeld:

Hello clay, what is the maximum memory size we are allowed to use ? How much memory will have the test machine ? Do you compile our programs in 64bits ? Thanks in advance.

Use as much memory as you need.  The details on the test machines are here: http://softwarecommunity.intel.com/isn/Community/en-US/forums/thread/30243918.aspx and here: http://softwarecommunity.intel.com/isn/Community/en-US/forums/thread/30243915.aspx.  It looks like we've got 4GB of memory.

(An upper bound of 25,000 nodes has been set in an earlier post.)

We do compile in 64 bits.  On windows we have two machines, one that has libraries in only 64-bit versions and the other that supports 32 bit versions.  Judges will try on the 64-bit machine before moving to the 32-bit machine.  I'm not sure about how the Linux platforms are set up.  I have assumed that the test machine (that has been used) defaults to 64 bits. (I've remained blissfully ignorant of such details, so if I've got this wrong, please feel free to correct my mistakes.)

--clay

---

"It's all very complicated and would take a scientist to explain it." -- MST3K

DweeberlyLoom:

Am I correct in the following two assumptions?

1)  The distance value is expressed as a 32 bit unsigned int?

2) ...when there are cycles we always take the 'minimum' path between any two nodes even when calculating the largest values (in the above example there are two paths from BBBBBBBBBB to DDDDDDDDDD, one is 11 and one is 17 ... always choose the smallest ... 11). Correct?

Yes and Yes. 

The problem is called "Shortest Path" so we are always looking for a minimum when presented with two options that are otherwise equivalent.  Would you rather be stuck in your economy class airline seat for 11 or 17 hours?  If you find a "Hello Kitty" DVD at two different outlets, would you buy the €11 one or the €17 copy?  If the pirate captain that you served under offered you the choice between 11 and 17 lashes as your punishment for buying that DVD, which would you take?

--clay

---

"It's all very complicated and would take a scientist to explain it." -- MST3K

Will node names always be exactly 10 characters?  Is it possible to have an edge like so:

Erie,PA Waco,TX 1234

s1g1ll:

Will node names always be exactly 10 characters?

Yes it is in the problem statement :
10 characters + 1 space + 10 characters + 1 space + rest of the line will be the weight

"Each entry will consist of 2 nodes, each represented by ten printable characters (no spaces), and an integer representing the weight of the edge between the two nodes. Each input field will be separated by a single space"

Hi . i want to know is there any sample Input file uploaded if have please send me the link

Thanks and Regards

murtaza dhari

murtazadhari:

Hi . i want to know is there any sample Input file uploaded if have please send me the link

Thanks and Regards

murtaza dhari

Actually there are two.  Check the thread labeled "Small data set file".

a sample Input and Output.