10397 - Connect the Campus

Dmytro Chernysh · Post by **Dmytro Chernysh** » Wed Jun 25, 2003 7:34 pm

Do you know that QuickSort is the fastest only in avarege, but there are cases where OuickSort is VERY slow!

If you are interested in that I can write more...

Dominik Michniewski · Post by **Dominik Michniewski** » Thu Jun 26, 2003 7:55 am

Yes but in this question buit-in qsort() in C library is enough ....
Pesymistic time complexity QuickSort and ShellSort is the same, but qsort() in average time is very efficient ... and I don't think, that judge create tests, on which qsort is problem

Best regards
DM

Observer · Post by **Observer** » Wed Jul 02, 2003 4:27 am

-- Post removed by Observer --

Observer · Post by **Observer** » Thu Jul 17, 2003 10:41 am

No one can help me..... weep

anupam · Post by **anupam** » Fri Jul 18, 2003 2:43 pm

well i am also a sufferer, does the picture f the problem indicate anything important, If it does they please post the picture here. Because it is not available in the site..;
Please post the pictures.

titid_gede · Post by **titid_gede** » Fri Jul 18, 2003 3:15 pm

i used code 10147 to solve this problem. only changed input / output. this is MST problem.

Observer · Post by **Observer** » Sat Jul 19, 2003 4:38 pm

-- Post removed by Observer --

dispanser · Post by **dispanser** » Wed Jul 23, 2003 9:25 am

anupam wrote:well i am also a sufferer, does the picture f the problem indicate anything important, If it does they please post the picture here. Because it is not available in the site..;
Please post the pictures.

the picture is absolutely not important. you can see a few buildings from far away, that symbolizes the campus

.

btw, can anyone tell me in what online contest the problem occured? i remember i have solved it, but i can't find the source

Thomas

Observer · Post by **Observer** » Fri Jul 25, 2003 5:26 pm

Hello???!!! Still haven't got any assistance....

titid_gede · Post by **titid_gede** » Fri Jul 25, 2003 5:57 pm

i have no idea.. since i'm pretty sure that if you got AC in highways you will get AC in connect to campus. have you check your input / output?
do you mind if you post your full source code?

Observer · Post by **Observer** » Sat Jul 26, 2003 4:19 am

-- Post removed by Observer --

Observer · Post by **Observer** » Thu Jul 31, 2003 9:23 am

-- Post removed by Observer --

Observer · Post by **Observer** » Wed Aug 06, 2003 12:58 pm

Hello??!?! Why no-one can help me......

little joey · Post by **little joey** » Wed Aug 06, 2003 1:32 pm

Dear Observer,

Please don't yell at us if we don't reply to your posts.

If you get no reply it can have several reasons:
- people don't know the answer;
- people don't care to answer;
- people can't understand your code.

The last reason applies to me. Your code is very hard to understand because you don't give comments, you use cryptic one-letter variable names, your indentation is weird, and last of all, you only give us part of it.
Publish your full code (like titid_gede asked), or PM it to me, and I'll have a go at it. My Pascal solution is AC, so I might find your bugs.

-little joey

Observer · Post by **Observer** » Wed Aug 06, 2003 4:34 pm

Excuse me, but you can't say something is weird only because it's different from the ones you use!!!

Explanation of variable names:
i, j, k, p, q are just loop counters or dummy variables;
tt : store the total length;
xc, yc : store the coordinates of the "nodes"
the use of other variables should be obvious...

I leave out the function declaration part because I'm pretty sure that it's correct. I deliberately cut it off to shorten your time to read my code (I've applied the sorting function in hundreds of other programs, and they proved that my sorting code is flawless...).

Comments are omitted, because most of the users here know Kruskal's algorithm quite well. But if you think they're useful, I'll try to add some...

P.S. Since I applied this MST code in some other occasions and got ACC (esp. 10147 Highways), the most possible error in my code is input/output I think. Is my eof statement wrong? Or are there any other i/o bugs?