### pleasurepain's blog

By pleasurepain, 2 days ago, ,

140A - New Year Table

One should take care of the precision problem. We need an angle θ to “include” a circle with radius r, where . Thus, we can have small circles, which is . To avoid wrong answer caused by precision, we can implement x ≤ y + ε instrad of x ≤ y.

140B - New Year Cards

In fact, we only need fill a table, where the entry in row i and column j denotes the card that is given to the j-th person after the i-th card is obtained. A simple observation is that when the i-th card is obtained, we should first find out the one with the maximum preference, and denote its index as p. It is obvious that this card should be given to every person except for the one with index p. For him, we should give the card with the second maxumum preference. Thus, it is sufficient to find out the cards with the first and second maximum preference, and fill the table with them.

Moreover, we should also keep updating the best card that each person can obtain. To calculate this result, we should first convert the preference sequence of each person into a “rank” sequence, which tells the rank of each card in the preference sequence.

Once completing the above implementation, we can find out the answer for each person column by column. For each column, we can start from bottom to top, and once we find that the entry in the current row is equal to the best card, we can store the row index as the answer and immediately skip to the next column.

140C - New Year Snowmen

The optimal strategy is that we keep updating the number of different sizes, and always select the three balls that have the maximum numbers. Well, I did not figure out the proof...

The above idea can be simply implemented by using a priority queue. However, the data should be compressed in previous since the given range is too large.

I have learned a very neat and general method. For an array a[n], we first copy all the elements to another array b[n] as a backup. Then, we sort a[n] in an increasing order, and set m = unique(a, a + n) - a, after which m will be equal to the total number of unique elememts (“unique” can be found in STL of C++). Finally, we implement id = lower_bound(a, a + m, b[i]) for every b[i] (“lower_bound” also belongs to STL of C++). After the above steps, in fact we have already mapped b[i] to a smaller number id.

140D - New Year Contest

There exists a greedy solution.

We sort the given sequence in an increasing order. Then, we keep updating the prefix sum and the current problem can be successfully submitted as long as the corresponding prefix sum does not exceed 720. For each problem with a prefix sum that is not larger than 360, its penalty time is zero; otherwise, it contributes a penalty time which is equal to the difference between 360 and the corresponding prefix sum.

The greedy solution can be proved by a standard scheme, which can be found in many books.

•
• +3
•

By pleasurepain, 3 days ago, ,

139A - Petr and Book

We can first calculate the total number of pages that can be finished within one week. Then, we divide the total number of pages by this number and obtain the residual. Finally, for this residual, we find the last day on which the whole book is finished.

139B - Wallpaper

The description seems a little difficult to understand...

We should first rotate the wall papers with 90 degrees so that the stripes are vertical. Then, we cut it into as many pieces as possible according to the height of the room. Next, we compute the total length that these pieces can cover, and finally obtain the number of rolls that is necessary to decorate the whole room.

139C - Literature Lesson

A straightforward implementation problem, but one needs take care of “corner” cases.

139D - Digits Permutations

This is in fact an exhaustive search problem.

At first, we enumerate the number of 0s at the end. Then, we enumerate all the combinations of the first sum that is equal to 10, counting from right to left. Finally, we find all the digits that have sum equal to 9. This algorithm has complexity O(10N), and we only need record the maximum number of consecutive 0s among all the enumeration and the corresponding combination.

139E - Mushroom Gnomes - 2

I think this is a very nice problem to practice segment tree with lazy propagation. One can find a lot of materials on the Internet about this technique, and one could also read chapter 28 in book Competitive Programmer's Handbook — a new book on competitive programming, which provides many detailed descriptions and talks about how to implement it.

Besides, there is still one important issue that should be considered. We should be very careful of precision problem. Instead of directly using probability domain, it is better to convert it into logarithm domain, since this can in general achieve a better dynamic range by replacing multiplication with addition. However, if the probability is zero, log(0) will lead to an exceptional case. To avoid this, we can aasign, for instance,  - 1000 instead of log(0).

•
• +1
•

By pleasurepain, 8 days ago, ,

It took me about one year to complete about 100 virtual rounds.

I learned a lot of techniques that I had seldom read in books or even never heard of before, like segment tree with lazy propagation, bit-mask dp and so on.

In the early stage, I could only solve about two div2 problems. As time goes on, I found that I could solve more and even all div2 problems, either on my own or by reading tutorials.

I also got familiar with a lot of IDs as I kept participating in more virtual contests. At first, I competed with them together in div2 but they improved quite fast and went to div1, and as it turns out, they are legends now. But I guessed that before legends become legends, they had similar experiences like us, too, facing challenges, keeping practicing, handling various problems, and making progress day by day.

This makes me believe more deeply, that hard working may not be sufficient to achieve one's target, but is at least surely necessary.

Best wishes to everyone's dream, and please never lose hope.

(Finally, I strongly recommend this book Competitive Programmer's Handbook — a new book on competitive programming, written by a great master, and hope that everyone can find something valuable there.)

•
• +196
•

By pleasurepain, 10 days ago, ,

137A - Postcards and photos

We scan the sequence from left to right, and count the number of consecutive 'C's and 'P's. For each such subsequence of length m, it contributes m / 5 + (m%5! = 0) to the final answer.

137B - Permutation

We adopt a hash table to record the integers that have been appearing in the sequence. Then, the answer is just the number of integers that are not stored in the hash table.

137C - History

We sort the events in an increasing order of their beginning time. Then, we scan the events from the last one to the first one, and for each one we check whether it can be completely covered by any other event. We denote the ending time of the i-th event in the sorted sequence as a[i]. It is obvious that only the first i - 1 events can completely cover it, and thus it suffices to check whether there is such an index j < i that a[j] > a[i]. Equivalently, we can check maxj = 0, 1, ..., i - 1a[j] > a[i]. Therefore, we adopt a prefix array to record the maximum a[m] for j = 1, 2, ..., m, and problem is solved.

137D - Palindromes

A DP problem. At first, we use p[i][j] to denote the minimum number of changes we need to convert the substring starting from i while ending at j, to a palindrome, which can be computed with complexity O(n2).

Next, we consider how to describe the rules of dividing the original string into shorter ones with '+', since this helps determine the recursive formula of DP. Suppose that we are going to add m '+'s, and these '+' are always added from left to right. For instance, given that 'abcdefg' has been divided into 'ab'+'cdefg', if we will add another '+', then it can only added among 'cdefg' but 'ab' can not be divided any more. It can be shown that with this rule, the original string can always be divided into any shorter ones and thus no potential answer will be missed.

Now, we use dp[i][j] to denote that we have added i '+'s and the i-th '+' is at position j, and the minimum number to convert these substrings (the ones before j) into palindrome ones is dp[i][j].

Then, for state dp[i][j], it can transfer to states dp[i + 1][j + nextj], where j + nextj > j and j + nextj ≤ n, and dp[i + 1][j + nextj] = min(dp[i + 1][j + nextj], dp[i][j] + p[j + 1][j + nextj]). Also, we should record the “paths” so that we can trace back the division pattern.

137E - Last Chance

The main idea is that for each position i, we calculate the longest substring that satisifes the requirement. We use p[i] to denote the total number of vowels in the first i positions.

At first, for any substring of length len, we transfer v ≤ 2c into 3v ≤ 2len. Then, for any position i, we should find out the maximum index j ≥ i so that 3(p[j] - p[i - 1]) ≤ 2(j - (i - 1)), which is equivalent to 3p[j] - 2j ≤ 3p[i - 1] - 2(i - 1). Therefore, we could build a segment tree based on 3p[j] - 2j. For any node in the tree, it stores the minimum value of its two child nodes (like a minimum heap). Then, for each i, the maximum j can be computed with complexity O(logN), by traversal from top to bottom (it is also possible that no j exists). Finally, we only need scan all the positions and find the maximum length.

By pleasurepain, 2 weeks ago, ,

136A - Presents

A simple inverse-mapping problem.

136B - Ternary Logic

It is similar to binary case, and one should just compute the module based on 3 instead of 2.

136C - Replacement

We first sort the array and then check the largest value a[n - 1]. If it is 1, then we just change it into 2; otherwise, we change it into 1 and sort the modified array again.

136D - Rectangle and Square

Consider all the possible division of the given 8 points, which should be 8!, and check whether we can find a feasible pattern that meets the requirements. Now, the main issue is how to determine that four points form a rectangular or square. At first, we find two neighboring sides and check whether they form a 90 degree, which can be achieved by computing their inner product. Then, we find the two pairs of oppisite sides, and check that whether the two sides belonging to each pair are the same or not. Furthermore, if all of them are the same, it is a square.

136E - Zero-One

We denote the player who plays first as v and the other one as u.

After some observation, one can find that v will always try to remove 1 from left to right while u tries to remove 0 from left to right. At first, we consider the case that the given zero-one sequence does not contain any '?' and has an even length in order to illustrate the essence behind the solution.

If the number of 0s is larger than 1s, then it is obvious that the final result is 00; on the other hand, if we have more 1s than 0s, then the final result should be 11.

If the numbers of 0s and 1s are exactly the same, then we might have 01 or 10 as the final result. One can check that if the last bit is 1 then it must be 01 since no one can take away the last 1. Similarly, the final result is 10 if the last bit is 0.

Now, we generalize the above idea. At first, we consider the case where the length is odd. In fact this can be simply converted to the even case, as long as we add an extra 0 and exchange their moving order. Secondly, we consider the sequence containing '?'. This is in fact quite similar to that containing no '?'. We check whether we can have more 0s, or more 1s, or equal 0s and 1s, by converting '?' into 0s or 1s properly.

By pleasurepain, 2 weeks ago, ,

133A - HQ9+

If the given string contains the required characters except for '+', the answer is yes.

133B - Unary

We can construct the binary sequence according to the requirement, and then calculate its value in decimal form.

133C - Turing Tape

Inverse the binary form and then compute the value...

133D - Piet

This is in fact a straightforward implementation problem, but we should complete some pre-processing in order to avoid TLE.

The main issue that might lead to TLE is that we have to move to one of the four corners within one group. One group may consist of many squares with the same color, and according to DP and CP pointers, after we enter such a group, we must first determine the corner and then move to the next square (or group). This sub-problem can be solved based on DP algorithm. For instance, we use dp[0][i][j] to denote that if we are in the i-th row and j-column and facing to the right, then we should move to position dp[0][i][j], which assembles the prefix or suffix idea. Similarly, we implement the same pre-processing for the other three directions.

133E - Logo Turtle

This problem can be solved by adopting a three dimensional DP. We use dp[i][j][0] and dp[i][j][1] to denote the maximum distance that we can reach, under the state that we have completed the first i commands, and implememted j changes, while facing to the right and left, respectively. For dp[i][j][0], it can transfer to states dp[i + 1][j + nextj][0] and dp[i + 1][j + nextj][1], where nextj ≥ 0 and j + nextj ≤ n. The detailed formula of dp[i][j][0] can be represented as follows, while dp[i][j][1] can be derived in a similar manner.

1) the i + 1-th command is 'F' and nextj is an even number: dp[i + 1][j + nextj][0] = max(dp[i + 1][j + nextj][0], dp[i][j][0] + 1)

2) the i + 1-th command is 'T' and nextj is an odd number: the same as 1)

3) the i + 1-th command is 'F' ans nextj is an odd number: dp[i + 1][j + nextj][0] = max(dp[i + 1][j + nextj][0], dp[i][j][1])

4) the i + 1-th command is 'T' and nextj is an odd number: the same as 3)

However, it is still not done here, since the maximum distance may be “negative”. In other words, we can achieve the maximum distance by moving to the left. Thus, we should implement DP again, but replace max with min. After all of the above steps, we will finally obtain the answer.

132D - Constants in the language of Shakespeare

Well, I searched on the Internet and found that it can be solved with a greedy algorithm. Nevertheless, I did not figure out how to prove it...

We start from the right bit and move to left. We will always try to find a subsequence consisting of consecutive 1s. If there is only one 1, we should assign a  + 2^ to this position; otherwise, we should assign a  - 2^ instead, while deleting these consecutive 1s but changing the next 0 into 1, which indicates that we add a  + 2^ to that position, temporarily.

We give s=10011011 as a simple example. We scan from right to left and first find 11. Then, we assign  - 20 and modify it as s=10011100, and find 111. Now, we assign  - 22, and change it into s=10100000. Next, we assign  + 25 and  + 27. As a result, we obtain  - 20 - 22 + 25 + 27.

•
• +3
•

By pleasurepain, 3 weeks ago, ,

131A - cAPS lOCK

Modify the letters as the problem requires.

131B - Opposites Attract

We use a[i] to denote the number of a non-negative integer i while using b[i] to denote the number of a negative integer  - i (i > 0). For any positive integer i, we have min(a[i], b[i]) choice, while for i = 0, we have choice. Thus, the final answer should be .

131C - The World is a Theatre

We enumerate all the feasible combination of boys and girls, and only consider those that satisfy the requirements. Then, the main issue is to calculate . Although n is not larger than 30, it is still difficult (or infeasible) to compute n!. Thus, we modify the formula as , which could handle all n ≤ 30.

131D - Subway

The solution is first DFS, and then BFS.

At first, we implement DFS to find the unique cycle and all the nodes on the cycle. Then, we implement BFS with all of these nodes as the starting state, and update the distance of each node. One can find plenty of materials about how to find the cycle based on DFS.

131E - Yet Another Task with Queens

There exists a solution with complexity of O(m). We first enumerate all the queens, and update three values for each row. The first value is the total number of queens in the current row; the second value is the position of the leftmost queen; the third value is the position of the rightmost queen. Then, we enumerate all the queens again. For any queen in the i-th row, if the total number of queens in this row is less than or equal to 1, then no queen could threaten it; otherwise, there will be exactly one or two queens that could threaten it, depending on whether it is the leftmost one or the rightmost one, which can be checked with complexity O(1) since we have stored the positions of the leftmost and rightmost queens.

Similarly, for each column, we update three values as well. The first value is the total number of queens in the current column; the second value is the position of the top queen; the third value is the position of the bottom queen. The following operations are almost the same as done when we deal with rows.

Finally, we deal with the diagonals of  + 45 and  - 45 degrees, respectively, and the answer is thus obtained.

131F - Present to Mom

The idea is that we use exhaustive enumeration to deal with one dimension while using “two pointers” to deal with the other dimension, which gives a solution of complexity O(n3).

We use dp[i][j] to denote the total number of stars from column 1 to column j, for the i-th row. Then, we enumerate all the feasible two boundaries of columns. For each combination, we adopt two pointers p1 and p2, both starting from 0, and move p2 downwards while letting p1 chase after p2. This behaves like a sliding window, and we modify its position and size so that it contains t stars, where t is the minimum integer that is not less than k. During this process, we update the answer.

By pleasurepain, 3 weeks ago, ,

We can compute the sum of all the integers. Then, we enumerate each element and test whether their difference is even or not.

129B - Students and Shoelaces

A straightforward implementation problem. We can use BFS to find out all the nodes whose degree is exactly one. The answer is just the total number of BFS.

Note that at the eighth second, all the positions are definitely safe. Therefore, it is sufficient to check whether we can survive within the first eight seconds. One feasible solution is to record and update all the safe positions at each second. If we can survive after eight seconds, it means that we can always reach the right upper corner; otherwise not.

129E - Games with Rectangle

In fact we might obtain some more clear observation if we consider the length and width of each rectangular in an independent perspective. For instance, for the length, the rectangulars can only have positions at (1, 2, 3,... n-1). As there are exactly k rectangulars, we should select 2k positions, which gives Cn - 12k different patterns. Similarly, for the width we have Cm - 12k patterns as well, and thus the final answer should be Cn - 12k × Cm - 12k. Cpq can be calculated by using Pascal triangle.

•
• -3
•

By pleasurepain, 4 weeks ago, ,

127A - Wasted Time

A straightforward implementation problem. Calculate the total distance and then the average time.

127B - Canvas Frames

For each integer i, we denote its total number as a[i]. Note that only a[i] / 2 (integer division) of them can be used to construct a frame. Thus, the total number of frames that can be built is .

127C - Hot Bath

This is also an implementation problem, but we should take care of the following issues:

1) several special cases like t0 = t1 should not be omitted;

2) to find the pair (y1, y2) so that the temperature is closet to t0, it is better to use “integer computation” rather than “double computation”, since the latter one may meet some weird “precision trap”.

The problem can be solved based on the well known KMP algorithm. Specifically, we use the array next[i] in KMP (one can find a lot of details about this on the Internet).

At first, we check next[n]. If it is zero, it means that the answer is definitely “just a legend”; otherwise, we check all next[i] with i = 2, 3, ...n - 1. If at least one of them is equal to next[n], we just find the answer. If there is no such index, we should further check next[next[n]]. If it is zero, it implies that the answer is still “just a legend”, which can be proved by contradiction; otherwise, we just find the answer again.

It turns out that the problem is not that difficult if we have noticed the following rules.

We first focus on the right upper corner point, (1, n). It can be seen that this point only depends on whether there is a command (1, n). Thus, by observing this point, we can determine this command. Then, we move to point (1, n - 1), and it depends on both the commands at point (1, n) and (1, n - 1). As we have known the command of point (1, n), we can immediately determine the result of (1, n - 1) as well. Similarly, we move to point (1, n - 2) and use the above arguments again.

In general, we enumerate rows from 1 to n, and for the i-th row, we enumerate columns from n to i + 1. After this, we have determined the command at all the points (i, j) with i < j. Then, we enumerate rows from n to 1, and for each row we enumerate columns from 1 to i - 1. After this, we have determined the command at all the points (i, j) with i > j. Finally, we enumerate points (i, i) from i = 1 to i = n and determine the command at points (i, i).

126D - Fibonacci Sums

Although n is up to 1018, in fact it is sufficient to consider the first 100 Fibonacci integers, since it increases at the order of about 2i.

We write the Fibonacci sequence as f[i] = (1, 2, 3, 5, ...) also adopt an array a[i] which is initialized with zero. For the given integer n, we find the maximum Fibonacci integer that is not larger than n as f[j] and then set a[j] = 1. Next, we set n to n - f1 and repeat this process until n is reduced to zero. For instance, if n = 13, we have a[i] = (00000100...), while for n = 7, we have a[i] = (0101000...).

Then, let us consider a[i]. For (00001), we can change it into (00110) and further into (11010). Thus, we adopt another array h[i], which denotes the number of consecutive zeros to the left of index i. For instance (00001001), we have h[5] = 4, h[8] = 2 while the other values are zero (indices start from 1).

Finally, we use dp[i][0] to denote the total number of decomposition under the condition that the i-th 1 in array a[i] is changed into zero; while use dp[i][1] to denote the total number of decomposition under the condition that the i-th 1 is not changed into zero. The recursive formula is dp[i][0] = dp[i - 1][0] * ((h[i] + 1) / 2) + dp[i - 1][1] * (h[i] / 2) and dp[i][1] = dp[i - 1][0] + dp[i - 1][1].

By pleasurepain, 5 weeks ago, ,

124A - The number of positions

Enumerate all the integers i and find out those that satisfy both i - 1 ≥ a and n - i ≤ b.

124B - Permutations

Generate all the feasible permutation patterns and find out the one under which the difference between the maximum number and the minimum integer is the smallest.

124C - Prime Permutation

We divide the positions into the following sets. A2 = (2, 4, 6, ..., 2m1), A3 = (3, 6, 9, ..., 3m2), A5 = (5, 10, 15, ..., 5m3),...

One can see that for any prime integer p > 2, Ap always has at least one common position with A2, as long as the index 2p does not exceed the range. Thus, we find out the maximum such prime integer p', and then count the total number of different positions belonging to sets A2, A3, ...Ap'. These positions must have the same letters, while the other positions can have any letter. Therefore, the left work is to determine whether we have enough number of the same letter.

124D - Squares

We first focus on the first condition and consider y = 0. One can see that the bad points are distributed on the X-axis with distance 2a. After increasing y to 1, 2, ... + ∞ , one can find that the bad points form multiple lines with  - 45 degrees. Similarly, the second condition results in multiple lines with  + 45 degrees.

As a result, the bad points have divided the whole plane into infinite grids. To get from the starting point to the ending point, we have to cross several (maybe zero) grids. The answer is just the least number of grids that we have to cross. In fact, this is quite similar to the Manhattan Distance. We consider the lines with  + 45 and  - 45 degrees as the “X” and “Y” axis, respectively. Then, we can calculate the manhattan distances of the two points, along the “X” and “Y” axis, as Dx and Dy. The answer is max(Dx, Dy).

124E - Brackets

I read the tutorials and I think the ideas behind this problem is really very amazing. It needs quite strong insight to reduce the problem to single dimension, which is not that straightforward, at least for me. I think I should work harder to improve my insight.

•
• +6
•

By pleasurepain, 5 weeks ago, ,

122A - Lucky Division

Generate all the divisors and check whether at least one of them is a lucky number or not.

122B - Lucky Substring

This is an implementation problem. As the length of the string is quite small, every step can be trivially implemented, without any worrying of TLE.

122C - Lucky Sum

Instead of directly computing each next[i], we previously find out all the lucky numbers, and equivalently enumerate the lucky numbers. The total number of lucky integers that are less than 109 is about 1024, and we can use bitmask to generate all of them. Nevertheless, we still need one more lucky integer, i.e., 4444444444, which is the value of next[i] for all i > 777777776. It is obvious that for any integer i between two lucky integers, next[i] is always equal to the second lucky imteger. Therefore, we can calculate how many integers belong to the interval of two neighboring lucky integers, and update the answer.

122D - Lucky Transformation

Let us see what happens when we meet the first “47”. If it is changed into “44”, then we can move on to find the next “47”. If it is changed into “77”, then we should check the digit before this “77”. If it is not “4”, then we can move on again; otherwise we have “477” now. It can be seen that we will get stuck into a loop, i.e., we should change “477” into “447” while later change it back into “477” again. For this case, the final result depends on whether the number of operations is odd or even.

122E - Lucky Permutation

To find the k-th lexicographic small permutation, it is sufficient to consider the last 13 digits, since 13! > 109. Then, the main issue is to find out the k-th lexicographic small permutation. There is a standard algorithm to solve this problem, referred to as Cantor Expansion, and one can search a lot of information and materials on the Internet.

•
• -7
•

By pleasurepain, 6 weeks ago, ,

119A - Epic Game

The solution is straightforward. We iterate between a and b to compute the GCD with n. Then, we decrease n with the corresponding value until n is reduced to zero, which also determines the winner.

119B - Before Exam

We keep calculating the average points of each provided combination, and updating the maximum and minimum values. Then, for the left theorems, we check whether we can still select some of them to form a new eaxm (perhaps this is the main tricky issue). If yes, we update the maximum and minimum values again.

119C - Education Reform

We use dp[n][m][w] to denote the maximum total value, under the condition that the n-th day is assigned with the m-th task while the the m-th task has points node[m].a + w. We use node[i] as a struct that has node[i].a, node[i].b and node[i].c as its elements, which have the same meanings as the problem mentions.

The updating of dp[n][m][w] is a little different from what I have known before. For instance, to compute some dp function f[n], we usually deduce its relationship with f[i] for i < n, and update f[n] from small indices to large indices. Once we “visit” f[n] for the first time, its value is determined, and will never be changed.

However, for this dp function, we start from some dp[n][m][w] and visit next potential states, perhaps with several times, and keep updating their values until they will never be visited any more. Specifically, from dp[n][m][w], we can move to dp[n + 1][m + i][w'], which means that for the n + 1-th day, we can select any one of the m + i-th task (i > 0) that have points node[m + i].a + w'. Note that some of the states perhaps can not be reached, since it requires that the next point xi must be either xi + 1 + k or xi + 1 × k, while xi should also be included in the given interval.

Generally speaking, from each determined state, we move to its next potential states and keep updating their values. At the same time, we record the transition between every two neighboring states.

By pleasurepain, 6 weeks ago, ,

This problem can be solved by the following three steps. Firstly, change all the letters into lower case ones. Secondly, remove all the required letters. Thirdly, add “.” in front of each survived letter.

118B - Present from Lena

Take care of the number of spaces that should be output before each digit.

118C - Fancy Number

We can enumerate all the digits, and for each digit d, we replace several original digits so that there exist at least k digits which are the same. To achieve the minimum cost and also the minimum lexicographic order, we should replace digits in the order of d (this can be viewed as a trivial case), d + 1, d - 1, d + 2, d - 2, and so on. The replacement should be stopped once we have obtained k same digits.

To simplify the implementation, for each digit, we can also record how many of them should be replaced. Finally, we implement the replacment. However, here we should be very careful. Suppose that the original digit t is replaced with d. If t < d, then we should replace digit t from right to left; otherwise we should do it from left to right, so that we can achieve the minimum lexicographic order.

118D - Caesar's Legions

The solution is DP. Let us use a[n][m][e] to denote the number of all the feasible patterns that have e type-1 people standing at the end of the line one after another, while the total number of type-1 and type-2 people are n and m, respectively. Similarly, we use b[n][m][f] to denote the total number of feasible patterns that have f type-2 people standing at the end of the line.

The recursive formula is as follows:

The initialization should be done as follows:

a[0][m][m] = 1, for all m < k2

a[n][0][n] = 1, for all n < k1

We can start from any node, and implement DFS. During this process, when we are visiting a node a and enumerating its “child” (since this may not be its true child node) node b, if b is still not visited, we add a directed edge from a to b. If b has been visited but its “child” nodes are still not fully visited, then we add a directed edge from a to b as well. If b has been visited and all of its “child” nodes have also been visited, then we do nothing, since this edge must have been assigned with a “direction”.

After the above operations, we in fact have established a directed graph. Then, we check whether it is strongly connected or not, which can be done by inversing all the direction of the edges and implement DFS again.

The last step is to prove that if the above obtained directed graph is not strongly connected, then it is impossible to construct any strongly connected directed graph. Well, I did not figure out a strict proof. But from an intuitive understanding, if the constructed directed graph is not strongly connected, it implies that there is at least one bridge edge, and thus it is impossible to establish any strongly connected graph.

•
• -8
•

By pleasurepain, 6 weeks ago, ,

117A - Elevator

At first, note that it takes 2m - 2 minutes for the elevator to go up from the first floor to the top and return back, and we refer to this event as a “cycle”. Thus, for each query, we can compute the floor on which the elevator stops at time ti.

Now, the left work should be done very carefully. For instance, we should determine whether we can catch the elevator within the current cycle, or we have to wait for another cycle. Moreover, after we get into the elevator, we should determine whether we can reach the target floor within the current cycle, or wait for more one cycle.

117B - Very Interesting Game

If we denote the first and second integer as x and y, then the integer after concatenation can be represented as x × 109 + y.

Thus, we should check whether 109x%mod = (mod - y)%mod could hold or not. It is obvious that if b ≥ mod - 1, then the above equation can always be satisfied, since (mod - y)%mod can take any value from {0, 1, 2, ..., mod - 1}. If b < mod - 1, then (mod - y)%mod can only take values of {0, mod - 1, mod - 2, ...mod - b}. Therefore, we can enumerate x from 1 to mod - 1, and find the first (also the minimum) integer that can satisfy the equation. Note that it is not necessary to test any x that is larger than mod - 1.

117C - Cycle

If there is no cycle, then it is obvious that no cycles of length 3 exist. On the other hand, there must be at least one cycle of length 3.

We denote the cycle as a1, a2, ..., an, and check a1, ai, ai + 1, where i is initialized with 2, and increased to n - 1. As this is a cycle, there is an edge from a1 to ai, and also en edge from ai to ai + 1. We obtain a length-3 cycle if there is an edge from ai + 1 to a1. However, if this edge is from a1 to ai + 1, then we increase i to i + 1, and check the next three nodes. This construction will always find out a tuple that achieves our target, since this is a cycle, and there must exist at least one node that has an edge directed to a1.

•
• +1
•

By pleasurepain, 7 weeks ago, ,

116A - Tram

The solution is straightforward. It is sufficient to record the number of people in the tram, and find out the maximum value.

116B - Little Pigs and Wolves

This turns out to be a simple problem if one has noticed that there exists at most one wolf around any pig. Thus, it is not necessary to consider the case where some single pig can be eaten by multiple wolves. We can enumerate each wolf and check whether there is at least one pig around it.

116C - Party

We can find that there are multiple connected components, and then implement DFS or BFS to each component, starting from the node which does not have any superior nodes, to calculate the maximum depth. This is just the required answer.

116D - Lawnmower

Note that once we move to the lower floor, we can never return back. Thus, we must clean up all the weeds on the current floor, and then move downstairs.

For each floor, we denote the positions of the leftmost weed and the rightmost weed as pl and pr, respectively. Then, suppose that we reach the current floor at some position p. No matter which direction we are facing to, the minimum distance that we need to move is either |p - pl| or |p - pr|, and finally we stay at either pl or pr. Now, we find the next floor that has at least one weed (note that there might be several floors without any weeds during our moving).

After finding the next floor, we can find that we should move from the previous position to the leftmost weed or rightmost weed in “horizonal” direction, according to whether we face to the same direction or not. The above calculation resembles the Manhattan Distance, whose horizational distance and vertical distance can be independently computed.

116E - Plumber

Well, I think this is really a brain-storm problem. When I finally understand the tutorials, I feel that I have seen a new world...

Let us first consider that we have 1 × m empty cells. If we only focus on the horizonal pipelines, it can be seen that the pattern can only be either “LRLRLRLRL...” or “RLRLRLRLRL...”, where “R” means that the pipeline is connected to the right side while “L” means that the pipeline is connected to the left side. For the vertical pipelines, we have 2m patterns, since they will never lead to “leaking” states.

Now, we extend the above case to 2 × m empty cells. Based on similar arguments, for the horizonal pipelines, we have 22 feasible patterns since we have two rows. For the vertical pipelines, one can check that for each column we always have “UD” and “DU”, two patterns, where “U” and “D” denote that the pipeline is connected to the upper and bottom side, respectively.

In general, with n × m empty cells, the answer is 2(m + n). If there are several cells that are not empty, then the patterns of the row and column to which these cells belong in fact have been determined. Suppose that the number of rows and columns that are fully empty is totally t, and then the answer will be 2t. Note that the previously filled cells might have already led to “leaking” states, and thus for this case the answer should be zero.

•
• -4
•

By pleasurepain, 2 months ago, ,

114A - Cifera

We keep dividing l by k until l is not a multiple of k any more, and then check whether l is reduced to 1 or not.

114B - PFAST Inc.

As n is limited up to 16, we can use bitmask to enumerate all the feasible combinations and check whether they can form a group or not. The total complexity is O(2n × n2).

114C - Grammar Lessons

This is a straightforward implementation problem. For each given string, we need to check the following conditions.

1) all the words end with the required suffix

2) all the words have the same gender

3) all the words appear in the required order

4) there is exactly one noun word

114D - Petr#

The idea is to previously calculate all the positions of the required prefix and suffix. Then, we enumerate every pair of feasible combination, and find out all the different substrings.

Therefore, the main task is how to determine whether two strings are the same or not. I did not come up with a good solution, however I studied the other accepted codes.

I found that they adopt an “unsigned long long int” variable x, initialized with zero value, and compute x = x × prime + s[i], where prime is a prime integer. I think this means to transform or map the string to an integer, like hash table. However, I did not figure out how could this guarantee that no two strings are mapped to the same integer, since we have at most 262000 different strings but only 264 integers. Although for some substring of length m, we can in fact only have O(n) different ones, which is quite small compared with 264, but this still can not guarantee that no collisions occur...

114E - Double Happiness

There is a standard solution, referred to as “sieve function”, to this problem. Using “bitset” can also solve the memory problem. Instead of testing each prime integer, we can enumerate a and b, and then test whether the result of a2 + b2 is prime or not. The complexity is O(ab) = O(n). To further decrease the constant of complexity, for each value of a, we can start enumerating the value of b from a + 1, with increment step of 2. The reason is that if both a and b are even or odd, the value of a2 + b2 must be an even integer, and thus is definitely not a prime integer.

•
• -3
•

By pleasurepain, 2 months ago, ,

112A - Petya and Strings

First change all the letters into lower case ones, and then compare the two strings as the problem requires.

112B - Petya and Square

To cut the whole board into two symmetric parts, the cutting line must pass through the central point. Therefore, the following four squares can not be special cells, i.e., (n, n + 1), (n, n), (n + 1, n), (n + 1, n + 1), where (r, c) denotes the r-th row and the c-th column.

112C - Petya and Inequiations

I did not figure out how to prove this, however it turns out that the following solution can pass all the tests.

At first, note that if can satisfy the requirement, then can satisfy as well. Thus, we set a1 = a2 = ...an - 1 = 1 and an = y - n + 1, which gives the maximum value of . Moreover, if y < n, then the answer is definitely “-1”; otherwise we divide y as mentioned above and check the result is no less than x or not.

112D - Petya and Divisors

For each integer n, it takes complexity to obtain all its divisors. For each divisor, we should check whether it is divisible by any one of the previous y integers. Thus, we can use an array idx[n] to record the maximum index of the given integer that has n as its divisor. When we deal with the current i-th query, we find out each of its divisor x, and check idx[x] to determine whether this divisor satisfies the requirement or not. Next, we update idx[x] = i, since x is divisible by the i-th integer.

•
• -9
•

By pleasurepain, 2 months ago, ,

110A - Nearly Lucky Number

We can read in the integer as a string, and count the total number of '4' and '7'. As the length of string is at most 18, it is sufficient to check whether the total number is 4 or 7.

110B - Lucky String

One can find that the optimal sequence should have pattern 'abcdabcdabcd...', and thus we can just output the first n letters.

110C - Lucky Sum of Digits

Suppose that the minimum integer has x 4s and y 7s. Then, we have 4x + 7y = n. To construct the minimum integer, we must have x + y as small as possible. If there are multiple such pairs, we should further find the one with the maximum x, which must be unique. After obtaining the optimal (x, y), the minimum integer have a form of 444...777..77.

110D - Lucky Probability

At first, we find out all the lucky integers and sort them in an increasing order. These lucky numbers in fact have divided the interval [1, 1E + 9] into several sub-intervals, whose borders are just these lucky numbers. Suppose that we have m intervals [a0, a1], [a1, a2], ..., [am - 1, am], where a0 = 1, a1 = 4, a2 = 7, a3 = 44, ...am = 1E + 9. For any interval [x, y] that contains exactly k lucky numbers, we must have and . Therefore, it suffices to count the number of pairs (x, y) that satisfy the above condition. Equivalently, we can enumerate all the feasible intervals, i.e., [ai, ai + 1] and [ai + k, ai + k + 1], and find out the number of common integers that also appear in [pl, pr] and [vl, vr].

Moreover, one should take care of one tricky case, i.e., k = 1. As one can see, when k = 1, [ai, ai + 1] and [ai + k, ai + k + 1] have a common integer ai + 1, which implies that ai + 1 has been counted twice if it belongs to both [pl, pr] and [vl, vr]. Therefore, one should decrease the counting result by one if this case occurs.

110E - Lucky Tree

As this is a tree, deleting any edges will divide it into several independent smaller trees. We can first delete all the edges that have a weight of lucky number and then adopt “union and find” to construct the smaller connected components.

We use ai to denote the number of nodes belonging to the i-th component. Now, instead of counting the required answer, we count the number of triples that do not satisfy the requirements. Note that if we pick all the three nodes from the i-th component, they definitely are against the requirements. This case gives , where all ai ≥ 3. Next, if we pick two nodes from the i-th component while one node from another different component, this gives , where ai ≥ 2. Finally, the desired result is n(n - 1)(n - 2) - n1 - n2.

109D - Lucky Sorting

If the given sequence is not initially non-decreasing, we need at least one lucky number.

We denote the original sequence and the sorted sequence as a and b, respectively. For each element in a, it appears in b at a unique position. There are exactly n such pairs, and thus we can adopt two arrays to record their relationship. We use atob[i] to denote that the i-th element in a is at position atob[i] in b, while using btoa[i] to denote that the i-th element in b is at position btoa[i] in a. Then, we enumerate each element in array b, and try to move the “required” element to the current position.

If i = btoa[i], it is not necessary to move any element. On the contrary, we should move the btoa[i]-th element to the i-th position. If either one of a[i] or a[btoa[i]] is a lucky number, it takes one “move” to exchange their positions. Otherwise, we can first exchange a[i] with a lucky number at position j, and then move a[btoa[i]] to the i-th position, which costs two “moves”.

From the above operations, one can check that it is always feasible to sort the original array in a non-decreasing order within 2n “moves as long as there is at least one lucky number. Note that whenever we exchange two elements, both atob and btoa should be updated at the same time.

•
• +3
•

By pleasurepain, 2 months ago, ,

108A - Palindromic Times

Note that for each hour, there either exists a unique answer or no answer. For instance, at hour 14, the answer is 14: 41 while for hour 17, no answer exists.

Therefore, we can first check for the given hour whether there is a feasible answer or not. If no, then we continue to search for the next hour that has such an answer.

108B - Datatypes

We should first sort the array in an increasing order. Then, for every pair of (ai, ai + 1) with ai < ai + 1, we check whether there exists such an integer x.

The maximum x that can be represented by ai bits is 2ai - 1. Thus, x2 = 22ai - 2ai + 1 + 1. One can check that x2 can always be represented by ai + 1 bits as long as ai + 1 ≥ 2ai.

108C - Dorm Water Supply

According to the description of the problem, the graph in fact consists of several simple rings and single links. Thus, we start enumerating from node 1 to node n and for each node that has no input pipe, we visit all the nodes along the pipes while recording the minimum diameter. Finally, print out the recorded results.

We denote the number of his teammates as A and the number of the other students as S. Then, the problem can be solved based on the following three cases.

1) A + S < n - 1: this means that there are not enough students;

2) S < n - 1: this means that the probability is absolutely one;

3) none of the above cases: the answer is just . To compute , I usually transform it into F = elog(F). In other words, we first calculate , and then obtain F = ef. I think “log” can guarantee better precision than directly mutiplying all the float numbers together.

•
• -7
•

By pleasurepain, 2 months ago, ,

106A - Card Game

As the problem requires, we first check the suits of the given two cards. If they have the same suit, then we compare their ranks; otherwise we check whether the first card is the the trump card or not.

106B - Choosing Laptop

We can adopt a double loop to eliminate all the outdated laptops. Next, we find the cheapest one as the answer.

106C - Buns

At first, I tried to solve it based on greedy algorithm. However, it turns out that such a greedy algorithm fails since all the involved numbers are integers...

Well, this is essentially a backpack problem, if we implement some equivalent transformation. More specifically, it is a multiple-backpack problem, one can also check the one in 95E - Lucky Country, which is also solved based on multiple-backpack.

106D - Treasure Island

The solution is straightforward implementation. However, trivial implementation ends up with TLE. To avoid this, for each position, we should calculate in previous the farthest position that we can reach when we move to any one of the four directions. This can be computed by using DP algorithm with complexity O(mn).

•
• -5
•

By pleasurepain, 3 months ago, ,

105A - Transmigration

It seems that the difficulty of this problem mainly lies in the precision. Suppose that we are given an integer F and a float number L, and asked to compute the value of F × L. One can implement the above calculation based on float numbers, however this might lead to some weird precision problem. Instead, as for this specific problem, one can write L in the fractional form of , where both A and B are integers, and A can be obtained by extracting from the given input while B = 100. With this transformation, F × L can be equivalently calculated as F * A / B, where “/” denotes the “integer division”.

105B - Dark Assembly

We use DFS to generate all the feasible patterns of distributing candies. For each configuration, we calculate the probability of winning by enumerating all the possible results of voting. The results of voting can be represented based on bitmasks. For instance, 0011 denotes that the first two people give positive voting while the other two give negative voting.

By pleasurepain, 3 months ago, ,

104A - Blackjack

Determine the result based on each value of n carefully.

104B - Testing Pants for Sadness

We use a[1], a[2], ..., a[n] to denote the given n values. To achieve the maximum number of clicks, it is obvious that we should first choose a[i] - 1 wrong answers and then select the correct one, for every i. For a[i], we have a[i] - 1 wrong answers, and thus we start from 1 to i - 1 for a[i] - 1 times, which gives (a[i] - 1) × (i - 1) clicks. Also remember that i contributes a[i] clicks, and this gives totally (a[i] - 1) × (i - 1) + a[i] clicks before we move to index i + 1. Therefore, we enumerate all the elements, and add the answers together.

104C - Cthulhu

Let us consider what form can such a graph have. There are n nodes and only one circle. This implies that we must have n edges as well, i.e., m = n. Next, after deleting some single edge, we will surely obtain a connected tree. Therefore, we can adopt a double loop to check if we can obtain a connected tree by eliminating some edge. The connectivity can be simply checked by using Union-Find.

I also find that it is sufficient to just check whether the original graph is connected or not, which can reduce the double loop to a single loop.

104D - Russian Roulette

We first consider the case where n is an even integer, and there is only one bullet. It can be seen that all the positions can be divided into two types, even indices and odd indices. The probability of winning is always 0.5 no matter at which type we put the bullet. Now suppose that we have two bullets. One can check that if both two bullets are put at the same type, the winning probability is still 0.5; otherwise, the winning probability is decreased. Thus, we should put the two bullets at the same type. Extending this to a general approach, we should put bullets at the even indices until all the even indices have been used up, and then put them at the odd indices. To achieve the minimum lexicographical order, we should implement the above operations from right to left.

Now we deal with the case where n is an odd integer. For one bullet, we can put it at any position, which always gives a winning probability of . When there are two bullets, the second one should be put at a position with even index so that the winning probability is not decreased. For more bullets, the strategy is similar as the case where n is even. In a word, when n is an odd integer, we should put the first bullet at position n. Then, we put the other bullets at positions n - 1, n - 3, n - 5, ..., 4, 2, n - 2, n - 4, ..., 5, 3, 1.

104E - Time to Raid Cowavans

This is a very very tricky problem.

If we answer the query by exhaustive calculation, the complexity is O(qN). However, note that if all queries have , the complexity is reduced to . On the other hand, if all the queries have , we can previously use DP algorithm to compute the results for all the potential values of b, resulting in a complexity of .

Based on the above observations, we can select one of the two algorithms according to the value of b. We sort the queries in the increasing order of b. For , we use DP algorithm with complexity O(N) to calculate the desired result; otherwise we directly compute the sum. The former operation may be implemented for at most times, which gives complexity while the latter one might be implemented for at most times, which gives complexity . Therefore, the total complexity has been reduced to .

By pleasurepain, 3 months ago, ,

102A - Clothes

We can adopt a triple loop to enumerate all the reasonable combination, and find out the one with the minimum cost.

102B - Sum of Digits

A simple implementation problem. Keep adding all the digits to obtain a new integer, and repeat again until it is reduced to an integer with only one digit.

102C - Homework

At first, we count the number that each letter has appeared in the string. To eliminate the number of different letters as many as possible, it is straightforward to first delete the letter with the minimum number, and then the one with the second minimum number, and then the one with the third minimum number, and so on.

102D - Buses

Although n can be as large as 109, the value of m in fact has determined that at most 2m of the nodes (stops) really affect the result, since the person can only get off the bus at these specified stops.

Thus, we should first compress the number of nodes (or stops) to the order of O(m), which can be achieved by using 'map' of STL in C++. Now we use dp1[k] to denote the number of different ways to get to node k. Furthermore, we maintain a prefix-sum array dp2[k] which have values . For a route from node i to node j, we can calculate . Therefore, to compute any dp1[k], we should find all the routes that can reach node k, and add them together as shown above. Besides, the calculation of dp1[k] should be implemented in an increasing order of k, and do not forget updating dp2[k] = dp2[k - 1] + dp1[k].

It is convenient to denote a point P with coordinate (x, y) as P = x + iy, where the complex form is introduced. Suppose that we have implemented several operations, and whatever the order of the two given operations are, they can always be described as repeating the following steps cyclically: first add vector C to vector A for m times, and then rotate the resulted vector for k times (both m and k can have zero values).

Thus, after the first cycle, A becomes (A + m1C)ik1 = Aik1 + m1Cik1. After the second cycle, it turns out to be Aik1 + k2 + m1Cik1 + k2 + m2Cik2. Note that ik can only have a form of i or 1. Thus, after several cycles, the resulted vector must have a form of Aik + aC + biC, which should be equal to B. This equation is satisfied if and only if both real and image parts are equal, respectively.

Look out for the case where C is a zero vector.

101D - Castle

The main solution consists of two steps.

Step 1. Implement DFS from the root node 1, and during this process, we should compute several variables.

childnode[n]: the number of child nodes that node n has;

total_t[n]: the time consumed to visit all the child nodes of node n while finally returning back to node n;

Step 2. Implement BFS to calculate the required answer. However the order of visiting next nodes should be carefully optimized, which is more complicated than I thought... One can check the tutorials in http://codeforces.com/blog/entry/2393, and the necessary variables to determine the visiting order has been obtained in the DFS step.

•
• +3
•

By pleasurepain, 3 months ago, ,

99A - Help Far Away Kingdom

Using C++, there is a simple manner to implement string parsing. For this problem, we can replace '.' with space, and initialize an 'istringstream' type with this modified string. Then, we define two string variables, and initialize them with 'istringstream' as a standard input. The next work is to find the last digit of the first string and the first digit of the second string, and output the answer according to the requirement.

99B - Help Chef Gerasim

Take care of two special cases n = 1, 2. For n ≥ 3, we can find out the maximum and minimum values, denoted as min and max, respectively. Besides, we should find out all the other values that are neither min nor max. If such value is unique, and equal to , the current configuration can be recovered.

99C - Help Victoria the Wise

The complete permutation has 6! = 720 patterns. Therefore, we can compare every one with all the other ones to check whether it results in a unique pattern or not. Now we should figure out how to determine that two patterns are equivalent after some rotation.

As an efficient manner, we can mark the six planes with front, back, up, down, left and right. Then, we fix one plane as the top, and rotate 0, 90, 180, 270 degrees to obtain four equivalent patterns. As there are 6 planes to serve as the top, the total number of equivalent patterns are 6 × 4 = 24.

•
• +3
•

By pleasurepain, 3 months ago, ,

96A - Football

Count the maximum length of repeated elements, and compare it with 7.

We store the integer as a string and use L to denote its length. At first, note that if L is an odd number, the answer should be 44...477...7 with 4s and 7s. If L is an even number, we can first compare it with 77...744...4. If the former one is larger, the answer must be 44...477...7 but here both the number of 4 s and 7 s are ; otherwise, it implies that we can always find a required integer with the same length L.

This minimum answer can be found by using DFS (it seems that DFS is an incredibly powerful technique...). The DFS works as follows.

We use s[pos] to denote the digit that we are dealing with at position pos, and use num4 and num7 to denote the number of 4s and 7s that are still not assigned. Initially, .

At first, if num4 > 0, we try to assign 4. If s[pos] < '4', it is obvious that we can safely assign 4 and the final answer is thus straightforward. If s[pos] =  = '4', then we should call DFS again to deal with position pos + 1 with num4 = num4 - 1. If s[pos] = '5', or'6', then we assign 7, and the answer has been determined. If s[pos] =  = '7', then we call DFS to deal with pos + 1 with num7 = num7 - 1. If s[pos] > '7', we should return 'false'.

96C - Hockey

As the strings have small length, we can adopt exhaustive search to find all the positions that should be replaced. We use T to denote the given letter. For each position, if it is not equal to T, we should replace it with T in order to achieve the maximum number of T; otherwise we should further check whether T is 'a' or not. If yes, then we replace it with 'b', and if no, we replace it with 'a'. Be careful that the lower case or upper case should stay the same.

96E - Horse Races

This is a sparse graph, and thus we can implement Dijkstra algorithm based on priority queue with complexity O(ElogE), where E is the number of edges.

With the above arguments, we can implement Dijkstra to every node, and find out all the nodes that it can reach. Then, we can build another new graph with the given cost, and it is sufficient to implement Dijkstra algorithm again to find out the shortest distance between the given starting point and ending point.

95E - Lucky Country

It turns out that this problem has a standard solution. At first, we adopt Union-Find technique to calculate the number of components and also the corresponding sizes. Then, the problem is reduced to a well-known, perhaps referred to as "Multiple-Pack" problem, and one can search a lot of information on the Internet.