Lecture
Это окончание невероятной информации про .
...
instructions without doubting them. Assume that my phone number is an ordinary ten-digit number. First, you need to cube this number (first multiply it by itself, then multiply the resulting product by the original number again). The answer will be a 30-digit number, and it must be exact. Do this multiplication, even if you have to do it by hand, and double-check it. Then you need to carry out the longest division process of your life. Divide the resulting number by 5,053,366,937,341,834,823. It's important not to make a mistake! Send me only the remainder of this division. It's important that you send only the remainder, not the quotient».
Suppose Petya has access to the internet (a fairly reasonable assumption nowadays, isn't it?), then we write:
«Petya, go to the website www.wolframalpha.com. You'll see a long rectangle there with an orange border. Enter my 10-digit phone number into this rectangle without any hyphens, dots, or parentheses – just ten digits. Right after the phone number, type the following
^3 mod 5053366937341834823.
Then click the small equals sign on the right side of the rectangle. The answer will probably be a 20-digit number that will appear in a box labeled Result. Send me that answer, and only that answer».
Naturally, Katya will read these instructions, and she'll also read Petya's reply. But she won't be able to understand anything. She got a 20-digit number, which, as she knows, is the remainder of the cube of the phone number divided by 5053366937341834823, modulo. So far no one has come up with an efficient way to recover the original number – in this case the phone number – from the remainder.
Can you suggest something even better? Yes, since you have a secret decoding key. This is d, the inverse of e mod (p - 1)(q - 1). There is a convenient algorithm for computing it, which you can use, of course, provided you know the two prime numbers p and q that were used to obtain N. (You do know them, because you chose them yourself, remember?)
Call the encoded number/message that Petya sent back to you Y. His original message was
Yd mod N.
To determine this value, you just need to enter it into Wolfram Alpha (replacing Y, d, and N with the actual numbers).
Katya knows N, since it was written on the card you asked her to pass to Petya. She knows Y, since that number was in Petya's reply that he sent you. But she doesn't know d, and she has no way of figuring it out. Katya runs into an algorithmic difficulty. Multiplying two numbers presents no difficulty to anyone, after all, everyone was taught that in school. But determining the factors, given a huge number, is much harder.
This puzzle analysis is from the book «Are You Really Smart Enough to Work at Google?».
Original article.
Original: http://tproger.ru/articles/problems/
28,223
Technocup is a programming olympiad organized by Mail.Ru Group, Bauman Moscow State Technical University, and MIPT for students in grades 8-11, as well as a potential opportunity to get into top technical universities through success in programming.
Two qualifying rounds of the 2016/2017 Technocup are behind us, and the third qualifying round took place on December 25. Now the main event is expected – the in-person competition in March 2017. There are still a few months to go, so you can study a couple of resources or check out the championship's VKontakte group. In addition, it will be useful to look at the analysis of problems from the qualifying rounds that have already taken place (given below).
The first «Pilot» Technocup was organized in an extremely tight timeframe. From the moment the idea arose (which, incidentally, was proposed by a student at Bauman Moscow State Technical University) to presenting the project to management, only a month passed. In the remote stages, school students were asked to solve five problems, based on the results of which 150 participants from each qualifying round were invited to the final. During the in-person stage, over the course of three hours, participants solved problems at venues at Bauman Moscow State Technical University and MIPT. Everything took place online. The participants competed in writing code and «hacking» other people's solutions – according to participants, it was exciting and engaging. Codeforces and the university instructors who developed the problems tried to make them as interesting as possible.
Today, Technocup has 5,500 users, 1,000 participants in each qualifying round, and 200 finalists who have already made it to the final. During the olympiad, participants are asked to solve algorithmic problems and come up with tests for their peers' solutions. If you're not passionate about programming, it's impossible to handle Technocup's assignments. The championship's participants are students who are specifically planning to enter leading technical universities.
Starting in 2017, winning and placing in the championship provides official benefits when applying to Russian universities. Technocup's partner, MIPT, offers winners 100 points in computer science. And admission to Bauman Moscow State Technical University for championship winners is possible without entrance exams at all.
And finally – the promised analysis of the problems from the first and second qualifying rounds.
727A – Transformation: from A to B
Vasily has a number a, which he wants to turn into a number b. To do this, he can perform two types of operations:
You need to help Vasily get from number a to number b using the described operations, or report that it is impossible.
Note that this problem does not require minimizing the number of operations. It is enough to find any way of getting from number a to number b.
Solution analysis
We will solve the problem in reverse – we will try to get from number B to number A.
Notice that if number B ends in 1, then the last operation Vasily used was to append a 1 to the number on the right. So let's remove the last digit from B and move to the new number.
If the last digit is even, then the last operation Vasily used was to multiply the number by 2. So let's divide B in half and move to the new number.
If B ends in an odd digit other than 1, then the answer is «NO».
After we move to the new number, we need to run the described algorithm again. If at some step we get a number equal to A, then we have found the answer, and if we get a number smaller than A, then the answer is «NO».
727B – Receipt total
Vasily left the store, and he became curious to recalculate the total on his receipt. The receipt is a string in which the names of purchases and their prices are written one after another without spaces. The receipt has the form «name1price1name2price2…namenpricen», where namei (the name of the i-th product) is a non-empty string of length at most 10, consisting of lowercase Latin letters, and pricei (the price of the i-th product) is a non-empty string consisting of dots and digits. Products with the same name may have different prices.
The price of each product is written in the following format. If a product costs a whole number of rubles, then the kopecks are not written.
Otherwise, after writing the number of rubles, a dot is appended to the price, followed by exactly two digits representing the kopecks (if there are fewer than 10 kopecks, a leading zero is used).
Also, every three digits (from less significant to more significant) in a ruble amount are separated by dots. Extra leading zeros are not allowed; the price record always starts with a digit and ends with a digit.
For example, the price records:
Write a program that, given the contents of a receipt, finds the total price of all purchases.
Solution analysis
In this problem, one had to carefully do exactly what was written in the statement. One could first extract all consecutive sequences of digits and dots that were prices.
Then one had to extract the whole number of rubles from each price and separately sum all the whole prices into a variable r. The same had to be done for kopecks from each price, adding them into a variable c.
After processing all the prices, one had to convert kopecks to rubles, that is, add to r the value c / 100 (the integer part of dividing c by 100), and assign c the value c%100 (the remainder of dividing c by 100). After that, all that remained was to carefully print the answer, not forgetting that if c < 10, a 0 must be printed first for the kopecks, then c, since the number of kopecks must consist of exactly two digits per the problem statement.
727C — Array Restoration
This is an interactive problem. You need to use the flush operation after printing each query. For example, in C++ you should use the function fflush(stdout), in Java — use System.out.flush(), and in Pascal — flush(output).
In this problem you need to restore an array that is unknown to you in advance. You may assume that the jury has conceived some array a, of which you only know its length n.
The only allowed action is to find out the sum of a pair of elements by specifying their indices i and j (the indices must be distinct). As a result of a query for indices i and j, you will receive the sum ai + aj.
It is known that the entire conceived array can be restored in no more than n queries. Write a program that restores the jury's conceived array a of length n using no more than n queries for the sum of two elements (in each query the indices of the two elements must be distinct).
Interaction Protocol
Each test in this problem consists of a single array that your program must restore.
The first line of input contains a positive integer n (3 ≤ n ≤ 5000) — the length of the conceived array. Your program must read this number first.
Next, your program must print to standard output queries for the sum of two elements of the array, or report that the jury's conceived array has already been found.
If the program makes a query for a sum, it should print a line of the form "? i j" (i and j are distinct integers from 1 to n) — the indices of the array elements whose sum your program is querying.
If the program reports the restored array, it should print a line of the form "! a1 a2 … an" (it is guaranteed that all ai in a correctly restored array are positive integers not exceeding 105), where ai equals the number located in the array at position i.
The result of a comparison query is a single integer equal to ai + aj.
For an array of length n, your program must make no more than n sum queries. Note that printing a line of the form "! a1 a2 … an" is not considered a query and is not counted toward their number.
Don't forget to use the flush operation after every line printed.
After printing the answer, your program must terminate.
Solution analysis
Initially, let's make three queries for the sums of numbers a1 + a2 = c1, a1 + a3 = c2, and a2 + a3 = c3.
After this we obtain a system of three equations with three unknowns a1, a2, a3. After simple calculations we get that a3 = (c3 - c1 + c2) / 2. After that, a1 and a2 are easily found. Now we know the values of a1, a2, a3, having spent 3 queries on this.
Then, for all i from 4 to n, we need to make a query for the sum a1 + ai. If the resulting sum equals ci, then ai = ci - a1 (recall that we already know the value of a1).
In this way, the entire array can be restored, spending exactly n queries on it.
727D — T-Shirt Distribution
As souvenirs at a programming competition, it was decided to hand out T-shirts. In total, the print shop printed T-shirts of six sizes: S, M, L, XL, XXL, XXXL (sizes listed in increasing order). For each size from S to XXXL, you know the number of T-shirts of that size.
During registration, the organizers asked each of the n participants to indicate their T-shirt size. If a participant was undecided between two sizes, he could indicate two adjacent sizes — meaning that either of the two sizes would suit him.
Write a program that determines whether it is possible to give every competition participant a gift from the T-shirts printed at the print shop. Of course, every participant must receive a T-shirt of their size:
In case of a positive answer, the program should find any one of the possible distributions of T-shirts.
Solution analysis
Let the array cnt store how many T-shirts of each size the print shop has.
Initially, let's give out T-shirts to those who definitely want a T-shirt of a single size, decreasing the corresponding value in the cnt array. If at some point there aren't enough T-shirts, then no answer exists.
Now it remains to distribute T-shirts to those who want a T-shirt of one of two sizes. Let's proceed greedily. Let's distribute size S T-shirts to the maximum extent to those who want them or size M T-shirts.
After that, let's move on to size M T-shirts, and first distribute them to the maximum extent to those who want size S or M T-shirts but didn't get an S T-shirt, and then, if size M T-shirts remain, distribute them to those who want them or size L T-shirts. In a similar way, let's distribute T-shirts of the remaining sizes.
If after all the T-shirt operations someone ends up without a T-shirt, then no answer exists; otherwise, an answer has been found.
727E — Games on a Disc
Tolya had n computer games, and he decided to record them onto a single disc. After that, he decided to write with a marker the names of all his games on this disc in a circle, clockwise, one after another. The names of all the games were different, and the length of each name was exactly k. The names written on the disc do not overlap with each other.
After Tolya wrote the names of all the games, a cyclic string of length n·k appeared on the disc.
Several years passed and Tolya has already forgotten which games are recorded on his disc. He remembers that at that time there were g popular games in total, and only these games could be on his disc, with each of the g games recorded on the disc at most once.
Your task is to restore any valid list of games that Tolya could have recorded on his disc.
Solution analysis
Using the Aho-Corasick algorithm, let's build a suffix tree on the set of game names such that at the tree vertex corresponding to the name of some game (a vertex at depth k) we store the number of that game.
The trie we've built allows us to append characters to some string one at a time and determine the vertex in it corresponding to the longest prefix, among all prefixes of the game names, that matches the suffix of our string. If the length of this prefix equals k, then the suffix matches some game name.
Let's write the string from the input data twice and compute idxi — the index of the game whose name matches the substring of the doubled string from index i - k + 1 to index i inclusive (if there is none, then -1).
Now it remains to iterate over the index of the character that is last in the record of the name of some game on the disc. Obviously, this index can be iterated from 0 to k - 1. With a fixed index f, it suffices to check that all names with last characters at indices f + ik mod nk for 0 ≤ i < n are distinct (to do this, we check that among idx(f + ik)%nk + nk there is no -1 and that they are all distinct). If this holds — we output YES and easily reconstruct the answer. If the conditions do not hold for any f, we output NO.
The asymptotic complexity of the solution — O(nk + ∑|ti|)
727F — Polycarp's Problems
Polycarp — is an experienced participant of the Codehorses programming competitions. Now he has decided to try his hand as a problem author.
He sent the round coordinator a set of n problems. Each problem is characterized by its quality; the quality of the i-th problem equals ai (ai can be positive, negative, or zero). The problems are sorted by their intended difficulty, which is in no way related to quality. Thus, the easiest problem has number 1, and the hardest — number n.
At the current moment, the coordinator's mood equals q. It is known that after reading the next problem, his mood changes by the quality of that problem, that is, after the coordinator reads a problem with quality b, the value b is added to his mood. The coordinator always reads the problems in sequence from the easiest to the hardest; the order of reading the problems cannot be changed.
If at some point the coordinator's current mood becomes negative, he immediately stops reading and completely rejects the entire problem set.
Polycarp wants to discard the minimum number of problems so that the coordinator's mood is always non-negative. Since Polycarp does not know the coordinator's exact current mood, he has m hypotheses of the form "the coordinator's current mood is q = bi".
For each of the m hypotheses, find the minimum number of problems that need to be removed from the set so that, when reading the remaining problems from the easiest to the hardest, the coordinator's mood is always greater than or equal to 0.
Editorial
Let us first solve the problem for a single value of Q. It is easy to show that the optimal behavior is as follows: we add the next problem of quality ai to the set of retained problems; while the mood value (the sum of the qualities and Q) is negative, we remove from the set of retained problems the problem with the worst quality. The quality of such a problem will necessarily be negative, so we will not spoil the mood value for the previous problems. Such a simulation is easily carried out using the std::set or std::priority_queue structures.
The reasoning above allows us to answer a query in O(n log n), however O(mn log n) does not fit within the time limit. Therefore, it should be noted that as Q increases, the number of removed problems does not increase, and there are only n possible such counts in total. Thus, the problem should be looked at from the other side: for 0 ≤ x ≤ n, compute the smallest value Q can have such that the number of removed problems does not exceed x. This problem is simply solved for each x using binary search in O(n log n log MAXQ), giving O(n2 log n log M AXQ) in total over all x. If we also take into account that we are only interested in m values of Q, then the binary search can be carried out only over them, giving O(n2 log n log m)
From the stored values, for each answer x it remains only to find the first answer whose smallest value of Q is not greater than the value of Q in the query. This can be done naively in O(n) or using binary search in O(log n) (the values of Q for the answers are non-increasing), giving O(mn) or O(m log n) in total.
The best asymptotic complexity will be O(n2 log n log m + m log n), however solutions in O(n2 log n log MAXQ + mn) also pass all tests.
729A — Interview with Oleg
Polycarp interviewed Oleg and wrote it down in his notebook without punctuation marks or spaces, in order to save time and manage to write everything down. As a result, the interview is a string s, consisting of n lowercase letters of the Latin alphabet.
In Oleg's speech there is the filler word ogo, as well as all words that are obtained from the word ogo by appending the syllable go to its right. For example, the words ogo, ogogo, ogogogo are filler words, while the words go, og, ogog, ogogog, and oggo — are not.
Filler words have the maximum possible size, that is, for example, in the speech ogogoo one cannot consider the filler word to be ogo, with goo being part of the ordinary interview phrase. In this case the filler word is the substring ogogo.
Before printing, Polycarp needs to replace each filler word with a sequence of three asterisks. Note that regardless of the length of the filler word, it is replaced with exactly three asterisks.
Polycarp quickly handled this task. Can you do it too? Time's up!
Editorial
In this problem it is enough to go through the string from left to right and, from each successive index, search for the longest substring of the form "ogo…go". If one is found, then "***" must be appended to the answer and we move past its end; otherwise, the next letter must be appended to the answer and we move to the next position.
729B — Spotlights
The theater stage is a rectangular field of size n × m. The theater director has given you a stage plan, according to which actors will be positioned on it. The plan marks which cells will have actors and which will not.
A spotlight installed on the stage will shine in one of four directions (when looking at the stage plan from above) — left, up, right, or down. Thus, a spotlight position is understood as the cell in which it is installed, together with the direction in which it shines.
You are faced with the task of placing a spotlight on the stage in a good position. A position is called good if both of the following conditions hold simultaneously:
You are faced with the task of counting the number of good positions for installing the spotlight. Two spotlight installation positions are considered different if either the cell where the spotlight is located differs, or the direction in which it shines differs.
Let us find the number of good positions in which the spotlight points left. This can be done separately for each row. To do this, one must scan the row from left to right, maintaining a flag indicating that a '1' has been encountered (for example, in the variable f). Then, when processing the next value:
The number of positions for the other three directions can be counted analogously.
729C — The Road to the Cinema
Vasya is at a car rental center and wants to get to the cinema as quickly as possible. The screening for which he has already bought a ticket starts in t minutes. Assume there is a straight road from the car rental center to the cinema, of length s kilometers. Let us introduce a coordinate system such that the car rental center is at point 0, and the cinema is at point s.
It is known that along the way from the car rental center to the cinema there are k gas stations, and at all of them you can refuel with an unlimited amount of fuel completely free of charge! Assume that the refueling operation happens instantaneously.
The rental center has n cars, the i-th of which is characterized by two numbers ci and vi — the cost of renting the car and the capacity of its tank. Thus, at a gas station you cannot pour more fuel into a car than the capacity of its tank vi. At the rental center, all cars are initially fully fueled.
Each of the cars can travel in one of two speed modes: normal and accelerated. In normal mode, the car covers 1 kilometer in 2 minutes, spending 1 liter of fuel on this. In accelerated mode, the car covers 1 kilometer in 1 minute, spending 2 liters of fuel on this. The mode can be changed at any moment. The mode may be changed an unlimited number of times.
You are faced with the task of choosing a car with the minimum rental cost, with which Vasya will manage to get to the movie theater before the start of his showing, that is, no later than t minutes. Assume that at the rental center all cars are initially fully fueled.
Solution analysis
It is clear that there exists a value of the tank size (let us call it w) such that if a car has a tank equal to or larger than w, it will arrive at the movie theater on time, otherwise it will not make it.
The value w can be found by binary search, since the function can(w) (whether the car can and will manage to arrive) is monotonic — it first takes the value false, then true.
After finding w, it is enough to choose the cheapest among all cars with tank size w or greater.
The function can(w) can be implemented by greedily simulating the process. It is easy to write a formula for finding the number of kilometers that can be driven in acceleration mode, if the nearest gas station is at a distance x, and we currently have f liters of fuel:
Thus, in one pass over the array of gas stations in order of increasing distance, one can compute the value of can(w).
729D — Battleship
Galya is playing a one-dimensional battleship game on a field of size 1 × n. In this game, a ships are placed on the grid field, each consisting of b consecutive cells. At the same time, one cell cannot belong to more than one ship, however, ships may touch each other.
Galya does not know the position of the ships. Galya can make shots at cells, and after each shot she is told whether that cell is part of some ship (in which case Galya is said to have «hit»), or not (then Galya has «missed»).
Galya has already made k shots and all of them were misses.
You are faced with the task of determining the minimum number of positions, by shooting at which Galya is guaranteed to hit at least one of the ships.
It is guaranteed that there exists at least one arrangement of ships satisfying the described conditions.
Solution analysis
Note the fact that if there are b consecutive zeros on the field, one must necessarily shoot at one of them. Suppose that all ships were pushed as far right as possible. Let us place twos in those cells where maximally right-pushed ships could be located. Let us iterate over the cells of the field, starting from the left, and shoot at a cell if it contains a 0 and it was preceded by b - 1 consecutive zeros. After that, it remains to shoot at any single cell containing a two. All the shots described will be the answer.
729E — Subordinates
A large company employs n employees, each of whom has a unique number from 1 to n. Among them, exactly one employee is the chief, whose number is s. It is also known that all employees, except the chief, have exactly one immediate superior.
Each of the employees was instructed to submit information about how many superiors they have (not only immediate ones). An employee's superiors are understood to be their immediate superior, as well as the immediate superior of that employee's immediate superior, and so on. For example, if a company has three employees, the first of whom is the chief, the second employee's immediate superior is the first employee, and the third employee's immediate superior is the second employee, then the third employee has a total of two superiors — one immediate and one non-immediate. The chief is the superior of all employees except themselves.
Some of the employees hurried, made mistakes in the count, and submitted incorrect information. You are faced with the task of determining the minimum possible number of employees who could have made a mistake when submitting their information.
Solution analysis
Initially, if the chief employee reported that they have superiors, let us replace as with zero. If there are employees who are not the chief but reported the number 0, let us assume that they reported some number greater than what the other employees could have reported, for example n.
There must necessarily be an employee with exactly one superior. If there is none, let us take the employee who reported the maximum number (taking into account everything described above), and replace that number with one. The same operation must be performed for the number 2, 3, and so on, for as long as there remain employees we have not yet considered.
After all employees have been considered, it remains to count the number of employees whose numbers were changed — this will be the answer.
729F — The financiers' game
Financiers Igor and Zhenya got bored one evening, and they decided to play a game. For this they prepared n securities, which contain information about the company's income over certain time intervals. Note that the income can be positive, zero, or even negative.
Igor and Zhenya laid out all the papers in a row and decided to take turns. Igor will take papers from the left, and Zhenya from the right. Igor goes first and takes 1 or 2 securities of his choice from the left. Then, on each subsequent turn, a player may take k or k + 1 papers from their side, if the player who moved before them took exactly k papers. Neither player may skip a turn. The game ends when the papers on the table run out, or when a player is unable to make a move.
You are faced with the task of determining the difference between the sum of the incomes of the papers taken by Igor and the sum of the incomes of the papers taken by Zhenya, if both players play optimally. Igor wants to maximize the difference, and Zhenya wants to minimize it.
Solution analysis
Let us solve the problem using dynamic programming. It is fairly clear that a position is characterized by three numbers: the boundaries of the segment of papers still lying on the table, and the number of papers taken by the previous player; as well as whose turn it is. So let Ilrk be the result of the game if only the papers from l to r were initially on the table, Igor moved first, and would make a move of k or k + 1. Similarly, let Zlrk be the same, but Zhenya moves first. It is clear that in the general case:
One must carefully handle cases where a player cannot take the required number of papers. The answer to the problem is the value I1n1.
At first glance it seems that such a solution has an asymptotic complexity of O(n3). However, upon closer examination this is not so. What values can l, r and k take?
First, (k(k+1))/2 ≤ n, since if the last player took k papers, then a total of at least 1 + 2 + 3 + … + k = (k(k+1))/2 papers have already been taken. From this, k does not exceed √(2n).
Second, let us look at the difference between the number of papers taken by Zhenya and by Igor, that is, at the quantity d = (n - r) - (l - 1). Suppose that at this point the players have made an equal number of moves, that is, it is now Igor's turn. Then 0 ≤ d ≤ k - 1. Indeed, on each turn Zhenya takes either the same number of papers as Igor, or one more, and the “length” of the turn increases. In total, the length of the turn has increased by k - 1, which means that this difference is no greater than k - 1. Thus, we can number the states by the numbers l, d and k, and the total number of states is O(n2). We will not consider states in which it is Zhenya's turn, but will immediately add them to the transition and enumerate both possible response moves (four transitions in total). The final asymptotic complexity is O(n2), and the easiest way to implement this solution is by recursive enumeration with memoization.
737E — Tanya turns 5!
Tanya has turned 5 years old and all her friends have gathered for the birthday celebration. In total, including Tanya, there are n children present at the party.
The celebration is already coming to an end, but slot machines are planned as the finale. In the hall where the celebration is taking place, there are m slot machines, numbered from 1 to m. Each of the children has already made a list of the machines they want to play. Moreover, if a child wants to play a particular machine, they know exactly how much time they need to enjoy playing on it. Only one child can play on any given machine at a time.
Since the celebration has already dragged on, all the adult guests already want to go home. To speed up the process, you can additionally order second copies of machines; to rent a second copy of machine j you must pay pj burles. Once a machine has been rented, it can be used until the end of the celebration.
How soon can all the children play according to their wishes, if you have a budget of b burles for renting additional machines. For each machine there is only one spare available, so it is not possible to rent a third copy of a machine.
Children may interrupt their play in an arbitrary manner. If child i wants to play machine j, then after renting an additional copy of machine j, it is permissible for them to play part of the time on the main copy of machine j, and part — on the additional one (and either of these parts may be reduced to zero). Switching between machines can happen instantaneously at integer moments in time. Of course, a child cannot play on two machines at the same time.
Remember that there is no goal of saving money (we don't economize on children!); the goal is to minimize the finishing time of the last child to finish playing.
Solution analysis
Let us first solve the problem in a simplified formulation: suppose there are no duplicate machines at all (in other words, that the budget b is not enough to rent any of the duplicates).
We can assume that every child wants to play every machine. Indeed, we simply assume that in this case ti, j = 0. Thus, we can consider the values t to form a rectangular table — for each child/machine pair, the cell records the playing time.
Obviously, the minimum time by which all games will end is no less than the sum of the values in each row Ri = ti, 1 + ti, 2 + … + ti, m. Similarly, since at most one child can play on each machine at a time, the minimum time by which all games will end is no less than the sum of the values in each column Cj = t1, j + t2, j + … + tn, j.
Consequently, the minimum time is no less than max(R1, R2, …, Rn, C1, C2, …, Cm). In fact, there always exists a schedule such that the sought minimum time equals the maximum of all the row sums and all the column sums. Let us call this quantity T.
Let us demonstrate this fact, and at the same time propose a way of finding the desired schedule.
Let us construct a weighted bipartite graph, with n + m vertices in each part.
Let us imagine that each machine has an imaginary child, so now there are n + m children (n real and m imaginary). The vertices of the first part will correspond to children: u1, u2, …, un — vertices corresponding to real children, and un + 1, un + 2, …, un + m — vertices corresponding to imaginary children, where un + j is the imaginary child of machine j.
Similarly, let us imagine that each child has an imaginary machine (there will be n of them). The vertices of the second part will correspond to machines: the first m vertices to real ones — let us denote them as v1, v2, …, vm, and the next n to imaginary ones — vm + 1, vm + 2, …, vm + n. Vertex vm + i will correspond to the imaginary machine of child i.
Let us draw edges. We will have four types of edges:
We will draw the edges so that the sum of the weights of the incident edges for each vertex turns out to equal T.
Edges of type 1. We will draw an edge between ui and vj if ti, j > 0. We will assign the edge weight ti, j. The presence of such an edge indicates that the child must play on the machine for the required number of minutes.
Edges of type 2. The presence of such an edge indicates that the machine will have a forced idle period of a certain number of minutes (in other words, during this time the imaginary child of this machine will be "playing" on it). For all j from 1 to m, find a - Cj. If this quantity is positive, draw an edge between un + j and vj of that weight.
Edges of type 3. The presence of such an edge indicates that the child will have a forced idle period of a certain number of minutes (we can consider that the child spends this time playing on the imaginary machine). For all i from 1 to n, find a - Ri. If this quantity is positive, draw an edge between ui and vm + i of that weight.
Edges of type 4. After adding edges of types 1-3, it is obvious that the sums of the weights of the incident edges for all vertices u1, u2, …, un, v1, v2, …, vm exactly equal T. For the vertices un + 1, un + 2, …, un + m, vm + 1, vm + 2, …, vm + n, however, this sum is so far less than or equal to T. Let us add a series of edges between these vertices so as to make these sums equal to T as well. This can always be done, simply by greedily adding such edges.
The following fact is known: in an arbitrary regular bipartite graph there exists a perfect matching (a corollary of Hall's theorem).
If we look at the given graph as an unweighted multigraph (a graph with multiple edges), where the weight of an edge in our graph denotes the number of edges between a pair of vertices, then the resulting graph will be a regular graph, and the fact above will hold for it (that is, a perfect matching will exist).
Let us find a perfect matching using Kuhn's algorithm in the weighted graph (as shown above, it is guaranteed to exist). Let us choose the weight of the minimum edge in it; let this quantity equal M. Then we assign children to machines for each edge between the vertices u1, u2, …, un and v1, v2, …, vm for time M. Furthermore, from the weight of each edge of the matching we subtract M. If an edge's weight becomes 0, we remove the edge.
After this, the graph remains such that the sum of the edge weights for each vertex is constant. This means it again has a perfect matching. Let us repeat the same operation with it.
We will continue in this manner as long as there is at least one edge in the graph. The schedule found is the one sought.
In fact, to speed things up in this part of the solution, one need not search for the matching from scratch each time, but can extend it from unsaturated vertices of the first part, if any are found. This algorithm in total will run in O(e2), where e is the initial number of edges, that is e = O(nm), so the asymptotic complexity of the algorithm becomes O(n2m2). Specifically in this problem, the constraints were small, and matchings could be built from scratch each time using Kuhn's algorithm.
Moreover, in fact we are constructing an optimal coloring of a bipartite graph. Presumably, to find it one could simply apply a known algorithm (read up on optimal edge coloring of a bipartite graph).
So, we have solved the problem without renting duplicate machines. Moreover, the value of the answer can be found quite simply as the maximum of all the row sums and all the column sums of the child/machine time matrix.
If duplicate leases are allowed, they are equivalent to adding a column into which values from the given column can be partially distributed. Of course, it is advantageous to do this with a column if the sum over it is Cj = T (that is, if the answer bottlenecks on it). It only makes sense to do this simultaneously for all columns for which Cj = T.
Therefore, the stage of determining which machines should be leased looks like this. We calculate the sum of the lease payments for all machines for which Cj = T. If this value is less than or equal to the budget b, we lease all these machines. We add the corresponding columns to the table, distributing the values from the duplicated columns among them as evenly as possible. We recalculate T. We repeat the process and stop it when the sum of the lease payments for the next operation exceeds b.
737F — Dirty plates
After another holiday, a stack of dirty plates has piled up in Nikita's kitchen. They need to be washed and placed in the drying rack, and in the drying rack the plates must also stand in a stack, with the sizes of the plates increasing from top to bottom. All plate sizes are different.
Nikita does not have much free space, namely, there is room for only one more stack of plates. Therefore, he can only perform two operations:
Take any number from 1 to a of the top plates from the stack of dirty plates, wash them, and place them in the same order on top of the intermediate stack.
Take any number from 1 to b of the top plates from the intermediate stack and place them in the same order on top of the stack in the drying rack.
Note that when performing either operation, the plates are placed on the stack in the same order in which they were before the operation was performed.
You know the sizes of the plates s1, s2, …, sn in the order in which they lie in the stack of dirty plates from top to bottom, as well as the numbers a and b. All plate sizes are different. Write a program that determines whether Nikita can arrange all the plates in the drying rack in increasing order from top to bottom, and if he can, find some, not necessarily optimal, sequence of actions to do this.
Solution analysis
Let us first try to solve the problem when there are no restrictions on a and b. It is clear that if it is impossible to rearrange the plates in this case, then it is also impossible with restricted a and b.
Let us consider which operations can and cannot be performed. It is clear that plates cannot be moved onto the drying-rack stack out of order, since we cannot remove them from there. It is also clear that if, at some point, we can move a certain sequence of plates from the top of the intermediate stack to the top of the final stack, and they will take their correct place there, then this can be done right away. The same applies to the stack of dirty dishes, but that will take two operations. It is also easy to notice another situation which, once we fall into it, means we can no longer reach the answer: if, in the intermediate stack, a plate of size y lies directly on a plate of size x, and y < x - 1. Indeed, no sequence of actions will allow us to insert the "missing" plates between them. Let us call a position a dead end if such a situation has arisen in it.
Let us call an operation that moves plates into the drying rack so that they end up in their correct places laying out. Since laying out can be performed at any moment, after each operation we will check whether such an operation is possible and perform it if so. Next, we will examine situations in which laying out is not possible.
Let us call a sequence of plates almost decreasing if it consists of one or more blocks of plates, in each of which the plate sizes are consecutive integers, while in each subsequent block all the sizes are smaller than in the previous one. In other words, an almost decreasing sequence looks like this: x1, x1 + 1, x1 + 2, …, y1, x2, x2 + 1, x2 + 2, …, y2, x3, …, where x1 > y2, x2 > y3, and so on. Let us consider the maximal sequence of plates from the top of the dirty stack that forms an almost decreasing sequence. It is clear that, before we move the entire stack, an operation that moves into the intermediate stack anything other than elements of this sequence will create a dead-end position, since the size of the last plate in this sequence is at least 2 less than the size of the next plate. It is also clear that we will not be able to perform a laying out before we move the whole sequence to the intermediate stack. Either way, the only possible next actions are to move this sequence to the intermediate stack, the only question being in what order. Two cases are possible:
We see that in each situation we found the optimal move, which means that the problem with a = b = ∞ can be solved by simulating these optimal moves in O(n2), or, if desired, in O(n). If, at the end, all the plates end up in the drying rack, then we have found a solution; otherwise there is no solution.
Now let us deal with the restrictions on a and b. The laying out operation from the dirty stack can still be carried out, by moving plates one at a time into the intermediate stack, and then one at a time again into the drying rack. Laying out from the intermediate stack is not always possible, so it is necessary to keep track of the size of the blocks in the intermediate stack. However, if there is a laying out that can be performed, then it must be performed, and if it cannot be performed, then we will not be able to lay out the plates in the required manner. Therefore, from here on we will again assume that all possible layings out have been done. Let us again consider the largest almost decreasing sequence in the dirty stack, and the same two cases:
Thus, once again, at every step we have an optimal move. The solution is to simulate the optimal moves. It can be implemented in O(n), but, in order not to complicate things with unnecessary steps, constraints were given that allow writing a solution in O(n2).
Часть 1 Algorithm Quizzes
Часть 2 Limitations - Algorithm Quizzes
Часть 3 Solution 1. The size of the linked list is known
Часть 4 Simple solution - Algorithm Quizzes
Часть 5 «Simple» Solution: O(N4) - Algorithm Quizzes
Часть 6 Analysis of problems from the first qualifying round - Algorithm
Comments