USA Computing Olympiad
Go back to the Math Jam ArchiveUSA International Olympiad in Informatics coach Rob Kolstad and past IOI team member (and gold medalist) Alex Schwendner will discuss the USA Computing Olympiad.
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
Facilitator: Rob Kolstad
robkolstad19:30:28
I'm Dr. Rob Kolstad, head coach of the USA Computing Olympiad. I'm joined from MIT by Alex Schwendner, a multiple gold medal winner at the International Olympiad in Informatics. Alex coaches at our camp along with Brian Dean, Percy Liang, and Richard Peng, all IOI medalists.
I'm Dr. Rob Kolstad, head coach of the USA Computing Olympiad. I'm joined from MIT by Alex Schwendner, a multiple gold medal winner at the International Olympiad in Informatics. Alex coaches at our camp along with Brian Dean, Percy Liang, and Richard Peng, all IOI medalists.
robkolstad19:30:43
The USA Computing Olympiad (USACO) promotes pre-college computing by running half
a dozen challenging computing competitions throughout the school year. The top 1
5 or so competitors get to go to the USA Invitational Computing Olympiad for a 9-
day camp in early June at the University of Wisconsin-Parkside, south of Milwaukee. The top four eligible competitors attend the International Olympiad on Informatics (IOI) during August -- this year in Egypt!
The USA Computing Olympiad (USACO) promotes pre-college computing by running half
a dozen challenging computing competitions throughout the school year. The top 1
5 or so competitors get to go to the USA Invitational Computing Olympiad for a 9-
day camp in early June at the University of Wisconsin-Parkside, south of Milwaukee. The top four eligible competitors attend the International Olympiad on Informatics (IOI) during August -- this year in Egypt!
robkolstad19:31:02
The contests draw about 1,000 competitors from about 60 countries across three divisions -- Gold, Silver, and Bronze -- offering a wide range of exciting computing problems. Winners are immortalized on the USACO web pages at http://www.usaco.org. Winners in the Gold division are prime targets for USAICO camp invitations.
The contests draw about 1,000 competitors from about 60 countries across three divisions -- Gold, Silver, and Bronze -- offering a wide range of exciting computing problems. Winners are immortalized on the USACO web pages at http://www.usaco.org. Winners in the Gold division are prime targets for USAICO camp invitations.
robkolstad19:31:24
A typical contest includes three programming tasks at each of three levels (Bronze, Silver, and the elite Gold). Contestants write solutions to these three tasks in C, C++, Pascal, and/or Java. The tasks at the Silver and Bronze levels are "algorithmic in nature" and generally require solutions that either use well-known a
lgorithms to speed solution of the task or require creation of an "ad hoc" technique on the fly.
A typical contest includes three programming tasks at each of three levels (Bronze, Silver, and the elite Gold). Contestants write solutions to these three tasks in C, C++, Pascal, and/or Java. The tasks at the Silver and Bronze levels are "algorithmic in nature" and generally require solutions that either use well-known a
lgorithms to speed solution of the task or require creation of an "ad hoc" technique on the fly.
robkolstad19:31:45
The solutions are submitted over the web to our grading system which runs the submissions multiple times with ever more challenging test data, assessing scores depending on the success of the submission. Scores are generally reported as points out of 1,000 or so possible.
The solutions are submitted over the web to our grading system which runs the submissions multiple times with ever more challenging test data, assessing scores depending on the success of the submission. Scores are generally reported as points out of 1,000 or so possible.
robkolstad19:32:01
Participating in one of the monthly online contests takes three hours (invested anytime over the 4.5 days of the contest). Results come shortly after the contest. The March contest starts this Thursday evening and ends early Tuesday morning.
Participating in one of the monthly online contests takes three hours (invested anytime over the 4.5 days of the contest). Results come shortly after the contest. The March contest starts this Thursday evening and ends early Tuesday morning.
robkolstad19:32:22
The U S Open, April's big contest, is the annual big 4 hour contest that, for USA students, requires a supervisor (known as a proctor). It is slated for the single day: 24 April. Proctors are responsible adults (teacher, parent, librarian, neighbor, friend, clergy, etc.) who will testify that a competitor did not break th
e rules during the 4 hours.
The U S Open, April's big contest, is the annual big 4 hour contest that, for USA students, requires a supervisor (known as a proctor). It is slated for the single day: 24 April. Proctors are responsible adults (teacher, parent, librarian, neighbor, friend, clergy, etc.) who will testify that a competitor did not break th
e rules during the 4 hours.
robkolstad19:32:33
We're looking to increase participation and get feedback from current and potential competitors. What's on your mind?
We're looking to increase participation and get feedback from current and potential competitors. What's on your mind?
robkolstad19:33:47
Whic is to say: We're open for questions!
Whic is to say: We're open for questions!
robkolstad19:33:59
Or perhaps you'd like to see a little programming problem?
Or perhaps you'd like to see a little programming problem?
robkolstad19:36:10
Do any of you write programs?
Do any of you write programs?
someperson01_219:36:13
Yup
Yup
robkolstad19:37:04
We have a worldwide subscription of about 1,000 folks from 60 countries. We accept entries from around the world, including cuba, iran, and all sorts of places that one might not expect.
We have a worldwide subscription of about 1,000 folks from 60 countries. We accept entries from around the world, including cuba, iran, and all sorts of places that one might not expect.
robkolstad19:38:36
The USOpen is, generally, open to anyone, including pre-college students (which includes pre-high school) and also post high school students, who are entered as 'observers'
The USOpen is, generally, open to anyone, including pre-college students (which includes pre-high school) and also post high school students, who are entered as 'observers'
robkolstad19:38:46
[sleepsta asked who can participate]
[sleepsta asked who can participate]
sleepsta19:39:04
the us open is also divided up to ranks?...or is all the questions about silver or gold level?
the us open is also divided up to ranks?...or is all the questions about silver or gold level?
robkolstad19:39:05
someperson asks about qualifying for higher level material
someperson asks about qualifying for higher level material
robkolstad19:39:19
Generally, new folks start out in the 'Bronze' division
Generally, new folks start out in the 'Bronze' division
robkolstad19:39:35
As soon as you do well (potentially even in the same contest), you can be promoted ot the next level
As soon as you do well (potentially even in the same contest), you can be promoted ot the next level
robkolstad19:39:45
The rare competitor does three sets of problems in one contest
The rare competitor does three sets of problems in one contest
robkolstad19:40:03
sleepsta asks what level the quetsions will be on the US Open
sleepsta asks what level the quetsions will be on the US Open
robkolstad19:40:15
Three divisions: you are invited to Bronze if you haven't entered before and can move up
Three divisions: you are invited to Bronze if you haven't entered before and can move up
robkolstad19:40:20
so the ansewr is "all three levels"
so the ansewr is "all three levels"
Anaxerzia_219:40:26
How much coding should you know to enter?
How much coding should you know to enter?
robkolstad19:40:29
LWu asks about java
LWu asks about java
robkolstad19:40:42
Java is accepted and is one of the languages we use in the competition
Java is accepted and is one of the languages we use in the competition
robkolstad19:41:02
The elite competitors rarely use Java because it is *not* supported at the international olympiad, the IOI
The elite competitors rarely use Java because it is *not* supported at the international olympiad, the IOI
robkolstad19:41:09
it also has slight execution speed issues
it also has slight execution speed issues
robkolstad19:41:31
Right -- us open has ranks
Right -- us open has ranks
robkolstad19:41:34
well, *divisions*
well, *divisions*
alexrs19:42:23
I'd say that once you can read and write simple files, do some math in a computer program,
I'd say that once you can read and write simple files, do some math in a computer program,
alexrs19:42:39
and print out little triangles of *'s, you can get something out of the contest.
and print out little triangles of *'s, you can get something out of the contest.
robkolstad19:42:49
We have a bunch of contests online at the contest site: http://contest.usaco.org. You can see how hard they are. This next contest wants you to be able to use arrays at the lowest level.
We have a bunch of contests online at the contest site: http://contest.usaco.org. You can see how hard they are. This next contest wants you to be able to use arrays at the lowest level.
alexrs19:42:52
There's a huge amount after that!
There's a huge amount after that!
alexrs19:43:20
We try very hard to provide a wide range of problems to challenge everyone.
We try very hard to provide a wide range of problems to challenge everyone.
poojacp19:39:59
what about middle school students??
what about middle school students??
robkolstad19:43:32
Middle s. students are welcome.
Middle s. students are welcome.
robkolstad19:43:50
There's a guy in Belarus who is 13 and is tearing up the contests... he won a gold medal at last year's IOI in Croatia.
There's a guy in Belarus who is 13 and is tearing up the contests... he won a gold medal at last year's IOI in Croatia.
alexrs19:43:51
I first came to the camp as a middle school student, some years ago.
I first came to the camp as a middle school student, some years ago.
SplashD19:41:14
Who can you get to be a proctor for the US Open?
Who can you get to be a proctor for the US Open?
robkolstad19:44:22
Proctors: Any responsible adult, including parents, librarians, older friends, teachers... anyone who can be trustworthy.
Proctors: Any responsible adult, including parents, librarians, older friends, teachers... anyone who can be trustworthy.
Lawrence Wu19:45:00
what's the best language? and what are we programming?
what's the best language? and what are we programming?
alexrs19:45:09
As for language, we support C, C++, Java, and Pascal. Which is best depends on what you're most comfortable with.
As for language, we support C, C++, Java, and Pascal. Which is best depends on what you're most comfortable with.
alexrs19:45:25
Although as Rob says, Java has some minor speed issues.
Although as Rob says, Java has some minor speed issues.
robkolstad19:45:37
Here's a typical "easy" task
Here's a typical "easy" task
balogne19:46:06
what is the usaco?
what is the usaco?
robkolstad19:46:08
Consider a number triangle. Write a program that calculates the
highest sum of numbers that can be passed on a route that starts
at the top and ends somewhere on the base. Each step can go either
diagonally down to the left or diagonally down to the right.
Consider a number triangle. Write a program that calculates the
highest sum of numbers that can be passed on a route that starts
at the top and ends somewhere on the base. Each step can go either
diagonally down to the left or diagonally down to the right.
robkolstad19:46:17
The route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
The route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.
robkolstad19:46:28
the 7, of course, aligns at the top
the 7, of course, aligns at the top
robkolstad19:46:34
now, programmers, how do you approach that?
now, programmers, how do you approach that?
Anaxerzia_219:47:06
itds 7-3-7-5
itds 7-3-7-5
someperson01_219:47:06
brute force all possibilities
brute force all possibilities
Anaxerzia_219:47:12
73875
73875
robkolstad19:47:34
well the question is not "What's the answer", the question is "how to do it" -- someperson points out that you can brute-force the possibilities
well the question is not "What's the answer", the question is "how to do it" -- someperson points out that you can brute-force the possibilities
robkolstad19:47:39
which isn't so bad for a triangle with 5 rows
which isn't so bad for a triangle with 5 rows
robkolstad19:47:43
but suppose the triangel has, e.g,. 5000 rows
but suppose the triangel has, e.g,. 5000 rows
robkolstad19:47:47
*triangle
*triangle
SplashD19:47:48
dynamic programming
dynamic programming
poojacp19:47:54
using recursion
using recursion
robkolstad19:47:55
now, how long does it take to brute force the answer?
now, how long does it take to brute force the answer?
someperson01_219:48:01
> 1 second
> 1 second
poojacp19:48:05
use recursive method
use recursive method
robkolstad19:48:24
SplashD has a good suggestion we're going to wait on for a moment....
SplashD has a good suggestion we're going to wait on for a moment....
robkolstad19:48:32
well, how many possibilities are there?
well, how many possibilities are there?
Lawrence Wu19:48:44
5000!
5000!
robkolstad19:48:45
for the height 5 triangle, one can well imagine going left or right on the first row, that's 2 choices
for the height 5 triangle, one can well imagine going left or right on the first row, that's 2 choices
robkolstad19:49:03
then for each of those 2 choices there are a couple choices and so it goes,
then for each of those 2 choices there are a couple choices and so it goes,
robkolstad19:49:06
doubling at every leve, eh?
doubling at every leve, eh?
Lawrence Wu19:49:12
2^5000...brute force would take a long time even for a computer
2^5000...brute force would take a long time even for a computer
robkolstad19:49:50
yeah, that'd be 10^0.301*5000 which is like 10^1500+
yeah, that'd be 10^0.301*5000 which is like 10^1500+
robkolstad19:50:07
and since the time limit is one second, you only get a few million (or few hundred million) operations
and since the time limit is one second, you only get a few million (or few hundred million) operations
robkolstad19:50:27
but what if you looked at the triangle backwards:
but what if you looked at the triangle backwards:
robkolstad19:50:32
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
robkolstad19:50:47
instead of start at the 7 (as the problem cleverly leads you), what if you started at the bottom?
instead of start at the 7 (as the problem cleverly leads you), what if you started at the bottom?
robkolstad19:51:00
You could choose between 4,5 5,2 2,6 and 6,5
You could choose between 4,5 5,2 2,6 and 6,5
robkolstad19:51:06
and use that result to guide the choices on the line before that
and use that result to guide the choices on the line before that
robkolstad19:51:11
and so on back up to the top
and so on back up to the top
robkolstad19:51:31
and that reduces the "computational complexity" back to something like N^2 (i.e., double N and the problem takes 4 times as long to solve)
and that reduces the "computational complexity" back to something like N^2 (i.e., double N and the problem takes 4 times as long to solve)
robkolstad19:51:38
and, as splashd points out:
and, as splashd points out:
Anaxerzia_219:51:49
How would you go about guiding the choices?
How would you go about guiding the choices?
robkolstad19:52:00
that's called dynamic programming if you do it in a prescribed way
that's called dynamic programming if you do it in a prescribed way
robkolstad19:52:33
Consider the left side of the pyramid
Consider the left side of the pyramid
robkolstad19:52:44
and focus on the next to bottom row
and focus on the next to bottom row
robkolstad19:52:56
the 2 must choose between 4,5; the 7 must choose between 5,2; and so on
the 2 must choose between 4,5; the 7 must choose between 5,2; and so on
robkolstad19:53:07
I think the two should choose the 5 in order to maxmize the sum
I think the two should choose the 5 in order to maxmize the sum
robkolstad19:53:12
likewise, the 7 should choose the 5
likewise, the 7 should choose the 5
robkolstad19:53:18
and the 4 should choose the 6, twice
and the 4 should choose the 6, twice
robkolstad19:53:41
so by combining those intermediate sums, the next-to-last row can become 7, 12, 10, 10
so by combining those intermediate sums, the next-to-last row can become 7, 12, 10, 10
robkolstad19:53:47
and then just iterate back up to the top :)
and then just iterate back up to the top :)
robkolstad19:54:15
Want to see another one?
Want to see another one?
someperson01_219:54:21
please
please
someperson01_219:54:31
a harder level problem?
a harder level problem?
robkolstad19:54:34
Given a sequence of N (10 < N < 10000) numbers, e.g.:
68 69 54 64 68 64 70 67 78 62 98 87
Find the longest strictly decreasing subsequence.
Given a sequence of N (10 < N < 10000) numbers, e.g.:
68 69 54 64 68 64 70 67 78 62 98 87
Find the longest strictly decreasing subsequence.
robkolstad19:54:52
This one is slightly harder; Alex is going to take it.
This one is slightly harder; Alex is going to take it.
alexrs19:55:09
How long with a recursive solution take?
How long with a recursive solution take?
Anaxerzia_219:55:31
you would in general prefer larger numbers
you would in general prefer larger numbers
someperson01_219:55:33
N^2?
N^2?
alexrs19:55:46
How many subsequences would there be if we wanted to check each one>
How many subsequences would there be if we wanted to check each one>
alexrs19:55:47
?
?
alexrs19:55:59
It doesn't have to be a contiguous subsequence
It doesn't have to be a contiguous subsequence
robkolstad19:56:17
Any guesses?
Any guesses?
SplashD19:56:29
2^N
2^N
someperson01_219:56:30
2^N?
2^N?
Anaxerzia_219:56:47
2^n
2^n
alexrs19:56:52
Right!
Right!
alexrs19:57:23
Remember, N can be up to 10000.
Remember, N can be up to 10000.
alexrs19:57:26
So will this work?
So will this work?
someperson01_219:57:59
no; maybe start from the max. elements in the set?
no; maybe start from the max. elements in the set?
robkolstad19:58:00
I think 2^10000 takes longer htan one second of CPU time
I think 2^10000 takes longer htan one second of CPU time
alexrs19:58:15
Will that always work?
Will that always work?
alexrs19:58:23
What if the max element is the last one?
What if the max element is the last one?
someperson01_219:58:37
Then jump to the next max one.
Then jump to the next max one.
alexrs19:58:59
What if the two biggest elements are the last two?
What if the two biggest elements are the last two?
alexrs19:59:26
Think about 5 4 3 2 1 6 7 8.
Think about 5 4 3 2 1 6 7 8.
someperson01_219:59:42
a sequence of length n means that you don't have to check the last n numbers?
a sequence of length n means that you don't have to check the last n numbers?
alexrs20:00:24
No. We might have 5 4 3 2 1 6 7 8 0
No. We might have 5 4 3 2 1 6 7 8 0
alexrs20:00:32
Then, we'd need to check for the last 0.
Then, we'd need to check for the last 0.
alexrs20:00:41
So the best is 5 4 3 2 1 0
So the best is 5 4 3 2 1 0
someperson01_220:00:44
Sorry, I mean for the starting index of the sequence
Sorry, I mean for the starting index of the sequence
alexrs20:01:46
Look at 1 9 2 8 3 7 4 7 5 6
Look at 1 9 2 8 3 7 4 7 5 6
alexrs20:02:16
The best here is 9 8 7 6
The best here is 9 8 7 6
alexrs20:02:43
(or 9 8 7 5 or 9 8 7 4 etc.)
(or 9 8 7 5 or 9 8 7 4 etc.)
alexrs20:03:07
Let's think about working backwards like robkolstad did for number triangles.
Let's think about working backwards like robkolstad did for number triangles.
alexrs20:03:51
Let's ask ourselves "what's the length of the longest decreasing subsequence starting at index i?"
Let's ask ourselves "what's the length of the longest decreasing subsequence starting at index i?"
alexrs20:04:04
So for 5 3 4 2 9
So for 5 3 4 2 9
Anaxerzia_220:04:15
start with longest increasing sequence
start with longest increasing sequence
alexrs20:04:22
The longest decreasing subsequence starting with 4 is 4 2 9
The longest decreasing subsequence starting with 4 is 4 2 9
alexrs20:05:05
We're looking for decreasing subsequences...
We're looking for decreasing subsequences...
Anaxerzia_220:05:22
look for the increasing sequence in the reverse sequence
look for the increasing sequence in the reverse sequence
alexrs20:05:39
Sure. It's the same thing.
Sure. It's the same thing.
alexrs20:05:58
Then, when we look at 3, we see that we can prepend 3 to "2". We can also prepend 5 to "4 2" or "3 2".
Then, when we look at 3, we see that we can prepend 3 to "2". We can also prepend 5 to "4 2" or "3 2".
alexrs20:06:07
So we'll work backwards.
So we'll work backwards.
alexrs20:06:29
For each number, we'll calculate and remember the length of the longest decreasing subsequence starting there.
For each number, we'll calculate and remember the length of the longest decreasing subsequence starting there.
alexrs20:06:50
Then, to figure out how long a subsequence we can make starting at a new number,
Then, to figure out how long a subsequence we can make starting at a new number,
alexrs20:07:07
we try prepending it to the sequence starting at each smaller number coming later.
we try prepending it to the sequence starting at each smaller number coming later.
alexrs20:07:18
Make sense?
Make sense?
alexrs20:07:26
How long will this take to run?
How long will this take to run?
Anaxerzia_220:08:22
not long
not long
alexrs20:08:31
The key is that we eleminate huge amounts of re-testing of answers by remembering the answers to subproblems.
The key is that we eleminate huge amounts of re-testing of answers by remembering the answers to subproblems.
alexrs20:08:34
How long?
How long?
Anaxerzia_220:08:40
n^2
n^2
alexrs20:08:50
Right. It's a lot better than 2^n!
Right. It's a lot better than 2^n!
Anaxerzia_220:08:59
why is it n^2?
why is it n^2?
ahuang20:09:31
for each number, you try once for each smaller number after it
for each number, you try once for each smaller number after it
alexrs20:10:02
Right. We need to calculate N numbers: the length of the subsequence starting at each point, and each takes N trials, as ahuang points out.
Right. We need to calculate N numbers: the length of the subsequence starting at each point, and each takes N trials, as ahuang points out.
alexrs20:10:20
So testing N things for each of N numbers takes N^2 time.
So testing N things for each of N numbers takes N^2 time.
alexrs20:10:55
Does that make sense?
Does that make sense?
alexrs20:11:01
Do you want to see another problem?
Do you want to see another problem?
Anaxerzia_220:11:09
a easier one :)
a easier one :)
robkolstad20:11:29
Let's look at a different type of task.
Let's look at a different type of task.
robkolstad20:11:48
But before we do, I should point out that we have 100 of these sorts of problems online at our 'training pages' that
But before we do, I should point out that we have 100 of these sorts of problems online at our 'training pages' that
robkolstad20:11:53
accept your program and test it against our test data
accept your program and test it against our test data
robkolstad20:11:59
just upgraded the server, too :)
just upgraded the server, too :)
robkolstad20:12:13
like any good training, it starts out *real* easy
like any good training, it starts out *real* easy
robkolstad20:12:17
it escalates rapidly
it escalates rapidly
robkolstad20:12:27
Usually when we're down it's cuz of network problems
Usually when we're down it's cuz of network problems
robkolstad20:12:34
the servers were never unavailable for more than a few seconds
the servers were never unavailable for more than a few seconds
robkolstad20:12:46
I live in the country and the networking is not so reliable as we'd all like
I live in the country and the networking is not so reliable as we'd all like
robkolstad20:12:54
Let's try a different kind of challenge
Let's try a different kind of challenge
robkolstad20:13:02
Farmer John has been elected mayor of his town! One of his campaign
promises was to bring internet connectivity to all farms in the area.
He needs your help, of course.
Farmer John has been elected mayor of his town! One of his campaign
promises was to bring internet connectivity to all farms in the area.
He needs your help, of course.
robkolstad20:13:08
FJ ordered a high speed connection for his farm and is
going to share his connectivity with the other farmers. To minimize
cost, he wants to lay the minimum amount of optical fiber to connect
his farm to all the other farms.
FJ ordered a high speed connection for his farm and is
going to share his connectivity with the other farmers. To minimize
cost, he wants to lay the minimum amount of optical fiber to connect
his farm to all the other farms.
robkolstad20:13:14
Given a list of how much fiber it takes to connect each pair of
farms, you must find the minimum amount of fiber needed to connect them
all together. Each farm must connect to some other farm such that a
packet can flow from any one farm to any other farm.
Given a list of how much fiber it takes to connect each pair of
farms, you must find the minimum amount of fiber needed to connect them
all together. Each farm must connect to some other farm such that a
packet can flow from any one farm to any other farm.
robkolstad20:13:25
Take a moment to read this one....
Take a moment to read this one....
robkolstad20:14:18
So the first thing you do is conceptualize the problem: There's a set of "farms" (points on a grid) and you must connect them one way or another by minimizing the length of the connections.
So the first thing you do is conceptualize the problem: There's a set of "farms" (points on a grid) and you must connect them one way or another by minimizing the length of the connections.
robkolstad20:14:25
Let me turn this one over to Alex...
Let me turn this one over to Alex...
alexrs20:14:46
Thanks Rob. So what are your first thoughts?
Thanks Rob. So what are your first thoughts?
alexrs20:14:52
Anyone have ideas?
Anyone have ideas?
Anaxerzia_220:14:54
circles
circles
Anaxerzia_220:15:28
How bouat conntecting all with a circle and letting internal connections reigh?
How bouat conntecting all with a circle and letting internal connections reigh?
Anaxerzia_220:15:41
reign*
reign*
alexrs20:15:42
We're going to assume that we can only connect pairs of farms.
We're going to assume that we can only connect pairs of farms.
alexrs20:16:05
That is, fiber connections can only meet at farms.
That is, fiber connections can only meet at farms.
alexrs20:16:26
So we just want to figure out which pairs of farms to connect to each other
So we just want to figure out which pairs of farms to connect to each other
alexrs20:16:36
so that all of the farms are connected.
so that all of the farms are connected.
alexrs20:16:44
That is, so that there's a path between any two farms.
That is, so that there's a path between any two farms.
Anaxerzia_220:16:55
Bruteforce?
Bruteforce?
alexrs20:17:10
What would bruteforce mean here?
What would bruteforce mean here?
Anaxerzia_220:17:21
check all of the connections and find the minimal one
check all of the connections and find the minimal one
ahuang20:17:31
all sets of n-1 cables, for n farms
all sets of n-1 cables, for n farms
alexrs20:17:53
So how many possibilities is that?
So how many possibilities is that?
haoye20:18:00
there are (n) (n-1) / 2 connections
there are (n) (n-1) / 2 connections
robkolstad20:18:01
[I left out that there might be as many as 100 farms]
[I left out that there might be as many as 100 farms]
haoye20:18:13
and each can exist or not
and each can exist or not
haoye20:18:21
so 2^(n * (n-1) / 2)
so 2^(n * (n-1) / 2)
ahuang20:18:29
(n choose 2) choose n-1
(n choose 2) choose n-1
alexrs20:18:46
Right. And again, this is going to be really slow.
Right. And again, this is going to be really slow.
alexrs20:19:14
Let's think about building up a network a piece at a time.
Let's think about building up a network a piece at a time.
SplashD20:19:20
greedy algorithm
greedy algorithm
alexrs20:19:31
Since all farms have to get connected eventually, let's just start with one.
Since all farms have to get connected eventually, let's just start with one.
alexrs20:20:01
Right, greedy: we pick the closest farm and connect it to our first farm.
Right, greedy: we pick the closest farm and connect it to our first farm.
alexrs20:20:47
And then we connect the farm that closest to either of our two farms.
And then we connect the farm that closest to either of our two farms.
alexrs20:21:19
At each step, we add the farm that we can add most cheaply --- with the shortest new connection.
At each step, we add the farm that we can add most cheaply --- with the shortest new connection.
alexrs20:21:28
Is this going to work?
Is this going to work?
Anaxerzia_220:21:40
yes, but how would you code that?
yes, but how would you code that?
alexrs20:21:57
Well, first let's make sure that it's going to work.
Well, first let's make sure that it's going to work.
alexrs20:22:24
A lot of the simple ideas we might have come up with for buy low didn't work.
A lot of the simple ideas we might have come up with for buy low didn't work.
alexrs20:22:37
So why is this going to work?
So why is this going to work?
Anaxerzia_220:23:00
You can keep starting with different farms
You can keep starting with different farms
Anaxerzia_220:23:09
and finding the shortest connection
and finding the shortest connection
Anaxerzia_220:23:15
so only n to check
so only n to check
Anaxerzia_220:23:18
right?
right?
alexrs20:23:52
Well, to find the farm that we can add most cheaply,
Well, to find the farm that we can add most cheaply,
alexrs20:24:13
we need to check all pairs of a farm already in our connected set and a farm outside of it.
we need to check all pairs of a farm already in our connected set and a farm outside of it.
alexrs20:24:23
(We need to connect an old farm to a new one.)
(We need to connect an old farm to a new one.)
alexrs20:24:44
There could be around n of each, so that takes n^2 time.
There could be around n of each, so that takes n^2 time.
alexrs20:25:18
Then we have to do this n-1 times to get all n farms.
Then we have to do this n-1 times to get all n farms.
haoye20:25:19
we can save a little bit of time by keeping a table of distances to the non-connected farms and only compute new distances when we add a farm to the network
we can save a little bit of time by keeping a table of distances to the non-connected farms and only compute new distances when we add a farm to the network
haoye20:25:35
right?
right?
alexrs20:25:39
Good!
Good!
alexrs20:25:48
How fast does that make it?
How fast does that make it?
Anaxerzia_220:26:09
n
n
alexrs20:26:40
It takes N time to add one farm, so it takes about N^2 time to add all the farms.
It takes N time to add one farm, so it takes about N^2 time to add all the farms.
alexrs20:27:03
But let's go back to why this algorithm is correct.
But let's go back to why this algorithm is correct.
alexrs20:27:14
Say we're thinking about adding the shortest new connection.
Say we're thinking about adding the shortest new connection.
alexrs20:27:33
But say that the best solution involves adding a different, more expensive, connection.
But say that the best solution involves adding a different, more expensive, connection.
alexrs20:28:03
Then, we could add the cheaper edge and remove the more expensive edge, and the farms would still be connected.
Then, we could add the cheaper edge and remove the more expensive edge, and the farms would still be connected.
alexrs20:28:26
Everytime we have a problem like this, it's worth thinking through and proving why your solution works.
Everytime we have a problem like this, it's worth thinking through and proving why your solution works.
robkolstad20:28:54
These sorts of tasks are typical of those that we pose each month on our contests
These sorts of tasks are typical of those that we pose each month on our contests
robkolstad20:28:57
and, of course, in the training pages
and, of course, in the training pages
robkolstad20:29:09
If you find them interesitng, you might enjoy programming this sort of challenge.
If you find them interesitng, you might enjoy programming this sort of challenge.
robkolstad20:29:18
Any final questions before we close out? Time is almost up:)
Any final questions before we close out? Time is almost up:)
robkolstad20:29:59
I sure appreciate you all attending today.
I sure appreciate you all attending today.
robkolstad20:30:06
We have a forum at http://forum.usaco.org
We have a forum at http://forum.usaco.org
robkolstad20:30:13
and, of course, i'm always available on email
and, of course, i'm always available on email
robkolstad20:30:20
register at http://train.usaco.org to train and
register at http://train.usaco.org to train and
robkolstad20:30:27
contest.usaco.org to compete
contest.usaco.org to compete
robkolstad20:30:31
it's free :)
it's free :)
robkolstad20:30:33
Thanks again for coming.
Thanks again for coming.
robkolstad20:30:37
Later!
Later!
Anaxerzia_220:30:37
Yeah, I rally think these would be somehting to try in the future :)
Yeah, I rally think these would be somehting to try in the future :)
robkolstad20:30:51
They really are fun
They really are fun
robkolstad20:31:01
and it's cool to make computers do your bidding 100million times per second
and it's cool to make computers do your bidding 100million times per second
Anaxerzia_220:31:03
i thought it would be more coding, since i dont know too much, but know i think ill look into these
i thought it would be more coding, since i dont know too much, but know i think ill look into these
Anaxerzia_220:31:05
thanks a lot!
thanks a lot!
robkolstad20:31:23
bye for now
bye for now
alexrs20:31:36
Bye! Thanks everyone!
Bye! Thanks everyone!
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
