Register to reply

Swedish programming olympics finals 2005

by ponjavic
Tags: 2005, finals, olympics, programming, swedish
Share this thread:
ponjavic
#1
Apr20-05, 11:54 AM
P: 226
Hello
I've recently qualified for the finals of the Swedish programming olympics.
Last year I finished 6th in Sweden with 4th being enough to qualify for the world championships and I'd like to improve my skills before the

contest next week. Therefore I'm trying to finish earlier contests' assignments and I would like some of you to help me.
Oh btw the competition is for high school students.

Here are some of the tasks I need help with. The tasks can be viewed at
http://www.syd.kth.se/po/FINAL02.pdf
but they're in Swedish so I will try to make a translation here.
Currently these are the tasks I need help with, the page might be updated later if I manage to solve them or if you've helped me.

Nr 1: Nattlig förflyttning or nightly transportation:
On one side of a bridge, a dark autumn night, there is n, 3 <= n <= 7 persons who all wish to get to the other side of the bridge. Since it

is so dark, a flashlight is needed when crossing the bridge. The group has only one and since the transportation should be as safe as

possible, only two persons at one time can get over. The time which takes a person to get over varies. When two persons go over the time of

the slowest determine the speed.

Write a program which recieves data about the group's size n and the time (in minutes) for every individual to get over the bridge,

t1,t2...tn, and which determines the shortest time it takes the whole group to get over the bridge.

Input: A dialog similar to this one

Groupsize: 4
Time for person A : 1
Time for person B : 5
Time for person C : 2
Time for person D : 10

Output: Only one line
The transportation takes 17 minutes.

Comment: There are almost many possibilities which lead to the same optimum time. This is one example with the time taken in paranthesis. A

and C crosses (2). A goes back (3). B and D crosses (13). C goes back (15). A and C crosses (17).

Edit: more testdata:
Gruppstorlek: 5
1 2 3 4 5
Svar: 16

Gruppstorlek: 6
10 1 20 25 30 35
Svar: 112

Gruppstorlek: 7
8 18 7 12 15 10 19
Svar: 105

I'm sure this doesn't need translation...
/Edit

P.S: I've manage to write a program which solves this.
The program puts all the times in a list and then tries every possibility by removing two from the left side list and putting them in the

right side. It then checks if the left side is empty and checks if the time taken is less than the best before this.
Then it also tries to put one from the right side to the left side and restarts (recursive function).
Now the problem is that the program works for persons up til 6 but for 7 persons it takes too much tima (1 min is max) so I need to optimate

this but how? Do you have another solution or ideas for optimization please tell me...

EDIT********
Solved thanks to salty dog, nice little algo, I was to stupid to look at the comment :D
//Edit

Nr 5: Motorvägar or Highways
The goverment in Motor Town has decided to rebuild a couple of national roads to highways, so that it is possible to travel between any two towns in the country by solely driving on high ways. Since they are expensive to build the goverment doesn't want to rebuild more road than necessary, so the goal is to minimize the total distance of rebuilt road.

Write a program that reads the country's roads and calculates which roads should be rebuilt into highways so that the goal is achieved. Some of the roads in the country can allready be highways. Naturally these don't have to be rebuilt. It is not allowed to build a motorway between two towns that aren't allready connected by a national road.

Input: The program reads input from motor.dat. The first line in the file holds two whole numbers n,(2<n<200) which tell the amount of cities in Motor Town, and m(1<m<5000) which tells the amount of roads. After that n rows follow including all the towns in Motor Town.

After this 4m lines that describes the roads. Each group of four lines holds the name of two cities connected by a road, the lenght of the row (1-1000) and an R or an M telling if it's a national road or a highway.

Output: the program should write the least distance of national road that has to be rebuilt in order to get from any town to any other driving solely on highways.
The least required distance that has to be rebuilt is 109. (see example in link)

P.S: My only thought is trying all combinations of rebuilt and not rebuilt roads and then checking if it is possible to get from all towns to eachother but with 5000 roads this seems very excessive 2^5000 lots of operations :P anyone have any better ideas?

Nr 6: Ett markan problem or "stupid swedish joke which can't be translated"
Successful farmer Sven owns a big fenced rectangular piece of land. He has let the piece of land be split up into smaller areas by building

the fence so that every smaller area is totally surrounded by the fence. All fences are straight and places parallel with the outer

boundaries.

Now Sven's oldest son, Peter, is going to get married and as a wedding gift he will get one of these smaller areas. Peter naturally will

want the biggest area (counted by square meters) but since Sven has been difficult and split the land in a complicated way it is not that

easy to determine which area is the biggest. Help Peter solve the problem by writing a program that determines which area has the biggest

(area?) square meters.

Input: The program will get data from the file mark.dat. The file starts with three whole numbers, b, (0 < b <= 40000), h,(0 < h <=40000)

and n, (4 <= n <= 50) on the first row separated by " ". b and h tells the width and the height of the piece of land and n tells the number

of fences on Sven's grounds. After this comes n rows with 4 whole numbers on each line, x1, y1, x2, y2(0<=x1,x2<=b,0<=y1,y2<=h) which tells

the start and ending points of a fence. The lower left corner of Sven's area has the coordinates (0,0) and the top right (b,h).

You can assume that the four fences, which are the boundaries, are included in the list of fences and also that no fences crosses or overlap

eachother. Here is an example of a file.
13 8 12
0 0 13 0
13 0 13 8
13 8 0 8
0 8 0 0
5 0 5 5
5 5 3 5
3 5 3 8
5 3 9 3
9 3 9 8
11 4 13 4
11 4 11 6
11 6 13 6

Output: the area(square meters) of the biggest area.
The biggest area has the area 40 square meters.

Comment: (use the datatype long in C/C++ or longint in Pascal to be sure the answer fits the variable)

P.S:
I simply can't solve this for big numbers. Currently my program creates a map {int map[width][height]} and also a {bool mapT[widht][height]}

and puts all the fences into the map then it runs through all squares and starts a recursive function that goes through all the possible

movements in the fence and makes all passed squares true and counts how many squares been passed. Then pushes the value to a list of all

areas. Then it finds next square which isn't true and starts this again. Now this works for small b, h but since tha maximum possible

widht/height is 40000 my solution is impossible I can't even make an array map[40000][40000]. Do you have any better ideas or way to

optimize my solution?

Ok I have more tasks but let's start with these two and if I get good response/help I'll add more ;)

Also please tell me if there's any errors in this post and if any clarification is needed or even if it isn't appropriate for this forum, lot's of thanks!
Phys.Org News Partner Science news on Phys.org
Security CTO to detail Android Fake ID flaw at Black Hat
Huge waves measured for first time in Arctic Ocean
Mysterious molecules in space
ramollari
#2
Apr20-05, 12:54 PM
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
saltydog
#3
Apr20-05, 01:05 PM
Sci Advisor
HW Helper
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.

saltydog
#4
Apr20-05, 01:22 PM
Sci Advisor
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.
ponjavic
#5
Apr20-05, 01:40 PM
P: 226
Quote 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...
ponjavic
#6
Apr20-05, 01:41 PM
P: 226
Quote 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
ponjavic
#7
Apr20-05, 01:52 PM
P: 226
ok solved first now any ideas for 6th?
saltydog
#8
Apr20-05, 02:03 PM
Sci Advisor
HW Helper
P: 1,593
Quote 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!
ponjavic
#9
Apr20-05, 02:24 PM
P: 226
Quote 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.
dduardo
#10
Apr21-05, 12:00 PM
Emeritus
dduardo's Avatar
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/
BicycleTree
#11
Apr21-05, 06:59 PM
P: 552
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.
Alkatran
#12
May6-05, 11:17 PM
Sci Advisor
HW Helper
Alkatran's Avatar
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!
BicycleTree
#13
May6-05, 11:50 PM
P: 552
Time is a factor; he said it has to execute in less than a minute.
BicycleTree
#14
May6-05, 11:52 PM
P: 552
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.


Register to reply

Related Discussions
What is my Swedish math degree equivalent to? Academic Guidance 8
Swedish Election Results Current Events 1
Swedish Jeans bringing antichrist to US... General Discussion 15
Longest Swedish Domain Name General Discussion 4