Results of the Russian Code Cup 2014 and analysis of tasks
On October 4, the final round of the Russian Code Cup, the largest annual sports programming competition in Russia, was held. The winner of the Russian Code Cup 2014 and the owner of the main prize - $ 10,000 - was Gennady Korotkevich. The second place was taken by Peter Mitrichev - he received $ 5000. Egor Kulikov finished third, his cash prize was $ 3000. Also this year, for the first time, all participants included in the top ten were awarded: owners of 4-10 places received $ 1,000 each.
The final was held in a new online format for the championship. Unlike the offline final of last year, the participants now did not have to come to Moscow, and the finalists solved all the proposed problems online, in a comfortable atmosphere for them. Fifty finalists who overcame their qualifications and qualifying round fought for the title of the best programmer. 23 people from the finalists of this year participated in the final of the 2013 RCC.
Interesting Facts Finals
The simplest task is A, it was decided by 45 finalists. The most difficult - F, for it was not a single attempt. If we consider only solved problems, then E was the most difficult, only 3 finalists decided it, and Yevgeny Kapun did it first. And Alexey Shlyunkin solved only this task.The finalists used to solve problems only 2 programming languages!
C ++ - 254 decisions, 91 of them made
Java - 52 decisions, 24 of them are made.
')
The first correct decision - Peter Mitrichev at 23 minutes, this is the most difficult final for this indicator.
The winner - Gennady Korotkevich - passed the fifth task in 1 minute 51 seconds before the end of the contest and came out on top. Having passed the fifth task, Peter Mitrichev, Egor Kulikov or Dmitry Dzhulgakov could have outstripped him.
Jacob Dlugach passed 3 tasks in the last hour, two in the last 16 minutes and burst into the top ten at the 7th place.
Analysis of tasks
Task A. A gameThe task
Time limit: 2 seconds
Memory limit: 256 megabytes
King Bytelandia holds an annual intellectual game. According to the rules of the game, all participants are divided into two teams, and a set of hints is communicated to each of the players. During the game, participants can exchange tips by the following rules: Each player of the first team can approach one player of the second and ask him for a hint, which he does not yet know. If there are several such tips, a member of the second team will tell him any of his choice. Each member of the first team can ask a hint only for one player of the second team, while several players can contact the player of the second team. The first team wins if it manages to collect all the clues. Help her captain find out whether his team will be able to collect all the clues, regardless of the answers of the second team.
Input format. The first line of the input file contains three integers n, m (1 ≤ n , m ≤ 500) and k (1 ≤ k ≤ 5000) - the sizes of the commands and the number of hints, respectively. The following n + m lines contain information about prompts available to players at the beginning of the game in the following format. The first number in the line corresponds to the number of prompts for the player, and the following numbers contain the numbers of the prompts - natural numbers not exceeding k .
The format of the output. If the first team can collect all the hints, output 1. In the first line of the output file n numbers, for each member of the first team, specify which of the players of the second team to ask for a hint. If there are several answers, output any. If the first team cannot collect all the hints in the first and only line, output 2.
Memory limit: 256 megabytes
King Bytelandia holds an annual intellectual game. According to the rules of the game, all participants are divided into two teams, and a set of hints is communicated to each of the players. During the game, participants can exchange tips by the following rules: Each player of the first team can approach one player of the second and ask him for a hint, which he does not yet know. If there are several such tips, a member of the second team will tell him any of his choice. Each member of the first team can ask a hint only for one player of the second team, while several players can contact the player of the second team. The first team wins if it manages to collect all the clues. Help her captain find out whether his team will be able to collect all the clues, regardless of the answers of the second team.
Input format. The first line of the input file contains three integers n, m (1 ≤ n , m ≤ 500) and k (1 ≤ k ≤ 5000) - the sizes of the commands and the number of hints, respectively. The following n + m lines contain information about prompts available to players at the beginning of the game in the following format. The first number in the line corresponds to the number of prompts for the player, and the following numbers contain the numbers of the prompts - natural numbers not exceeding k .
The format of the output. If the first team can collect all the hints, output 1. In the first line of the output file n numbers, for each member of the first team, specify which of the players of the second team to ask for a hint. If there are several answers, output any. If the first team cannot collect all the hints in the first and only line, output 2.
Idea: Anna Malova
Realization: Anna Malova
Analysis: Anna Malova
Consider the bichromatic graph - the first team, the second team. It is written on the edge, what prompts the participant of the second team owns, which the participant of the first team does not yet know, that is, the difference between the sets of participants' prompts. We leave only those edges on which one number is written. Among such edges we leave only those on which only one number is written.
Using the constructed graph, we will make another bipartite graph: the vertices of the first beat are the participants of the first team, the tops of the second beat are those tips that are still unknown to the first team. There is an edge between two vertices, if there was an edge in the previous bichrophic graph, coming from the same vertex on which this information was recorded. If the resulting match contains the maximum matching, then the first team can win. Otherwise, the first team cannot win.
To meet the specified time limits, to find the difference of sets you need to use a bitset. In addition, before launching Kuhn’s algorithm to search for the maximum matching, you need to compare the sizes of the shares, if the size of the share with the prompts exceeds the size of the share of participants, then the answer 2 is immediately given.
Video:
Task B. Painting the building
The task
Time limit: 2 seconds
Memory limit: 256 megabytes
In one company, they decided to repaint the gray wall of their office with a length of n meters in corporate colors: blue and orange. To do this, they bought an innovative robot painter.
The robot can paint the walls in accordance with the program recorded in it. The program is a sequence of commands. Each command is given in two integers and a color and tells the robot what segment of the wall c is in which color to paint. For example, a wall with a BBOOO coloring plan can be obtained using a program consisting of two teams: paint in blue from first meter to fifth, and then in orange from third to fifth.
One of the programmers of the company was instructed to write a program that, having executed it, the robot would paint the walls in accordance with the given scheme. He easily coped with the task and even wrote a program containing the minimum possible number of commands. After that, he asked himself: how many programs exist of the same length that will paint the wall according to the coloring plan?
Input format. The first line contains the number T - the number of tests. The following are descriptions of T tests.
In the only line of the test, a line is given consisting of the letters B and O , where the letter in the i -th position is responsible for whether the i-meter of the wall is to be painted in blue or orange.
The total length of the lines does not exceed 500,000.
The format of the output. For each of the T test cases, print a single number — the number of programs of programs of minimal length leading to painting the fence accordingly. Since the answer can be large, output the answer modulo 10 9 + 7.
Memory limit: 256 megabytes
In one company, they decided to repaint the gray wall of their office with a length of n meters in corporate colors: blue and orange. To do this, they bought an innovative robot painter.
The robot can paint the walls in accordance with the program recorded in it. The program is a sequence of commands. Each command is given in two integers and a color and tells the robot what segment of the wall c is in which color to paint. For example, a wall with a BBOOO coloring plan can be obtained using a program consisting of two teams: paint in blue from first meter to fifth, and then in orange from third to fifth.
One of the programmers of the company was instructed to write a program that, having executed it, the robot would paint the walls in accordance with the given scheme. He easily coped with the task and even wrote a program containing the minimum possible number of commands. After that, he asked himself: how many programs exist of the same length that will paint the wall according to the coloring plan?
Input format. The first line contains the number T - the number of tests. The following are descriptions of T tests.
In the only line of the test, a line is given consisting of the letters B and O , where the letter in the i -th position is responsible for whether the i-meter of the wall is to be painted in blue or orange.
The total length of the lines does not exceed 500,000.
The format of the output. For each of the T test cases, print a single number — the number of programs of programs of minimal length leading to painting the fence accordingly. Since the answer can be large, output the answer modulo 10 9 + 7.
Idea: Vitaly Aksyonov
Realization: Nikolay Vedernikov
Analysis: Nikolay Vedernikov
The task required to paint the strip in two colors. We are able to paint any subdivision in some color. It was necessary to count the number of ways to paint a strip in the minimum number of colors.
In this problem there are two cases: the ends of the strips are painted in one color or different. Consider the first case.
The ends are painted in one color, which means that the total segments are 2 k + 1. Let us show how many minimum colors are necessary. Consider the final coloring of the strip, if the last segment we painted a segment in the middle, then the total number of segments increased by two (we broke a segment into two and added a new one). In this way, we can extract k segments, and in the end remain 1. Total, we spent k + 1 moves. If at some point we took a segment not from the middle, but from the edge, we will spend more moves than necessary.
Now count the number of ways. Consider the final coloring and the last move we painted a segment in the middle, then the number of ways to choose this segment is equal to the total number of segments minus extreme, total 2 k - 1. Thus, we reduced the task to a smaller task. Continuing in this way, we get the final answer (2 k - 1) · (2 k - 3) · ... · 3 · 1, which is equal to (2 k - 1) !! ..
Consider the case in which the ends are painted in different colors, then the entire segment 2 k . Consider the final strip colorings. Suppose that at the beginning we extracted segments from the middle l , and then extracted a segment with an edge. Then we spent l + 1 and we had 2 k -2 l -1 segments, and the ends turned out to be the same color. According to previous arguments, we can not color it faster than k - l . Total: k +1 moves. In addition, from this follow the fact that we paint the first move, a segment from one of the ends.
Now count the number of ways. Let's call the first segment black. Let the first move we painted a segment from the left edge. We will sort out how far he will paint, and everything that is to his right will have to be painted white, according to our reasoning. Note that now we have two previous tasks, in which the ends are painted in one color. Let in the left segment l black segments, then the answer on this segment will be ((2 l - 1) - 2) !!, and on the right ((2 k - (2 l - 1)) - 2) !! .. Except In addition, we can paint segments from the left half and from the right in any order. That is, the product of the segments must also be multiplied by choose ( l - 1, k ), since we have already painted one segment, it means that we need to do more k colors, and on the left we have to make l - 1 colors. In addition, the first segment, we could paint on, because we still paint on top of the right segment. And such options are equal to the length of the right side. So for a fixed number l the answer will be (( l - 3) !!) · ((2 k - 2 l -1) !!) · choose ( l - 1, k ) · (suff_lenl). Thus, let's iterate l and sum it up. Similarly, we count for the other end.
If we interpret factorials and inverse factorials by module, then for one l we will be able to answer for O (1). The total running time is O ( n ).
Video:
Task C. Backpack problem
The task
Time limit: 2 seconds
Memory limit: 256 megabytes
As a homework in computer science, Petya and Vasya were asked to write a program that would solve a backpack problem. The task is formulated as follows: given N things with weights a i , is it possible to choose a subset of things with a total weight equal to exactly W ?
Petya and Vasya successfully coped with the task, having received Accepted in the testing system. But when discussing the problem, it turned out that Petya and Vasya used different approaches to the solution.
It turned out that Vasya actually counted the number of ways to select a subset of things weighing W , and when printing the answer he compared this number with zero. To simplify the implementation, Vasya did not count the number of methods, but his remainder from dividing by some number m . Petya immediately declared that Vasya’s decision was wrong, but he could not come up with a test, on which it gives the wrong answer. Can you find such a test?
For a given m, create a test for a backpack problem in which the number of ways to gain weight W is divided by m without remainder.
Input format. The only line of the input file contains an integer m (1 ≤ m ≤ 10 18 ) - the module for which calculations were made in the Vasya program.
The format of the output. If there is no such test, output a single number -1. Otherwise, in the first line print two integers N and W separated with a space (1 ≤ N ≤ 200, 1 ≤ W ≤ 500). In the next line print N integers a i (1 ≤ a i ≤ W ).
Memory limit: 256 megabytes
As a homework in computer science, Petya and Vasya were asked to write a program that would solve a backpack problem. The task is formulated as follows: given N things with weights a i , is it possible to choose a subset of things with a total weight equal to exactly W ?
Petya and Vasya successfully coped with the task, having received Accepted in the testing system. But when discussing the problem, it turned out that Petya and Vasya used different approaches to the solution.
It turned out that Vasya actually counted the number of ways to select a subset of things weighing W , and when printing the answer he compared this number with zero. To simplify the implementation, Vasya did not count the number of methods, but his remainder from dividing by some number m . Petya immediately declared that Vasya’s decision was wrong, but he could not come up with a test, on which it gives the wrong answer. Can you find such a test?
For a given m, create a test for a backpack problem in which the number of ways to gain weight W is divided by m without remainder.
Input format. The only line of the input file contains an integer m (1 ≤ m ≤ 10 18 ) - the module for which calculations were made in the Vasya program.
The format of the output. If there is no such test, output a single number -1. Otherwise, in the first line print two integers N and W separated with a space (1 ≤ N ≤ 200, 1 ≤ W ≤ 500). In the next line print N integers a i (1 ≤ a i ≤ W ).
Idea: Boris Minaev
Realization: Artem Vasilyev
Analysis: Artem Vasilyev
In this problem, you need to find such a test for a backpack problem, that the number of ways to gain weight W is divided by the number M.
Further we will consider W equal to 500. The main construction of the author's solution is based on generating such a set of n things of small weight so that their sum is less than W / 2 . Calculate for this set the number of ways to type a subset of things with a total weight k for all k from 0 to W / 2 and denote this number by ck . We require that for our dialing any number from 1 to 10 18 be represented as a sum of not more than 200 - n ck numbers.
Suppose that there is such a set of things that for each x there is k such that ck = 2 x, then such a property would be obvious: for each x , if the binary record M contains a unit at position x , we add a thing with weight W - x in our set. Since the sum of things added before this step was less than W / 2 , it is easy to see that the number of ways to get weight W is equal to M. Note that this process can be described by the following greedy algorithm: while M is greater than zero, we find the maximum ck ≤ M , add a thing with weight W - k and subtract the number ck from M.
Unfortunately, it’s difficult to get such a set of things, so you need to come up with some other set of things that has the property that the above greedy algorithm finds a solution for any M. To do this, take a set of things with a random low weight and the amount is less than W / 2 . You can check and make sure that if we choose our set in this way and count the numbers ck for it, the greedy algorithm will most likely return the correct partitioning of any number M into the terms ck . Thus, it is possible to construct a set of things that satisfies this property, and using the greedy algorithm, add things in such a way that the number of ways to collect W becomes equal to 0 modulo M.
Video:
Task D. Networking
The task
Time limit: 2 seconds
Memory limit: 256 megabytes
In one progressive country, the development of information technologies is in full swing! High speeds were laid to be used for data transmission. For ease of control over data flows and cost savings on laying, highways were laid out in such a way that data can reach from any city to any other in a unique way.
However, it is not enough to lay the wires; you also need to develop routing algorithms. During the discussions, the following data routing model was used: k cities are announced as key points and each of them is renamed “Servergrad- i ”. After that, each city gets a network address. The network address of the city v will be an array of k elements, in which the i- th element is equal to the number of cities through which traffic must pass in order to get from city v to Servergrad- i .
To avoid problems with routing, each city must have a unique address. Also, the government wants Servergrads to be as small as possible. Help the government decide which cities to use as Servergrades.
Input format. The first line contains the number n (2 ≤ n ≤ 100 000) - the number of cities in the country. Further, in n - 1 line there are pairs of cities between which the highway is laid.
The format of the output. Print the number k - the minimum number of Servergrads, which is enough to ensure the correct routing of all cities. Next, output k different integers from 1 to n, where the i -th number is responsible for which city will be chosen as Servergrad- i- th.
Memory limit: 256 megabytes
In one progressive country, the development of information technologies is in full swing! High speeds were laid to be used for data transmission. For ease of control over data flows and cost savings on laying, highways were laid out in such a way that data can reach from any city to any other in a unique way.
However, it is not enough to lay the wires; you also need to develop routing algorithms. During the discussions, the following data routing model was used: k cities are announced as key points and each of them is renamed “Servergrad- i ”. After that, each city gets a network address. The network address of the city v will be an array of k elements, in which the i- th element is equal to the number of cities through which traffic must pass in order to get from city v to Servergrad- i .
To avoid problems with routing, each city must have a unique address. Also, the government wants Servergrads to be as small as possible. Help the government decide which cities to use as Servergrades.
Input format. The first line contains the number n (2 ≤ n ≤ 100 000) - the number of cities in the country. Further, in n - 1 line there are pairs of cities between which the highway is laid.
The format of the output. Print the number k - the minimum number of Servergrads, which is enough to ensure the correct routing of all cities. Next, output k different integers from 1 to n, where the i -th number is responsible for which city will be chosen as Servergrad- i- th.
Idea: Boris Minaev
Realization: Andrey Komarov
Analysis: Andrey Komarov
In the problem, a tree was given and it was necessary to mark the minimum possible number of vertices so that the distance vectors from each vertex to the selected ones were different.
Consider separately the case when a given tree is a chain : the vertices can be ordered in such a way that the first is associated only with the second, the last with only the last but one, and the rest with only two neighbors. If a tree is a chain, then, obviously, as an answer, you can take one of the ends of this chain: all vertices will be removed from it at different distances.
Otherwise, there is a peak of a degree greater than two in the tree. Suspend a tree for this top. We calculate the following dynamics for each subtree: the minimum number of labels that must be placed in this subtree so that the distance vectors for each pair of vertices of this subtree are different, provided that somewhere above the root of the subtree there is at least one marked vertex. We call the value of this dynamics min ↑. Note that this is not exactly what needs to be calculated in the task, but this will coincide with the task if you remove the restriction on the existence above the root of the labeled vertex. We call this dynamics min . Note that min ↑ ≤ min . So, if we can produce an answer of exactly min ↑ in size, this will be the answer to the problem. We solve the problem in two stages - first we calculate the values ​​of min , and then we get an answer of this size.
Suppose we want to calculate min ↑ for some vertex v . We calculate these values ​​for its subtrees. We got that in some of them there is at least one tag, and in the other tags there is no. Let the number of subtrees in which there are no labels be equal to k . Then, in response to v, you need to add at least k - 1 labeled vertices (one for each unmarked subtree, except for one). Suppose we have added less. Then there are at least two unlabeled subtrees. Then the roots of these subtrees will be indistinguishable: there are no marked vertices in their subtrees, and all other distances are the same. Now we will show that these additions are enough. Consider any two vertices from different subtrees. They can be either at the same or at different depths. Let them at different depths. Then the distances from them to the intended labeled vertex above the root are different (the lengths of the paths to the root are different). Let them at the same depth. Then, by construction, at least in one of the subtrees in which these vertices lie, there is a labeled vertex. Then the distances to it from these two selected vertices will be different: from the one from whose subtree the marked vertex is selected, the distance will be less.
We now construct a min answer. The root we have chosen has at least three children. Hence, by the construction of min ↑, at least in two subtrees of the root there is a labeled vertex. Therefore, for each subtree there is a labeled vertex outside this subtree. Take it as the required min ↑ of the labeled vertex above. Then the answer will be the union of the min ↑ answers for all children of the root.
All considered operations can be done with one detour in depth. Hence, the total running time is O ( n ).
Video:
Task E. Boolean tree
The task
Time limit: 2 seconds
Memory limit: 256 megabytes
Acne very long thought how to solve a simple little problem, and in the process of coming up with a solution I drew a graph on the board. This graph, by coincidence, turned out to be a root tree. At this moment Borya came up to the blackboard, and began to write expressions in some vertices of the tree, in which different values ​​were assigned to Boolean variables.
After that, they introduced a rule according to which for each vertex of the tree, you can determine the value of the variable in this vertex. Namely, if the assignment of this variable to a value was recorded at this vertex, then the last such value is used. If thus the value could not be determined, then the value of this variable is taken in the nearest ancestor of this vertex, in which the assignment of the value of this variable is recorded. If the vertex has no such ancestor, then the value is undefined.
After several operations, they wanted to calculate for a given variable in how many leaves of the tree the value of this variable is true, in how many false, and in how many is not defined. And then they realized that it was difficult, and that they could not do it. Therefore, they ask you to help them, and after each addition of the entry on assigning a value to a variable, determine for how many leaves the value of this variable is true, for how many false, and for how many is not defined.
Input format. The first line contains the number T - the number of tests. The following is a description of T tests.
The first line of the test gives two natural numbers n and m (1 ≤ n , m ≤ 10 5 ), where n is the number of vertices of a given tree, and m is the number of additions of new entries about assigning a value to a variable. The second line contains n numbers, where the i -th number is the ancestor number of the i -th vertex. For the root, this number is zero. It is guaranteed that you are given exactly the tree. Next come m lines - record descriptions. Each of these lines contains three numbers: v is the number of the vertex, x is the number of the variable, and b is zero or one if the value of the variable is false or true, respectively. The variable number is a positive integer not exceeding 10 5 .
In each set of input data, the sum of all n and the sum of all m does not exceed 10 5 .
The format of the output. For each of the test examples, output m lines containing three numbers — the number of leaves of the tree for which the value of the variable just written is true, false, and not defined, respectively.
Memory limit: 256 megabytes
Acne very long thought how to solve a simple little problem, and in the process of coming up with a solution I drew a graph on the board. This graph, by coincidence, turned out to be a root tree. At this moment Borya came up to the blackboard, and began to write expressions in some vertices of the tree, in which different values ​​were assigned to Boolean variables.
After that, they introduced a rule according to which for each vertex of the tree, you can determine the value of the variable in this vertex. Namely, if the assignment of this variable to a value was recorded at this vertex, then the last such value is used. If thus the value could not be determined, then the value of this variable is taken in the nearest ancestor of this vertex, in which the assignment of the value of this variable is recorded. If the vertex has no such ancestor, then the value is undefined.
After several operations, they wanted to calculate for a given variable in how many leaves of the tree the value of this variable is true, in how many false, and in how many is not defined. And then they realized that it was difficult, and that they could not do it. Therefore, they ask you to help them, and after each addition of the entry on assigning a value to a variable, determine for how many leaves the value of this variable is true, for how many false, and for how many is not defined.
Input format. The first line contains the number T - the number of tests. The following is a description of T tests.
The first line of the test gives two natural numbers n and m (1 ≤ n , m ≤ 10 5 ), where n is the number of vertices of a given tree, and m is the number of additions of new entries about assigning a value to a variable. The second line contains n numbers, where the i -th number is the ancestor number of the i -th vertex. For the root, this number is zero. It is guaranteed that you are given exactly the tree. Next come m lines - record descriptions. Each of these lines contains three numbers: v is the number of the vertex, x is the number of the variable, and b is zero or one if the value of the variable is false or true, respectively. The variable number is a positive integer not exceeding 10 5 .
In each set of input data, the sum of all n and the sum of all m does not exceed 10 5 .
The format of the output. For each of the test examples, output m lines containing three numbers — the number of leaves of the tree for which the value of the variable just written is true, false, and not defined, respectively.
Idea: Boris Minaev
Implementation: Demid Kucherenko
Analysis: Vitalik Aksenov
To begin with, we will reduce our task to the one variable problem. Let's create a tree for each variable, in which the initial tree will contain the root of the original tree and a link to it. The link in the tree will always point to the top, in whose subtree we are now. Let's go around our tree bypassing in depth. If we go to the top in which some variable is set, then we create a new child at the top in the corresponding tree and rearrange the link to it. If we exit the vertex, then we rearrange the link in its corresponding tree to its ancestor. We squeezed the trees. It is necessary to remember to keep in each vertex the number of leaves in its subtree.
We will now solve the problem on the tree for one variable. We will process all requests for this variable sequentially. We need to be able to do two things:
- how many leaves only this vertex affects;
- find the closest ancestor, in which some value is set for this variable.
If we implement this, processing the request is not very difficult:
- find the number of leaves affected by this vertex - x ;
- we find the closest ancestor, in which some value is set for this variable - p ;
- if in p the same value as at our vertex, then the number does not change;
- if p is a different value than at our vertex, then the number changes to x ;
- if p does not exist, the number changes to x * then the number of “unknown” leaves decreases by x ;
- p must reduce the number of leaves affected by x
To implement queries, you need to expand the tree into a segment tree, where you can make a query on a subtree. Then requests of the first kind are very easy to handle using the sum in the subtree. To find the correct ancestor, we will do the following: when we make a request to a vertex, we add one to all the vertices in the subtree, that is, we say that they are covered by another vertex. Then, in order to find the ancestor, we will look for the binary rise of the first position, in which the value differs by one - it will be the desired ancestor.
Total running time: O ( mlog 2 n ), where n is the size of the tree, m is the number of requests.
Video:
Task F. Robot
The task
Time limit: 8 seconds
Memory limit: 256 megabytes
A robot travels through a rectangular cell field consisting of n columns and m rows. He can begin his journey in any cell of the first row. Then he can make some (possibly zero) number of moves. Let the robot stand in the column x and row y , then in one move it can go either into the cell ( x + 1, y + 1) or into the cell ( x - 1, y + 1). Of course, the robot can not go beyond the field.
The journey of the robot is complicated by the fact that there are rectangular obstacles on the field, the sides of which are parallel to the sides of the field. The robot can not go into the cage, which is covered by an obstacle. No two obstacles intersect, but they can touch.
You need to count the number of cells that can get a robot.
Input format. The first line contains the number T - the number of tests. The following is a description of T tests.
The first line of the test contains two integers n and m (1 ≤ n , m ≤ 10 9 ) - the number of columns and rows per field. The next line contains one integer k (1 ≤ k ≤ 10 5 ) - the number of barriers on the field. The following k lines contain a description of the obstacles. Each such line consists of four integers x 1 , y 1 , x 2 , y 2 , denoting the coordinates of the opposite obstacle angles (1 ≤ x 1 ≤ x 2 ≤ n, 2 ≤ y 1 ≤ y 2 ≤ m ). It is guaranteed that the obstacles do not intersect.
The total number of obstacles in the input file does not exceed 10 5 .
The format of the output. For each of the T test examples, print one number - the number of cells that the robot can visit.
Memory limit: 256 megabytes
A robot travels through a rectangular cell field consisting of n columns and m rows. He can begin his journey in any cell of the first row. Then he can make some (possibly zero) number of moves. Let the robot stand in the column x and row y , then in one move it can go either into the cell ( x + 1, y + 1) or into the cell ( x - 1, y + 1). Of course, the robot can not go beyond the field.
The journey of the robot is complicated by the fact that there are rectangular obstacles on the field, the sides of which are parallel to the sides of the field. The robot can not go into the cage, which is covered by an obstacle. No two obstacles intersect, but they can touch.
You need to count the number of cells that can get a robot.
Input format. The first line contains the number T - the number of tests. The following is a description of T tests.
The first line of the test contains two integers n and m (1 ≤ n , m ≤ 10 9 ) - the number of columns and rows per field. The next line contains one integer k (1 ≤ k ≤ 10 5 ) - the number of barriers on the field. The following k lines contain a description of the obstacles. Each such line consists of four integers x 1 , y 1 , x 2 , y 2 , denoting the coordinates of the opposite obstacle angles (1 ≤ x 1 ≤ x 2 ≤ n, 2 ≤ y 1 ≤ y 2 ≤ m ). It is guaranteed that the obstacles do not intersect.
The total number of obstacles in the input file does not exceed 10 5 .
The format of the output. For each of the T test examples, print one number - the number of cells that the robot can visit.
Idea: Boris Minaev
Realization: Boris Minaev
Analysis: Boris Minaev
In the task it was necessary to count the number of cells that are reachable from the first line of the field. The main difficulty lies in the fact that the size of each side of the field can reach 10 9 cells.
Firstly, due to the fact that the robot performs moves diagonally, it is convenient to separately consider cells of different parity. The robot can reach all the cells of the first line of the field. We will increase y and recalculate reachable cells. It is most convenient to store a set of reachable cells for a string in the form of a union of disjoint segments. Then you can easily recalculate the set when moving to the next line. Namely, one cell will be added to each segment on each side. Some segments may merge into one, and some will intersect with field boundaries or barriers.
Learn to effectively change this set of segments. It is best to store it in a data structure that allows you to find a segment that crosses a given coordinate in O (log n ). Additionally, for each segment we will keep information on whether the segment can increase to the left and to the right. Let's carefully consider all the events that can occur:
- Two segments joined together. This is the easiest case. You just need to combine them in the data structure.
- The segment has expanded to such an extent that it crossed with the edge of the field or an obstacle. Then you need to put a mark in the description of the segment that it can no longer grow in some direction.
- The barrier has begun. It is necessary to consider all segments that intersect with the barrier. Some of them need to be completely removed, some trimmed, and some divided into two parts. It is also necessary to create events that will occur when neighboring segments grow so large that they cross the current barrier.
- The barrier is over. It is necessary to find two adjacent segments and mark them that they can grow in the direction of the rectangle. You also need to add an event that should occur between neighbors. For example, if two neighbors are segments, then they may merge at some point. If one of them is a segment, and the other is an obstacle, then they may intersect. In other cases, do not add anything.
Also note that all segments need to be stored lazily. That is, changing their size, as well as recalculating the total number of accessible cells, is necessary only when a certain event occurs that affects a given segment.
Solution time is O ( n log ( n )), where n is the total number of barriers.
Video:
Source: https://habr.com/ru/post/239681/
All Articles