# Swedish programming olympics finals 2005

by ponjavic
Tags: 2005, finals, olympics, programming, swedish
 P: 453 I don't have any comment about your solution, but it is a general observation from me that these Olympics (Olympiads) usually test the ability to analyze algorithms where data is taken from an input file and results placed in an output file. I also saw this tendency in the International Informatics Olympiad 2004 in Athens ... The algorithms given are extremely difficult to deal with, but the programming skills are hardly tested. Regards
 HW Helper Sci Advisor P: 1,593 Hello Ponjavic, I wish to test a theory for the first one: Sort them first in ascending order. The objective is to always have a quick runner to go back to get the slow ones. Thus, first the fastest two go across, quick one goes back, then the two slowest runners go over, and the quick one left behind goes back. Start all over: Fastest two go over, leave less quick over with the fastest one going back to get the next two slower ones which walk across. Fast one left behind goes back and the cycle repeats. Is this the most optimum way? Think I'll wip-up a quick C++ program and check it out.
HW Helper
P: 1,593

## Swedish programming olympics finals 2005

Alright, I did this one by hand:

1
3
5
7
15
21
30
61
75
100

Using the logic above, I get 217 with number 1 always going back to pick up the slowest left, always leaving 3 behind to run back and pick him up for another go-round. Surely it can't be this easy and I'm inclinded to be suspicious of my algorithm just for that reason.
P: 226
 Quote by ramollari I don't have any comment about your solution, but it is a general observation from me that these Olympics (Olympiads) usually test the ability to analyze algorithms where data is taken from an input file and results placed in an output file. I also saw this tendency in the International Informatics Olympiad 2004 in Athens ... The algorithms given are extremely difficult to deal with, but the programming skills are hardly tested. Regards
I'm not sure if you mean shown to you in the task by "The algorithms given" if so this is not the case at all for the Swedish final. Here you either have to create your own algo, or find an appropriate one and implement it, so my question is really which algorithm could be used to solve these two problems.
I'd also mentione that the programming skills are very very important as the most important part of the tasks is not really to solve them you might get 1/2 out of five for that but to optimize them and I'm sure this also applies to the international competition...
P: 226
 Quote by saltydog Alright, I did this one by hand: 1 3 5 7 15 21 30 61 75 100 Using the logic above, I get 217 with number 1 always going back to pick up the slowest left, always leaving 3 behind to run back and pick him up for another go-round. Surely it can't be this easy and I'm inclinded to be suspicious of my algorithm just for that reason.
Actually it should be quite easy as it's the first question, maybe I've overdone it :P I'll look in to this and also post more input/output
 P: 226 ok solved first now any ideas for 6th?
HW Helper
P: 1,593
 Quote by ponjavic ok solved first now any ideas for 6th?
If so then that was just luck on my part. I regret making the comment about it being easy and don't wish to demotivate you as I'm sure you could blow my doors off (American for beat me) with other programming tasks. I'm also quite older than you and have had more time programming. Good luck!
P: 226
 Quote by saltydog If so then that was just luck on my part. I regret making the comment about it being easy and don't wish to demotivate you as I'm sure you could blow my doors off (American for beat me) with other programming tasks. I'm also quite older than you and have had more time programming. Good luck!
Don't worry I'm not going to get demotivated and it was quite easy compared to others I just couldn't find the solution, thank you very much =)
For every one of these there are maybe four I've done so I'm just trying to do all of them I'll add another one now.
 Emeritus P: 1,919 I don't have time now to look over the problems but if you need help practicing for the competition I would recommend this website: http://acm.uva.es/problemset/ There are a ton of problems to work on and when you think you have the correct solution just email them the program and you'll get a reply saying if the program was correct or incorrect. Another good website is: http://www.topcoder.com/
 P: 548 Well, a while ago I was browsing my discrete math book (which has about 3 full courses of material in it) and I came across algorithms for constructing minimal spanning trees of loop-free undirected graphs. The book covered Kruskal's Algorithm and Prim's Algorithm. Apparently there are a number of ways to implement these algorithms, some more efficient than others. Anyway, you can use one of these to solve the Motortown example. If you have two towns connected by a pre-existing highway then I think you can collapse the two towns as one node with all edges for either of the towns going into that node. After you condense as many towns as you can then you can apply a tree-spanning algorithm. Here is some information on Prim's and Kruskal's algorithms: http://www.cs.usask.ca/resources/tut.../prim/mst.html For the fence problem there is a formula (Heron's formula) for giving the area of a triangle with edges of length a, b, c. For each region, find a convex corner of the region and find the area of the triangle (call it area A) covering that corner. Then remove the corner point and you are left with a region of area B. Area B + area A = the area of the region; repeatedly apply the same technique to find area B. The hard part would probably be determining when the corner is convex. One way is, you could pick a region (finding regions by traversing the nodes) and at every step always find the area of and then remove the corner farthest away from any arbitrary point--that corner would always be convex. There is also a formula (so I think I have heard, talking somewhere on these forums a while ago) that lets you find the area of a region given the coordinates of its corners, but I don't know more about that.
 HW Helper Sci Advisor P: 944 Actually, you don't do the best by always sending the quick one across. Conside if there is: person a: 0 seconds person b: 5 seconds person b: 10 seconds person c: 20 seconds Best time according to you: 35 seconds actual best time: a cross with b, a goes back. b and c cross together, b goes back. a crosses with b. Total: 5 + 20 + 5 = 30 seconds. I'd suggest a simple and dirty solution because time isn't a factor. Check every possible combination and take the minimum!
 P: 548 Time is a factor; he said it has to execute in less than a minute.
 P: 548 typo: you had a b b c, it should be a b c d. Also, the main point of your post is wrong because the crossing order you describe is the order SaltyDog's algorithm produces.

 Related Discussions Academic Guidance 8 Current Events 1 General Discussion 15 General Discussion 4