Slashdot Mirror
ACM Programming Contest Results
An anonymous submitter writes: "Shanghai Jiao Tong University has won the 2002 ACM International Collegiate Programming Contest with six of nine problems solved. Also solving six problems were MIT (2nd), University of Waterloo (3rd), Tsinghua University (4th), and Stanford University (5th). You can view the problems online, as well as the final standings. Congratulations to all!"
I mean, how long do you spend writing a game and forget about basic fucking options?
Yah, eventually I found the dot-file to configure it, but PLEASE, this is ridiculous.
Now my whole weekend is ruined cause I spent 3 hours looking for the tux racer config file. FUCK!!!
SP
(I rule)
Is this article necessary? I could see posting it if an American team had won this contest, but exactly what kind of agenda are you trying to promote by prominently mentioning that the Chinese won? China is a Communist nation that engages in brutal (and all too often bloody) repression of its own citizens. I'm not saying that Slashdot should ignore China or post anti-China stuff at every opportunity, but the least it could do is avoid glorifying China. Remember 9/11? It's time to come together and rally around our nation, not a brutal totalitarian regime.
Could someone post a link with an ASCII/Postscript/html converted list of problems?
.
Thats the sound of those questions flying past way above my head...
Here are the final standings. Note how close Waterloo came to coming in at second place! (Note that only the first few items has penalty numbers attached to them)
Rank | Name | Solved | Penalty
1 Shanghai JiaoTong University 6 | 831
2 Massachusetts Institute of Technology 6 | 972
3 University of Waterloo 6 | 974
4 Tsinghua University 6 | 1186
5 Stanford University 6 | 1264
6 Saratov State University 5 | 532
7 Fudan University 5 | 678
8 Duke University 5 | 808
9 Moscow State University 5 | 856
10 Universidad de Buenos Aires 5 | 894
11 Charles University Prague 5
11 Royal Institute of Technology 5
11 Seoul National University 5
11 St Petersburg Institute of Fine Mechanics and Optics 5
11 University of New South Wales 5
11 University of Wisconsin - Madison 5
11 Warsaw University 5
18 Albert Einstein University Ulm 4
18 Belarusian State University 4
18 Novosibirsk State University 4
18 Petrozavodsk State University 4
18 POLITEHNICA University of Bucharest 4
18 Sharif University of Technology 4
18 The University of Tokyo 4
18 University of Oldenburg 4
18 University of Toronto 4
27 California Institute of Technology 3
27 Cornell University 3
27 Orel State Technical University 3
27 Queen's University 3
27 Sofia University 3
27 The Chinese University of Hong Kong 3
27 The University of Chicago 3
27 University of Calgary 3
27 University of California, San Diego 3
27 University of Central Florida 3
27 University of Otago 3
27 University of Texas at Austin 3
27 University of the Witwatersrand, Johannesburg 3
27 Virginia Tech 3
Honorable Mention
American International University Bangladesh Nanyang Technological University
Amir Kabir University of Technology National Chiao Tung University
Bangladesh University of Engineering and Technology National Taiwan University
Cairo University Saint Mary's University
Ecole Polytechnique Texas Tech University
Ewha Womans University Universidade de São Paulo
Florida Institute of Technology Universidade Federal de Pernambuco
Indian Institute of Technology - Kanpur University of Arkansas
Instituto Tecnológico de Ciudad Madero University of California at Berkeley
ITESM, Campus Monterrey University of Nebraska - Lincoln
LeTourneau University University of North Carolina
Messiah College University of Wisconsin - Parkside
Super-Region | Champion
Africa and the Middle East University of the Witwatersrand, Johannesburg
Asia Shanghai JiaoTong University
Europe Saratov State University
Latin America Universidad de Buenos Aires
North America Massachusetts Institute of Technology
South Pacific University of New South Wales
If you havent Acrobat you can use this..
Programming Contest World Finals
ok i'll try again
h tt p://icpc.baylor.edu/icpc/Finals/problems.pdf
http://access.adobe.com/perl/convertPDF.pl?url=
For those who are unable to view PDFs.
Here is the problems PDF in text format
Smart kids with $$$ goes to MIT.
Smart kids without $$$ goes else where.
Here is a Link to a HTML version of the PDF
Problems
I'm impressed that I can picture everything logicaly in my head, but that's quite a bit of code, interesting as it may be. How big were the teams and how much time did they have?
I'm a writer, a poet, a genius, I know it. I don't buy software, I grow it.
Here is a Link to a HTML version of the PDF
Problems
IT IS NOT Slashdotted already. Prove the fucking bastard that tried to karma whore wrong by clicking here
Nice Lie Shit For Brains!
Go waterloo!
"Caffeine is not an option. Caffeine is a way of life."
I've seen many school teachers IN NORTH AMERICA who don't have a clue about order of operations.
DUUURRRRRPP!!!!
Liberate your mind in two clicks or less.
Didn't the questions sound a little weird to you?
I bet the MPAA and RIAA invented these question to get free development work for creating their napster alternatives. The question about the indecipherable codes kind of alerted me then the others seem to fit together with my suspicions.
slashdot has some real stupid fucks on it.
Oh my i know how to use sed and awk am i just such a fucking genius, yippy for me.
I'm a huge brain that's why i dropped out of school and sit around babysitting unix boxes, becuase i'm a big genius.
slashdot is so fucking cheesy, holy shit.
Many of the ACM competitors from English speaking countries compete weekly at TopCoder.
College students and professionals alike compete against each other to solve 3-problem sets within 75 minutes (choice of C++ or Java or C#).
Under 18 are allowed to compete as well, but not eligible for prizes.
i can't read this drivel anymore, it's just pathetic.
That Fortran 90 wasn't one of the supported languages for the championship. They are allowing C, C++, Java, and Pascal. If you're a problem solver, you know your Fortran. And these are math problems, evidently. So I'm baffled as to why it's not an option. Before I see the deluge of "Fortran is dying" comments, it is still heavily used for engineering problem solving, I know for a fact, so don't give me that crap.
Page 2 - "This page is intentionally blank". IBM harking back to the good ol' days?
Dave
I write a blog now, you should be afraid.
0q9ncwrtoqitn cq00t8qnweqd foiuioa;r ewOR IOE RUR IOAWEOIR IDSHFD FH DFJH kldf kls;fjds h fhawr89w98ry df hkas dfhk3wrg hg35 435 5q jq4jklewrhjklsfhdjs jd hfjkls hfewory iaewrfi7yeraw7rftaw7 7 rfawe7yae rw ew97 ewayr8 9we0r7098u5 ur0oe;d; das ;dsoyfu ;oauify;jweah j hewahj lkeaw ewatkjt ew jltk 4litu iul25iu 5x2l 32il5uz x532iul 6cc u6i ciuq c235;lc25;3o clu25ic l c5 c4jh ghyn6jx4ku;l x25h c6khg6 c5jylk;c 24ui;o c4tiu uc6i 24c89 84y9tcewal k rceawh mnd dbnfcm dfads f,mhekrjlhewkajrlh weacrjh ctk 4coqtycq24yc4 84c c6498 c49q28 cq2498 498 cq9648 q34978 c4q9c y4t98 tuicw;iuatwc uiacwt ctaw uilwtckjl thc rcaej ckrathjk rtckj atcawc jkth akjwcthjct iawh lewcgawnct atncck3wuk4uca
Most likely the Shanghai Jiao Tong University students ate it. Chinee are like that; Eating dog heads when not building railroads.
Just make one person memorize the code for a scheme interpreter beforehand. Have him type it in at the beginning of the test (while the other students think about the problems), and voila -- your whole team suddenly becomes a couple-hundred IQ points smarter.
You just have to get used to writing scheme code embedded inside of a gigantic string constant...
If they only allowed Lisp. The problems are just begging for a CL implementation.
Balloons in a Box
Input: balloon.in
You must write a program that simulates placing spherical balloons into a rectangular box.
The simulation scenario is as follows. Imagine that you are given a rectangular box and a set of points. Each point represents a position where you might place a balloon. To place a balloon at a point, center it at the point and inflate the balloon until it touches a side of the box or a previously placed balloon. You may not use a point that is outside the box or inside a previously placed balloon. However, you may use the points in any order you like, and you need not use every point. Your objective is to place balloons in the box in an order that maximizes the total volume occupied by the balloons.
You are required to calculate the volume within the box that is not enclosed by the balloons.
Input
The input consists of several test cases. The first line of each test case contains a single integer n that indicates the number of points in the set (1 n 6). The second line contains three integers that represent the (x, y, z) integer coordinates of a corner of the box, and the third line contains the (x, y, z) integer coordinates of the opposite corner of the box. The next n lines of the test case contain three integers each, representing the (x, y, z) coordinates of the points in the set. The box has non-zero length in each dimension and its sides are parallel to the coordinate axes.
The input is terminated by the number zero on a line by itself.
Output
For each test case print one line of output consisting of the test case number followed by the volume of the box not occupied by balloons. Round the volume to the nearest integer. Follow the format in the sample output given below.
Place a blank line after the output of each test case.
Sample Input
2 0 0 0
10 10 10
3 3 3
7 7 7
0
Output for the Sample Input
Box 1: 774
Undecodable Codes
Input: codes.in
Phil Oracle has a unique ability that makes him indispensable at the National Spying Agency. His colleagues can bring him any new binary code and he can tell them immediately whether the code is uniquely decodable or not. A code is the assignment of a unique sequence of characters (a codeword) to each character in an alphabet. A binary code is one in which the codewords contain only zeroes and ones. For example, here are two possible binary codes for the alphabet {a, c, j, l, p, s, v}.
Code 1 Code 2
a 1 010
c 01 01
j 001 001
l 0001 10
p 00001 0
s 000001 1
v 0000001 101
The encoding of a string of characters from an alphabet (the cleartext) is the concatenation of the codewords corresponding to the characters of the cleartext, in order, from left to right. A code is uniquely decodable if the encoding of every possible cleartext using that code is unique. In the example above, Code 1 is uniquely decodable, but Code 2 is not. For example, the encodings of the cleartexts "pascal" and "java" are both 001010101010. Even shorter encodings that are not uniquely decodable are 01 and 10.
While the agency is very proud of Phil, he unfortunately gives only "yes" or "no" answers. Some members of the agency would prefer more tangible proof, especially in the case of codes that are not uniquely decodable. For this problem you will deal only with codes that are not uniquely decodable. For each of these codes you must determine the single encoding having the minimum length (measured in bits) that is ambiguous because it can result from encoding each of two or more different cleartexts. In the case of a tie, choose the encoding which comes first lexicographically.
Input
One or more codes are to be tested. The input for each code begins with an integer m, 1 <= m <= 20, on a line by itself, where m is the number of binary codewords in the code. This is followed by m lines each containing one binary codeword string, with optional leading and trailing whitespace. No codeword will contain more than 20 bits.
The input is terminated by the number zero on a line by itself.
Output
For each code, display the sequential code number (starting with 1), the length of the shortest encoding that is not uniquely decodable, and the shortest encoding itself, with ties broken as previously described. The encoding must be displayed with 20 bits on each line except the last, which may contain fewer than 20 bits. Place a blank line after the output for each code. Use the format shown in the samples below.
Sample Input
3
0
01
10
5
0110
00
111
001100
110
5
1
001
0001
00000000000000000001
10000000000000000000
0
Output for the Sample Input
Code 1: 3 bits
010
Code 2: 9 bits
001100110
Code 3: 21 bits
10000000000000000000
1
Crossing the Desert
Input: desert.in
In this problem, you will compute how much food you need to purchase for a trip across the desert on foot.
At your starting location, you can purchase food at the general store and you can collect an unlimited amount of free water. The desert may contain oases at various locations. At each oasis, you can collect as much water as you like and you can store food for later use, but you cannot purchase any additional food. You can also store food for later use at the starting location. You will be given the coordinates of the starting location, all the oases, and your destination in a two-dimensional coordinate system where the unit distance is one mile.
For each mile that you walk, you must consume one unit of food and one unit of water. Assume that these supplies are consumed continuously, so if you walk for a partial mile you will consume partial units of food and water. You are not able to walk at all unless you have supplies of both food and water. You must consume the supplies while you are walking, not while you are resting at an oasis. Of course, there is a limit to the total amount of food and water that you can carry. This limit is expressed as a carrying capacity in total units. At no time can the sum of the food units and the water units that you are carrying exceed this capacity.
You must decide how much food you need to purchase at the starting location in order to make it to the destination.
You need not have any food or water left when you arrive at the destination. Since the general store sells food only in whole units and has only one million food units available, the amount of food you should buy will be an integer greater than zero and less than or equal to one million.
Input
The first line of input in each trial data set contains n (2 n 20), which is the total number of significant locations in the desert, followed by an integer that is your total carrying capacity in units of food and water. The next n lines contain pairs of integers that represent the coordinates of the n significant locations. The first significant location is the starting point, where your food supply must be purchased; the last significant location is the destination; and the intervening significant locations (if any) are oases. You need not visit any oasis unless you find it helpful in reaching your destination, and you need not visit the oases in any particular order.
The input is terminated by a pair of zeroes.
Output
For each trial, print the trial number followed by an integer that represents the number of units of food needed for your journey. Use the format shown in the example. If you cannot make it to the destination under the given conditions, print the trial number followed by the word "Impossible."
Place a blank line after the output of each test case.
Sample Input
4 100
10 -20
-10 5
30 15
15 35
2 100
0 0
100 100
0 0
Output for the Sample Input
Trial 1: 136 units of food
Trial 2: Impossible
I checked this out a while earlier. It's nothing but an advertising pitch.
Try filling out the registration form; the whole thing is survey to gauge your knowledge of industry buzzwords ("Rate your ability at using Oracle databases from 1-5"). They really care nothing about your *skill* as a programmer.
I thought the point of this thing was to help differentiate among programmers, where the traditional means (of comparing buzzword-lists on resumes) was insufficient. This is just more of the same, but on a web site instead.
Hooray, we have another way for companies to pull our resumes off of the internet...
Input: ferries.in
Millions of years ago massive fields of ice carved deep grooves in the mountains of Norway. The sea filled these grooves with water. The Norwegian people call them fjords. This landscape of mountains and water is beautiful, but it makes traveling difficult. The usual scheme is: drive some kilometers, wait for a ferry, cross a fjord with the ferry, drive some more kilometers, and so on until the destination has been reached. To reach a destination as early as possible, most people have the following strategy: drive as fast as allowed (the maximum speed is 80 km/h) to the next ferry, and wait until it goes. Repeat until the destination has been reached.
Since driving fast requires more fuel than driving slow, this strategy is both expensive and harmful to the environment. The new generation of cruise control systems is designed to help. Given the route you want to go, these systems will gather information about the ferries involved, calculate the earliest possible time of arrival at the final destination, and calculate a driving scheme that avoids driving faster than needed. The systems will calculate your road speed so that you board the next ferry the moment it leaves.
Given a route (a sequence of road-pieces and crossings with ferries), you must write a program to calculate the minimal time it takes to complete this route. Moreover, your program must find a driving scheme such that the maximal driving speed at any point during the trip is as small as possible.
Input
The input file contains one or more test cases.
Each test case describes a route. A route consists of several sections, each section being either a piece of road or a crossing. The first line in the description contains a single number s (s > 0), which is the number of sections in the route. The next s lines contain the descriptions of the sections. Every line describing a section starts with two names: the place of departure and the place of arrival, followed by either the word 'road' or the word 'ferry' indicating what kind of section it is. If the section is a road, its length (a positive integer) is given in km. For example:
Dryna Solholmen road 32
Lines describing ferry sections have more information. Following the word "ferry", the duration of the ferry crossing, in minutes (a positive integer) is given. This is followed by the frequency f (f > 0) of the ferry, that is, the number of times the ferry departs in a single hour. The next f integers give the departure times of the ferry, in ascending order. For example:
Manhiller Fodnes ferry 20 2 15 35
The ferry travels from Manhiller to Fodnes in 20 minutes, and it leaves twice an hour (on 0h15, 0h35, 1h15, 1h35,...). The beginning of the entire trip always starts at a full hour. The sections in a route are consecutive, that is, if a section goes from A to B then the next section starts at B. Every route in the input can be traveled in no more than 10 hours.
The input is terminated by the number zero on a line by itself.
Output
Output for each test case is a single line containing three items. The first item is the test case number. The second is the total travel time for an optimal scheme in the form hh:mm:ss. The third item is the maximal road speed in an optimal scheme rounded to two digits to the right of the decimal point.
Place a blank line after the output of each test case.
Sample Input
1
Bygd Bomvei road 7
2
Ferje Overfarten ferry 20 2 5 25
Overfarten Havneby ferry 30 3 10 30 50
5
Begynnelse Brygge road 30
Brygge Bestemmelse ferry 15 4 10 25 40 55
Bestemmelse Veiskillet road 20
Veiskillet Grusvei road 25
Grusvei Slutt ferry 50 1 10
0
Output for the Sample Input
Test Case 1: 00:05:15 80.00
Test Case 2: 01:00:00 0.00
Test Case 3: 03:00:00 45.00
Iran is also the first place team at International Math Olympiad 1998 and the only team over 200 points and the only team that have a perfect score contestant. Yes, they beat Russia and USA.
Here is a problem from IMO 1998:
Consider all functions f:N->N such that f(t^2f(s))=s[f(t)]^2. Find (with proof) the minimum possible value of f(1998).
Iran is also the first place team at Intenational Physics Olympiad 1999. Yes, they beat China, Russia and USA.
Bear in mind that these are high school contest for high school students around the age of 16-17 years old.
Island Hopping
Input: islands.in
The company Pacific Island Net (PIN) has identified several small island groups in the Pacific that do not have a fast internet connection. PIN plans to tap this potential market by offering internet service to the island inhabitants. Each groups of islands already has a deep-sea cable that connects the main island to the closest internet hub on the mainland (be it America, Australia or Asia). All that remains to be done is to connect the islands in a group to each other. You must write a program to help them determine a connection procedure.
For each island, you are given the position of its router and the number of island inhabitants. In the figure, the dark dots are the routers and the numbers are the numbers of inhabitants. PIN will build connections between pairs of routers such that every router has a path to the main island. PIN has decided to build the network such that the total amount of cable used is minimal. Under this restriction, there may be several optimal networks. However, it does not matter to PIN which of the optimal networks is built.
PIN is interested in the average time required for new customers to access the internet, based on the assumption that construction on all cable links in the network begins at the same time.
Cable links can be constructed at a rate of one
kilometer of cable per day. As a result, shorter cable links are completed before the longer links. An island will have internet access as soon as there is a path from the island to the main island along completed cable links. If m[i] is the number of inhabitants of the i-th island and t[i] is the time when the island is connected to the internet, then the average connection time is:
====
\
> t * m
/ i i
====
--------------
====
\
> m
/ i
====
Input
The input consists of several descriptions of groups of islands. The first line of each description contains a single positive integer n, the number of islands in the group (n <= 50).
Each of the next n lines has three integers x[i], y[i], m[i], giving the position of the router (x[i], y[i]) and number of inhabitants mi (mi > 0) of the islands. Coordinates are measured in kilometers. The first island in this sequence is the main island.
The input is terminated by the number zero on a line by itself.
Output
For each group of islands in the input, output the sequence number of the group and the average number of days until the inhabitants are connected to the internet. The number of days should have two digits to the right of the decimal point. Use the output format in the sample given below.
Place a blank line after the output of each test case.
Sample Input
7
11 12 2500
14 17 1500
9 9 750
7 15 600
19 16 500
8 18 400
15 21 250
0
Output for the Sample Input
Island Group: 1 Average 3.20
I remember years past when I was on the team competing for my university. Locals, not International. One year we had several of our guys graduate (IIRC), and were short on filling in with CS students. Well, we ended up with a Chemical Engineer who could program, and I tell you it was a blessing. He brought a whole different viewpoint to the table on how to solve things, because of having different techniques needed for his discipline.
Iterative estimation of math problems to get the needed significant digits instead of actually trying to solve it, that sort of thing. Helped all of us open our eyes for "non-CS" ways to solve stuff.
=Blue(23)
LITTLE GIRL: But which cookie will you eat FIRST? C. MONSTER: Me think you have misconception of cookie-eating process.
Wait a minute. I don't see any sssca compliant copy prevention code in any of these programs. This is a dangerous felony under the sssca or cbtpa! Someone please call the MPAA and stop this before someone figures out how to steal albums with this potentially dangerous source code that is not approved by the mpaa or Microsoft.
Oh ya, the gun that you own that can kill people is pefectly legal to own. However software not approved by the mpaa or the fcc or microsoft is bad!
What is the world coming to? Soon half the webpages out there will have the title 'New Page 1'..
Toil for Oil
/ooo*
/OOOOO\
Input: oil.in
Prospecting for new sources of oil has become a high-technology industry. With improved drilling technology it has become economically viable to seek out ever smaller and harder to reach deposits of oil. However, using exploratory drilling to locate these deposits is not cost-efficient, so researchers have developed methods to detect oil indirectly.
One such method to detect oil is sonar, which uses reflected sound waves to locate caves in underground rock formations. Determining how much oil can be contained in such a cave is a difficult problem.
gf +
/ \
y
+-------+
filter lameness *
-- --
junk ' -- ---
, -- --
. -=- +ooooooo+
; -- -- -=-O---
-- --- +
-- --
+ + ' +
*ooooooo--- ---o---
--OOOOOOOO+OOOOOOO+
junk ---OOOOOOOOOOO--
---OOOOO---
filter --O--
defeater +
In this problem, you will be given some cross-sections of underground caves, represented by polygons such as the ones shown in the figure. Some of the points bounding the polygon may be holes through which oil can seep out into the surrounding rock (represented by * in the figure). Given the polygonal shape of the cave and the positions of the holes, you must compute the maximum amount of oil that could be in the cave (shown as gray shaded areas in the figure). This amount is limited by the fact that, in any connected body of oil, the oil level can never be above a hole, since it would drain into the surrounding rock instead.
Input
The input contains several cave descriptions, each in the form of a polygon that specifies a cross-section of a cave.
The first line of each description contains a single integer n, representing the number of points on the polygon (3 <= n <= 100).
Each of the following n lines contains three integers x[i], y[i], h[i]. The values (x[i], y[i]) give the positions of the points on the boundary of the polygon in counterclockwise order. The polygon is simple--that is, it does not cross or touch itself. The value of h[i] is equal to 1 if the point is a hole through which oil can seep out, and 0 otherwise. The "upward" direction in each case is the positive y-axis.
The input is terminated by a zero on a line by itself.
Output
For each cave description, print its sequence number (starting with 1) followed by its oil capacity. Approximate the oil capacity by the area within the given cross-section that may contain oil, rounded to the nearest integer. Use the format in the example output given below.
Place a blank line after each test case.
Sample Input
4
10 0 0
5 10 1
0 20 0
-10 0 0
11
0 6 0
1 5 1
6 0 0
10 4 0
8 6 0
6 4 0
4 6 0
8 10 0
10 8 0
12 10 0
8 14 1
0
Output for the Sample Input
Cave 1: Oil capacity = 150
Cave 2: Oil capacity = 27
If anyone is interested in a programming contest for high school kids, check out USACO (USA Computing Olympiad). They have contests throughout the year (any country can participate) which lead up to the US Open (only US participates), a 5 hour, proctored contest which then determines eligibility to go to IOI (The Computer Science World Olympiad Training Camp) from which a few kids are chosen every year to represent the US in world competitions.
:-).
The contest style is very similar to the ACM (solve n problems in m hours) and often very interesting problems are given (just because it's high school, doesn't mean the kids are stupid
If anyone is a computer science geek in high school or a teacher of CS in a high school, you should definitely check it out.
When I was a sophomore(?) in high school around 1980, some friends and I entered a programming contest. I don't remember which one it was; it may even have been an ACM contest.
Anyway, we got a bunch of problems. I ended up taking the hardest one, which would probably take all the time allotted, while the others worked on cranking out the simpler one.
Here was the question: You have a salesman that must travel through a series of cities. Write a program to find the shortest route.
I had never heard of the Travelling Salesman problem before.
So I diligently tried to solve the problem. But for some strange reason, I kept running into cases that made it difficult to find the optimal, shortest route. I worked my ass off for the 2 or 3 hours that we had, and ended up running out time. I was sure there "had to be a solution", otherwise, why would they give us the problem?
It wasn't f***ing fair, and I'm still f***ing pissed about it to this day. :)
Sometimes it's best to just let stupid people be stupid.
See subject
They do not honor their claims. Complete scam.
Tux Racer is not free software, you fuck nut. It costs $29.99 (and a trip to the local jail if you try to share it).
Not bad, #27. But if you look at the SE US Regional Standings, we look even better! #1, #4 and #7 -- our undergrad teams regularly beat other SE US graduate teams. UCF has represented the SE US at the world finals for most of the competition's history, including they heaftier competition of more recent years.
UCF has never won #1, but they took #2 in 1987 and #4 in 1986 back in the Early Years. In the '90s, we've broken the top 10 at world only once or twice, but we've managed to place in the top 25 regularly.
-- Bryan "TheBS" Smith
Independent Author, Consultant and Trainer
I think it is a nice sign of equality throughout the world, what surprise should it be that the country with the most citizens won? If China can somehow get its act together it can be a major world influence, because of its massive and massively expandable population. Youve probably heard all the news of their space programme et al., besides american universities came 2nd (MIT)and 5th (Standford), chinese (Shanghai) 1st and 4th (Tsinghua), there really isnt that much difference if you look at the scoresheets. Besides just because the govvernment isnt exactly uh... yea... I'm just saying i wouldnt have president Bush (who still enforces the death penalty, (though not to the extent of the chinese, in general) be my leader.
0xC3
...even moderately offended by the lack of functional languages offered to the contestants?
(I'm (not (one) of those) rabid, foaming LISP advocates) that insists *everything* is better with functional languages... but... I do believe there is a time and place for just about every style of programming. Some of those questions looked very much like the "time and place" for a nice modern functional language like Haskell. Even Scheme would've been nice... Miranda, some flavour of ML... anything.
Perhaps there is some reasoning behind this that I'm missing. I guess I just thought it was sad that the ACM seems to be promoting the view that functional languages are too 'esoteric' even for use in a programming contest.
What about the solutions? What are the penalties in the list about?
Are the unsolved problems the same for every team?
Please post a reply. I don't want to dig a lot of stuff to find out the answers. I'm not in the mood...
So if someone cares (snif...) i would be very grateful, and maybe some other guys too. We could arrange a mass microdonation for the one that comes up with a cool post about the issue...
I feel so lonely...
and some moron is going to mod you as Funny, which is even worse.
Yes, I agree. Not just functional, either; lots of their problems would be exquisitely tackled by a logic programming language like prolog or twelf. It saddens me that ACM is not progressive enough to encorporate even "known good languages" into their allowed set (yet would easily fall to Yet Another Procedural Language with corporate backing like Java).
;)
There are lots of things that suck about the ACM contest, anyway. Personally, I think that the ICFP contest is much better, because:
- You can use any language, number of teammates, resources, etc.
- You get several days
- The problems are more interesting (sometimes unsolved)
- Work at home
(* Could you please warn us before handing us a PDF link. A large number of us dont have the ability to read them. *)
I do have a PDF reader, but it gave me funny error messages about a "bad CMAP", whatever the fudge that means.
However, rather than skanky math and combinatorial problems, why not give more **practical** problems, "write a PDF viewer in less than 2000 lines of code" (or a token quota or an EXE size quota, etc.)
Or give them more time and have them write OSS modules.
In may almost 1.5 decade of programming, the closest I have come in the real world to those kinds of problems is to write a license-plate typo matcher for a smog-check organization based on license plate and name/address, both of which may be mistyped. I had to look at the patterns of errors, for example, license "123ABC" may be mistyped "ABC123", etc.
However, even that is not representative of the majority of programming issues that I face on a day-to-day basis.
I suppose it is more cerebral than football games, but still lacks in the paycheck reality department IMO.
Table-ized A.I.
Almost all of it is about optimization problems. I see little place for real-world issues like abstraction, concurrency, standardization, business problems (i.e. unstructured complexity).
I am sure it is good fun, and is a good predictor of math intelligence, but I would not call it a programming contest.
Then again, Computer "Science" has all too frequently been treated and taught as a wierd form of math, when almost all uses of it are in engineering. This may be one reason for the embarassingly slow progress in the field.
The only good weather is bad weather.
I was in ACSL back in high school, this is the first time I've heard it mentioned on slashdot. Was it really small beans that not many other American slashdotters have done it?
It was pretty cool back in high school (for me, i graduated in '93) the school would fly us out to miami or houston or other places for the all-star competition at the end of the regular season.
The programs were usually doable, the test was tricky because most of the time it was following very closely syntactic and algorithmic details to determine the value of a variable when a loop exits, etc. The tests were mostly bookkeeping, though. It was really easy to miss a small detail, and get the question way wrong. There were a few, but not too many, computer-science type questions (such as figuring out how nested a particular recursion loop would be, which would take WAY too long to run through manually on paper), representations of Finite-State Automata, etc. But most of the normal questions just involved base 2, 8, 10, or 16 math and conversions, and/or running through algorithms on paper, keeping manual track of all flags and stuff.
make world, not war
He already said that he was a sophmore in HIGH SCHOOL...
Why don't they make the code publicly available? Along with the annotations of the Judges?
All things considered, UW isn't a bad school. I'm in my last year of undergrad there (Computer Science), and it does provide a very wide-reaching CS education, with ample possibility to explore specialized areas in your final year.
Unfortunately, the city ot Waterloo itself is a pretty drab place with not much to do, and the surrounding student ghettos are pretty unsightly. I can't think of any fourth-year students who aren't counting down the days before they graduate.
You can get it if you've got the marks? Well, yeah, duh. Isn't that how every university is/should be?
:P
I'm a student at the University of Waterloo, and we're not quite a 'state school'. We get funding from our government (which is a province, btw, not a state) and private industry, but all of the students have to pay tuition. Which, if you're a foreign student, costs $24 000 a year, instead of the $5 400 Canadian students pay (our government subsidizes half of the cost of tuition)
You might want to recheck your facts.
And tuition isn't deregulated in Ontario yet.
Silly.
Have you thought about what you're looking at today?
You don't mind if I shamelessly lift this phrase from you, do you? Thanks. :)
(* Re:"Pacheck Reality Department". mind if I shamelessly lift this phrase from you, do you? *)
:-) Go ahead.
Sure, but it will cost you $29.95 per usage. I got bills to pay you know.
...just kidding
Table-ized A.I.
it happened that I proposed (almost) the same problem at a seminar in Nov 2002, and then I solved it. My program does not find the shortest string; but it also understands if a code is 'uniquely infinitely decodable' that is if it can decode strings of infinite lenght in an unique way. It is based on a known technique, see [Cover Thomas], with some improvements. This program also shows that the problem is polynomial complexity in n,k where n=number of words k=maximum of letters in a word.
Strange how 42 is the answer to every problem...
Never pet a burning dog.
Did anybody else conjure up images of batch processed punch card runs when reading over some of these problems? I don't know if it's the IBM backing of the event or what, but I got images of geeks sitting at punch card writers feeding an old Model 704 numerical representations of oil-filled polygons in card form and waiting for it to spit out an answer. The questions are interesting enough, and I'm even taking a crack at a few on my own time, but I can't shake the images!
Am I going insane?
"These people look deep within my soul and assign me a number based on the order in which I joined" --Homer re:
Good job UCF!
I was in the programming team a few years back and we finished 6th in regionals. I think all of our teams finished top 10 that year. I was the only grad student in the team, but it was a nice learning experience.
I hope these achievements show up in the university rankings. Way to go Dr.Orooji!!
congrats to Shanghai Jiao Tong University and all the other people that took place.
hmm sooner