April 12, 2013 at 00:11Olympiad programming tasks: what kind of beast?
Recently, we announced a competition of tasks in sports programming . The contest organizers asked to write a short announcement about the contest on the ABBYY blog, but the strict editor refused to print the announcement without explaining what the olympiad problem is. From this a whole article was born. Let's start with an example of an olympiad problem.The same example so as not to follow the link
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output
In the city of N. it is very bad with roads, catering and IT infrastructure. There are n intersections in the city, some of which are connected by two-way roads. The road network consists of n - 1 roads; roads can be reached from any intersection to any other. Yes, you are right - the road network forms an undirected tree.
Recently, the mayor of the city came up with a way to eliminate problems with catering and IT infrastructure, and at the same time! It was decided to put at the crossroads of the city restaurants of two well-known cafe networks for IT-employees: “iMac D0naldz” and “Burger Bing”. Since the owners of the networks are not friends, it is strictly forbidden to place restaurants of two different networks at neighboring intersections. There are other requirements. Here is the complete list:
The mayor is going to take a good tax on each restaurant, so he is interested in the maximum number of restaurants.
Help the mayor analyze the situation. Find all such pairs (a, b) that a restaurants may belong to iMac D0naldz, b to Burger Bing, and the sum a + b is maximum.
The first line of the input contains an integer n (3 ≤ n ≤ 5000) - the number of intersections in the city. Next, in n - 1 line, all roads are listed, one road per line. Each road is given by a pair of numbers x i , y i (1 ≤ x i , y i ≤ n) - the numbers of the connected intersections. Consider the intersections numbered from 1 to n.
It is guaranteed that a given road network is an unoriented tree with n vertices.
In the first line print an integer z - the number of pairs to find. Next, print all the required pairs (a, b) in increasing order of the first component a.
IT restaurants
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output
In the city of N. it is very bad with roads, catering and IT infrastructure. There are n intersections in the city, some of which are connected by two-way roads. The road network consists of n - 1 roads; roads can be reached from any intersection to any other. Yes, you are right - the road network forms an undirected tree.
Recently, the mayor of the city came up with a way to eliminate problems with catering and IT infrastructure, and at the same time! It was decided to put at the crossroads of the city restaurants of two well-known cafe networks for IT-employees: “iMac D0naldz” and “Burger Bing”. Since the owners of the networks are not friends, it is strictly forbidden to place restaurants of two different networks at neighboring intersections. There are other requirements. Here is the complete list:
- at each intersection there should be no more than one restaurant;
- each restaurant is owned by either iMac D0naldz or Burger Bing;
- each network must build at least one restaurant;
- there are no pairs of intersections that are connected by a road and on which there are restaurants of different networks.
The mayor is going to take a good tax on each restaurant, so he is interested in the maximum number of restaurants.
Help the mayor analyze the situation. Find all such pairs (a, b) that a restaurants may belong to iMac D0naldz, b to Burger Bing, and the sum a + b is maximum.
Input data
The first line of the input contains an integer n (3 ≤ n ≤ 5000) - the number of intersections in the city. Next, in n - 1 line, all roads are listed, one road per line. Each road is given by a pair of numbers x i , y i (1 ≤ x i , y i ≤ n) - the numbers of the connected intersections. Consider the intersections numbered from 1 to n.
It is guaranteed that a given road network is an unoriented tree with n vertices.
Output
In the first line print an integer z - the number of pairs to find. Next, print all the required pairs (a, b) in increasing order of the first component a.
Test examples
Input
5
1 2
2 3
3 4
4 5
Output
3
1 3
2 2
3 1
Input
10
1 2
2 3
3 4
5 6
6 7
7 4
8 9
9 10
10 4
Output
6
1 8
2 7
3 6
6 3
7 2
8 1
5
1 2
2 3
3 4
4 5
Output
3
1 3
2 2
3 1
Input
10
1 2
2 3
3 4
5 6
6 7
7 4
8 9
9 10
10 4
Output
6
1 8
2 7
3 6
6 3
7 2
8 1
The first thing that catches your eye is an unusual condition. This approach has developed historically: writing a short mathematical formulation is not accepted. Usually they try to connect it with real life, well, or with a not very real one . For example, in USACO, the heroes of all tasks are the farmer John and the cows. Before proceeding with the solution after reading the conditions, the participant needs to highlight the mathematical formulation of the problem.
The solution to the olympiad problem is a program written in one of the programming languages. The most popular languages are: C ++, C #, Java, Pascal. You might say that Pascal has long been deprecated. However, do not underestimate it! Experienced sports programmers are able to write standard algorithms in Pascal, which are already in C ++, faster than an ordinary person will read the condition of the task :) By the way, because participants choose a programming language on their own, there is a risk that they make suboptimal choices . Firstly, solutions do not exist in all languages, and secondly, solutions written in some languages may work less efficiently than in others.
Back to the discussion of the conditions. Olympiad tasks are very formalized :
- strict input / output format, sometimes even accurate to spaces and line feeds;
- conditions, as a rule, have a strict unambiguous interpretation. That's where customers can learn to write TK!
- strict limits on runtime and used memory. In real development, they’ll probably tell you something in the style of “ we want it to work on such and such hardware and on such and such OS ” or “ listen, your program eats too much memory ”. Much less often you can hear phrases such as “ your program should work no more than 1.5 seconds ” or “ don't you dare use more than 64 megabytes of memory ”;
- all initial values are strictly limited.
Such a strict formalization is justified. All decisions of the competition participants are checked on a certain set of tests, which is prepared by the jury of the Olympiad and is usually not known to the participants in advance. The next feature is task analysis. The author of the olympiad problem thinks about how many percent of the participants will solve such a problem, for how long (up to minutes), to what topic this problem belongs (for example, a graph task or a greedy algorithm task).
In general, there are two types of Olympiad problems: “ classical ” and “ heuristic ”". Classical problems require an exact, strictly proved solution. When solving heuristic problems, participants compete among themselves who can get the best answers. For example, whose solution correctly recognizes more characters. Heuristic tasks usually do not have exact solutions. Here they are most close to real development. For example, character recognition is quite a “heuristic” task.
There are many ways to evaluate solutions for "classic" tasks:
- the task is considered solved if the participant’s solution worked correctly on all tests. Such a rating system is used in ACM competitions.
- points are awarded for the decision, which depend on the number of tests successfully passed by the program. This approach is often used at school olympiads: no one will leave resentful from the competition and get at least 0.5 points.
- tests are combined into groups, for each of which a certain number of points is awarded. It should be noted that points for the group are awarded only if the solution worked correctly on all tests from the group. This is a reasonable compromise between justice and participants' satisfaction. ABBYY Cup professes such a form of evaluation of decisions;
- sometimes the number of points received by the participant depends on the time that was spent on solving the problem. For example, such a system is used on Codeforces and Topcoder.
Evaluation of solutions to "heuristic" problems in each case is developed individually. In the heuristic task that the ABBYY Cup 2.0 finalists were asked to solve, it was necessary to develop a program for classifying documents by subject. The solution was tested on a group of tests, each of which contained a certain set of texts on different topics. There were three subjects in total, and each of them was presented in each group in a different amount. The one whose solution passed the largest number of test groups won. When installing a “heuristic” task on a testing platform, you sometimes have to modify it, since most testing platforms are “tailored” to evaluate classic tasks.
Of course, one can talk endlessly about the peculiarities of olympiad problems. We highlighted only the most important points. If you have questions or comments, welcome to comments. And if you know how and love to compose the tasks described in the article, we can talk about it here .
Vladimir Minyailov, NLC Technology Department,
Ruzana Miniakhmetova, a group of educational projects.