This is the fifty fifth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra We have already seen Max flow and last time we used it to ensure…

This is the fifty fourth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Last time we saw how to implement max flow in ILP. Today we are…

This is the fifty third part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Today we are going to implement Maximum flow in ILP. We use the following…

This is the fifty second part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra In part 2 we saw how to calculate unsigned magnitude decomposition for non-negative integer…

This is the fiftieth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Today we are going to solve three graph problems: vinimum spanning tree, vertex cover and…

This is the forty ninth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Today we solve the task B from Deadline24 2018 edition.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
Sewage system Introduction Beetlejumpers are known throughout the Universum for their concern for the infrastructure and industrial facilities of their worlds. The exceptional quality of solutions provided throughout the worlds is due to the high-quality materials, as much as. . . to the extraordinary skills of Beetle-architects. To become one of the famous Beetle-architects one has a long way to go. One of the first challenges on this career path is the work on the less elegant, but no less important projects – such as planning the sewage system layout. Competence examination for 2nd degree Beetle-prearchitect includes, among others, the following problem: Connect entrance connections with exit connections in a given area with the dimensions X * Y . It is a typical examination problem, so there are numerous conditions simulating the real work: - there is not much vertical space, so the pipes must not cross, - due to optimization requirements the whole space must be covered with pipes, - due to safety standards concerning pressure, each connection must be used only once. Naturally, the area the examinee is working on is precisely defined, i.e., pipes cannot protrude beyond the area. Problem An area with dimensions X * Y and the number of the necessary connections – N are known. Also known is the set of start points with their corresponding end points (N pairs of coordinates). The problem is to generate pipeline descriptions: each description must begin at one of start points and finish at a corresponding end point. Each field of a given area must be used exactly once and all pipelines must fit within the borders of the area. Input data Test sets are given in flow*.in files. The first line of the test set includes one integer T denoting the number of tests. Description of each test contains the definition of the area and connections belonging to it. The first line of the test description includes two natural numbers X and Y that denote the dimensions of the area to be covered with pipes. The second line includes a natural number N – the number of pipelines (connections) to be built. Each of the following N lines contains four natural numbers separated by spaces – information concerning the pairs of connection points. The first two numbers in each of those lines (x_s^i, y_s^i ) denote the pipeline start point coordinates. The following two numbers in each of those lines (x_e^i, y_e^i ) are the endpoint coordinates of the same pipeline. Each test has at least one correct solution. 1 <= T <= 10 5 <= X; Y <= 100 1 <= N <= 600 1 <= x_s^i, ; x_e^i <= X 1 <= y_s^i ; y_e^i <= Y 1 <= i <= N Output data As an answer to each test provide definitions of pipeline routes. Test answers must be provided in the same sequence as in the input data file. The first line of the test answer should contain N – the number of pipelines. The following N lines should include sequences of characters Ck. Each character Ck can take one of the following values (the pair (i; j) was adopted as current coordinates): - ’N’ – for the move to j - 1 line (up), - ’E’ – for the move to i + 1 field in the same line (to the right), - ’S’ – for the move to j + 1 line (down), - ’W’ – for the move to i - 1 field in the same line (to the left). Each sequence corresponds to one pipeline and describes consecutive steps of moving around a given area, beginning at start point and finishing at its corresponding end point (if a pipeline covers the area of F fields, its description should consist of F - 1 characters). Pipelines should be presented in the same sequence as their start and end points were provided in the input data file. Example For input data: 2 3 3 2 1 1 3 3 1 2 1 3 4 7 4 1 1 1 7 2 1 2 7 3 1 3 7 4 1 4 7 One of possible solutions is: 2 EESWSE S 4 SSSSSS SSSSSS SSSSSS SSSSSS |

Idea is: for…

This is the forty eighth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra You are given board with thirty rows and fifteen columns. For each cell you…

This is the forty seventh part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Today we are going to solve Battleship puzzle. It is very similar to nonograms…

This is the forty sixth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Hi. Today we are going to generate Gray code using ILP. I am not…

This is the forty fifth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Today we solve Election task from Deadline 24 2017 using ILP. You can read…

This is the forty forth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Today we are going to solve Pizza practice problem from Hash Code 2017 contest…

This is the forty thrid part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra We have already seen how to implement function in ILP. Last time we used…

This is the forty second part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Today we solve another puzzle: Fifteen puzzle. Let’s begin. Game Image from Wikipedia. In…

This is the forty first part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra We continue our exploration of riddles solvable by ILP. Today we are going to…

This is the fortieth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra We already know how to implement binary logic in ILP, today we are going to…

This is the thirty ninth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Today we are going to simulate non-deterministic Turing machine using ILP. Let’s begin. Idea…

This is the thirty eighth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Today we are going to implement basic data structure: array. If you know functional…

This is the thirty seventh part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Today we are going to solve “Send more money” problem. We have the following…

This is the thirty sixth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Today we will try to introduce various goal types to our problems. There are…

This is the thirty fifth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Last time we saw how to implement Special ordered sets in ILP. Today we…