pleasurepain's blog

By pleasurepain, 29 hours ago, In English,

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 .

Read more »

 
 
 
 

By pleasurepain, 5 days ago, In English,

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].

102E - Vectors

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By pleasurepain, 8 days ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By pleasurepain, 12 days ago, In English,

96A - Football

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

96B - Lucky Numbers (easy) 95B - Lucky Numbers

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.

Read more »

 
 
 
 

By pleasurepain, 2 weeks ago, In English,

94A - Restoring Password

A simple problem with straightforward solution. Divide the given string into 8 parts with the same length 10, and convert each of them to a decimal digit according to the provided mapping relationship.

94B - Friends

Generate all the feasible C53 patterns, and check whether there exist any three people that are either known or unknown to each other. The mutual relationship can be represented by the connectivity of graph.

94C - Frames

This is a horrible problem...There are a huge number of cases that should be considered. One of the cases that is likely to be ignored is shown as follows:

Suppose that m = 4, n = 100, and a = 3, b = 10. One might give 3 as the answer. However the answer should be 2, since we can first select 3, 4, 7, 8, and then select 5, 6, 9, 10.

94D - End of Exams

It turns out that greedy algorithm solves this problem. Assume that we have n segment lines with the same length w, and we put them one after another, i.e., the i-th one starts from the end of the previous one. Next, we have another m segment lines with the same length , and also put them in the same manner as mentioned above.

For each segment line with length w, we check whether it contains more than two segment lines with length . If yes, the answer is NO; otherwise we can further calculate the “contents” in each cup by checking what are included in each of the m segment lines.

Note that if we use “float” types, we may fail obtaining sufficiently precise results, especially under some weird cases. The best choice is to replace all the division with an equivalent multiplication.

94E - Azembler

At first, I consider using DP to solve this problem. For instance, we can use dp[n] to denote the minimum number of operations to obtain the integer n. We can find out all pairs of (i, j) and coefficients k = 1, 2, 4, 8 so that n = i + k × j holds and dp[n] = dp[i] + dp[j] + 1. However, this fails since dp[i] and dp[j] are dependent under some cases. For instance n = 138, and the optimal decomposition is 138 = 2 + 8 × 17 and 17 = 1 + 8 × 2. Here dp[17] = 2 and dp[2] = 1, and thus dp[138] = 4. However the optimal answer should be 3 since after we obtain 2, the number of operations to obtain 17 is reduced to 1 instead of 2.

It turns out that this problem can be solved by using DFS with powerful branch and bound tricks. In detail, we just keep generating values by using the values that have already been calculated, and assign them to the registers that have not been consumed. When all the registers have been used or we have got the target value n, the call of DFS function should be terminated immediately to significantly reduce the comlexity.

93E - Lostborn

At first we derive the recursive formula. We use f(a1, a2, ..., ak)[n] to denote the target value. Suppose that we have obtained f(a2, ..., ak)[n], and to calculate the target value, we should further delete the integers which are divisible by a1. These integers have form q × a1, but q is not divisible by any a2, a3, ..., ak, since we have chosen them in such a manner. Moreover, holds, and thus f(a1, a2, ..., ak)[n] = f(a2, ..., ak)[n] - f(a2, ..., ak)[n / a1], where “/” denotes the integer division.

With the above formula, we can compute the result based on DFS. For small n, we can calculate f(a1, a2, ..., ak)[n] in previous to reduce the search complexity. Furthermore, we can sort (a1, a2, ..., ak) in a decreasing order in order to decrease “n” as fast as possible, for each call of DFS.

Read more »

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it  

By pleasurepain, 3 weeks ago, In English,

92A - Chips

It can be observed that n people will consume elements. Thus, we should first compute the remainder m%N, and then find out the maximum i so that . The answer is .

92B - Binary Number

This is a simulation problem. We start from the end of the binary sequence, and enumerate the digit one by one. If we meet a “0”, then do nothing; otherwise we simulate the binary addition of adding “1” to the current position. When the sequence reduces to a single “1”, the number of total operations is just the answer.

92C - Newspaper Headline

To construct the second string while using the the minimum number of the first string, we can adopt the greedy algorithm.

Specifically, we maintain a variable S, which is set to  - 1 initially. For any letter appearing in the second string, we should find the same letter in the first string with the smallest index i satisfying i > S. Then, we update S = i. When we can not find the required i, it implies that we have to start from the beginning of the first string again, which will set S =  - 1. This also means that the number of the first string should be added by one.

To implement the above algorithm, we can store the positions of each letter in previous, in an increasing order. Thus, we can use binary search to find out the smallest index i satisfying i > S.

92D - Queue

This is a classic “inversal pair” problem, but asking to find out the farthest “inversal pair”.

The basic idea is using suffix, specifically, suffix minimum index. For the original array a[n], we use b[n] to denote its suffix minimum index, i.e., b[i] gives the index from i to n - 1 so that a[b[i]] is the minimum value among a[i], a[i + 1], a[i + 2], ..., a[n - 1]. Furthermore, as there may exist duplicate values, b[i] should be the maximum index if there are several equal minimum values.

Next, to find the farthest inversal pair of a[i], we can implement binary search among b[i], b[i + 1], ..., b[n - 1] and find out the largest b[j] so that a[i] > a[b[j]] holds. The binary can succeed since b[i] is a nondecreasing sequence.

92E - Ski Base

Well, I can only come up with a “not so strict” proof...

We adopt a variable a with initial value equal to 1. Whenever we find that the currently added edge belongs to a connected component, we multiply a by 2 (remember to calculate the modulo), and output the answer a - 1.

To prove the correctness of the above formula, we divide all the edges into two types S and T, with the former one containing the edges that do not belong to any components while the latter one containing the edges belonging to some component. If we remove all the edges from T, then the graph reduces to several unconnected components, and thus no ski base can be built. As we add edges from T, the graph “begins” to contain at least one component. As we have 2|T| ways to choose edges from T, we can have 2|T| - 1 ski bases. The term “-1” comes from the empty case, where no edges from T are selected, since this leads to no ski base.

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By pleasurepain, 3 weeks ago, In English,

90A - Cableway

There are at most 300 students, and thus we can directly simulate the whole process, i.e., what happens in each minute. The simulation terminates when no students are left.

90B - African Crossword

The implementation is straightforward. We can enumerate each letter, and only those that appear exactly once in the corresponding row and column should be output.

90C - Robbery

An interesting problem.

Suppose that Δ x elements are taken away. To guarantee that the n - 1 sums keep the same, the changing quantity for each element must be  - Δ x, Δ x,  - Δ x, Δ x, .... Therefore, if n is an even number, it is impossible to take away any elements, since the total sum can not be changed. For an odd number n, it can be seen that to take away Δ x elements, we have to carry out moves. For each minute, at most m moves can be conducted, and thus . Given k minutes, we can carry out at most moves. However, the value m = min(a[1], a[3], ...a[2n + 1]) has provided an upper bound (the index starts from 1), and thus the answer should be min(T, m).

90D - Widget Library

The description is long but it turns out to be a traversal on a q-ary tree, which can be solved by using DFS. One important trick is to store the results that have been obtained at each node to avoid TLE.

90E - Chip Play

The trick is how to find out the next position with constant complexity so that the total complexity is (n × m × n × m). For each position with an arrow, we assign four links to denote the nearest four positions with arrows that it can reach, in left, right, up and down directions, respectively. This process can be completed with complexity O(n × m), by using the prefix and suffix idea.

When we move from the current position to the next one, we should update the links assigned to the four nearest arrows as well, since after moving, the current arrow will disappear. Suppose that the current position is P, and its four links are P[L], P[R], P[U], P[D], denoting that the nearest left, right, up and down arrows. When P disappears, the nearest right arrow of P[L] should be P[R], and the nearest left arrow of P[R] is P[L], and the nearest upside arrow of P[D] is P[U], and the nearest downside arrow of P[U] is P[D].

After the above updating, we can always find out the next arrow with constant complexity. Remember to restore the initial links after every time we complete DFS.

Read more »

 
 
 
 

By pleasurepain, 4 weeks ago, In English,

88A - Chord

Given three elements, we can generate all the 6 permutations, and calculate the distance to check which type it belongs to. Note that the distance might be a negative integer and when this occurs, add 12 to convert it to a positive one.

88B - Keyboard

When given an uppercase letter, the basic idea is to enumerate the distance of all the feasible combinations of “Shift” and the corresponding lowercase letter, and check whether there exists any one that satisfies the requirement. However, if we implement the computayion every time the query comes, it may lead to TLE. As there are at most 26 uppercase letters, we can first calculate the distance for each one, and store the results. When a query comes, just take out the corresponding result.

88C - Trains

This problem can be solved by direct simulation. Suppose that a < b, and one can see that after time , the two trains meet each other again, and thus it is sufficient to focus only on this time interval.

We implement the simulation based on the length of b, i.e., we first consider the time interval [0, b], then [b, 2b], [2b, 3b], and so on. There are exactly such intervals. Next, we store and update the starting time of train-a in each interval of length b, and calculate the number of interval of length a that is included. This total length is just the time that train-a will be selected, while the left length belongs to train-b.

The total complexity is about O(max(a, b)).

88D - Vasya and Types

This problem can be solved by straightforward implementation. The key point is to store the number of “*” and “&” for each type and do not forget the case where the type reduces to “errtype”.

88E - Interesting Game

This is a famous game theory problem, referred to as Sprague-Grundy Theorem. One can check the book written by the great master Competitive Programmer's Handbook — a new book on competitive programming for more details.

Read more »

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By pleasurepain, 4 weeks ago, In English,

84A - Toy Army

The strict proof seems to be a little complicated as far as I consider, however an intuitive understanding suggests that the answer is n + n / 2, and it is accpeted...

84B - Magical Array

We must find out all the intervals that consist of the same integers. For an interval with P integers, the number of reasonable subsequences is . Thus, we can adopt two pointers to find out all the target intervals, and calculate the answer.

84C - Biathlon

As it has been guaranteed that no two circles intersect with each other, the given point can only fall into at most one particular circle (one special case is that two circles touch each other at the given point). Thus, we first sort the circles in an increasing order of their X-coordinates, and find out two circles between which the give point falls (check the X-coordinate of the given point as well, and a special case is that the given point falls at one of two ends of all the circles), which can be achieved by using binary search.

Then, the final step is to check which circle it falls inside, or completely outside all the circles.

84D - Doctor

The basic idea is still binary search. We use a[n] to denote the given array. We use binary search to find out the maximum T so that . Moreover, we compute K - S as the remainder. Then, any a[i] that is not larger than T should be firstly eliminated. Next we enumerate the first K - S survived a[j] in the natural order while decreasing them by one, and eliminate those a[i] ≤ T again. Finally, we start from the current position and output the survived indices one by one, by shifting to the right in a circular manner.

84E - Track

I spent about three hours modifying the algorithm to avoid the time limit....The most impressive modification I used is scaling the constant from 1 to . This is the first time that I realized what an important role that a constant can play.

The general idea is to generate all the feasible patterns of maps and find out the one with the minimum distance and order. For instance, if letter 'a' and 'b' can be used, then we will obtain a map where we can move to positions of 'a' and 'b' while the other ones can not be used. With this equivalent map, we can implement BFS from the starting position until the terminating position is reached. During this process, we update the distance and also the minimum order if necessary.

As k can take values up to 4, we may have to check as many as C264 patterns for the worst case. It turns out that this will lead to TLE. Therefore, we have to further reduce the complexity. Instead of beginning from the starting position, we can begin from every one of the four positions that can be reached from the starting position. Each time we select one position, we have determined one letter that must be used and thus the number of feasible patterns is reduced to C253, which is supposed to satisfy the time limit as I consider.

However, I made a mistake that the number of generated patterns is in fact A253 rather than C253. As these two values only differ by a constant of , I did not realize (or believe) that such a constant matters so much. After I correct the mistake, it passed... What a fascinating problem!!

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

By pleasurepain, 5 weeks ago, In English,

79A - Bus Game

We can directly simulate the process and thus obtain the final result.

79B - Colorful Field

We store the positions of all the “waste” in each row, and also the corresponding number. For each query, we find the right row and check whether it is “waste” or not. If no, then we calculate the total number of waste before this position, which can be obtained with constant complexity if we use prefix technique. Then, we will know the total number of crops and the correct type can be computed according to the remainder obtained by dividing 3.

79C - Beaver

For each of the given n small strings, we can calculate its beginning and ending positions in the long string, where it appears. The above results can be directly computed without using any advanced techniques about string, since the length of small string is quite short.

For each index i in the long string, we store two types of information. We first record the indices of small strings that start from i and their beginning position, specifically in this trival case equal to i. Secondly, we record the indicies of small strings that end at i and their beginning position, which is just i - length(smallstring) + 1.

The left work is to use two pointers technique to calculate the required answer. We use p1 and p2 to denote the beginning and ending positions of the current range that we are observing. At the same time, we record a “set” which contains the small strings belonging to the current range.

When we move p2 forward by one step, we add new small strings (if any) to the set, and check is there any small string ending at p2 are included in the set. If yes, it means that the current range contains at least one small string and thus we should move p1 forward by one step to obtain a new range for the next check. Before p1 is increased, all the small strings that start at p1 should be deleted from the set. If no, we can further move p2 forward to check the next extended range.

As we use “set” in the STL of C++, the updating of set has complexity of O(logN), and thus the total complexity is O(NlogN).

Read more »

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

By pleasurepain, 5 weeks ago, In English,

78A - Haiku

Count the total number of “a, e, i, o, u” in each line, and check whether they satisfy the form of “5, 7, 5”.

78B - Easter Eggs

For simplicity, we use 0, 1, 2,...,6 to denote the seven colors. The following pattern always satisties the requirement 012345634563456345634...

78C - Beaver Game

A very interesting problem!!

We use FIRST to denote the player who moves first, and SECOND to denote the other player. If n is an even number, this results in a perfectly “symmetric” situation, and SECOND always wins since he can simply “copy” what FIRST has done. As long as FIRST can succeed cutting the logs, SECOND can also make it.

When n is an odd number, it becomes a little complicated. We write m = XY, where both X and Y are divisors of m, and it also means that the original log of length m has been cut into X new logs with the same length Y. To satisfy Y ≥ k, we should have . If we set X as the maximum divisor that satisfies this condition, then none of the logs of length Y can be further cut. We can prove this by contradiction. Assume that Y can be further cut, which implies that Y = pq, and q ≥ k. Thus, we can obtain a larger X' = Xp, which is impossible since we have set the maximum value to X.

Therefore, FIRST can first cut any original log so that none of the new logs can be further cut. Then, the situation is equivalent to saying that we are given n - 1 (an even number) logs while rightnow SECOND is the first one to move, and thus FIRST wins. Be careful that X cannot be 1, and thus if X = 1, FIRST still loses.

78D - Archer's Shot

A wonderful mathematical problem. We count the number of hexagons column by column. We denote the column that contains the center “A” as the first column. According to the symmetry, it is sufficient to focus on the columns to the right of “A”, inclusively. For each column, we use binary search to find the highest hexagon. Again due to the symmetry, we only need to count the hexagons above “A”.

For the hexagon with height h, we can check two points, the right upper point and the rightmost point, to see whether both of them fall inside the circle or not. If yes, this hexagon is covered by the circle; otherwise not. The left work is to compute the distance of these two points from the center, which needs some simple geometric calculation (using Pythagorean theorem) and omitted here.

Read more »

 
 
 
 
  • Vote: I like it  
  • -9
  • Vote: I do not like it  

By pleasurepain, 6 weeks ago, In English,

80A - Предсказание Панорамикса

As the range is quite small, we can directly calculate the next prime integer and check whether it is the same as the given one or not.

80B - Депрессия

At first, we should note that if the hour is larger than 12, we can decrease it by 12, since they will form exactly the same angles. For instance, 13:26 is equivalent to 01:26. Then, we calculate the angles of minute and hour, respectively. As 60 minutes are equal to 360 degrees, its angle is just M × 6. For the hour, 1 hour or 60 minutes is equal to 360/12 degrees. Thus, the angle of hour is H × 30 + M × 0.5.

80C - Герои

A little complicated but not quite difficult problem. Enumerate all the feasible divisions of the heroes, and find out first the minimum difference and then the maximum liking.

80D - Сброс наковальни

This is a pure mathematical problem. We use f(p) and f(q) to denote the probability density function (pdf) of p and q, respectively. For normal distribution with range [x, y], the pdf is written as . Then, we derive the formula as follows:

We first deal with the first term.

.

Then, it comes to the second term. This should be solved based on the following two cases:

1) 4b < a:

2) 4b ≥ a:

Therefore, for a ≠ 0 and b ≠ 0, we can calculate the answer according to the above formula. For the other cases, the rules are:

1) a = b = 0, the answer should be 1;

2) a = 0, b ≠ 0, the answer is ;

3) a ≠ 0, b = 0, the answer is 1.

80E - Боброжуй-0xFF

I think this is a nice problem to practice dp based on trees. We use dp[n] to denote the maximum number of beavers that it can eat, under the condition that all the child nodes of node n have been processed and it returns back to node n. Furthermore, we use left[n] to denote the number of beavers that are still at node n, under the above same condition. We need another array beaver[n] to denote the number of beavers at each node at the beginning.

Now, we start implementing DFS from the given root node s. To calculate dp[n], we assume that all the child nodes of n, i.e., dp[m], have been computed (they are obtained when the DFS function returns). Then, we sort all the dp[m] in a decreasing order. If we use M to denote the number of its child nodes that have at least one beaver, then . Moreover, note that we might still have beavers left at both node n and its child nodes, and we should take them into consideration as well. Thus, we should further update .

Be careful that when we call DFS to deal with any child node, we should decrease beaver[m] by 1, since we need at least one beaver to return back!! Also remember to update left[m] with correct values. The DFS function trivially returns when it is a leaf node or it has no beavers at all. Finally, we can output dp[s] as the required answer.

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

By pleasurepain, 6 weeks ago, In English,

Well, this is a tough round...

74A - Room Leader

The solution is straightforward. Calculate the total points for each user, and output the one with the maximum points.

74B - Train

The following example might give us more intuitive understanding to this problem. Suppose that stowaway is at position 3 while the controller is at 5 and moving to positions with larger indices. If the train keeps moving, the optimal position at which the stowaway should stay is obviously 1. However, the optimal strategy might change if the train stops at some station before the stowaway is caught. When the train stops, the stowaway can first check both the current position and moving direction of the controller, and then find out the next optimal position, just as the above simple example shows.

With the above arguments, we can directly simulate the whole process according to the given string.

Read more »

 
 
 
 

By pleasurepain, 7 weeks ago, In English,

75A - Life Without Zeros

This is a "straightforward-implementation" problem. Eliminate all the zeros in each integer and check whether the sum equation still holds or not.

75B - Facetook Priority Wall

The main issue involved in this problem is how to correctly sort out the names and actions. After this, we only need to record the scores that every user can obtain, and output them in the required order.

75C - Modified GCD

At first, we should compute the GCD of the given two integers. As their common divisors must also be the divisors of GCD, the next step is to calculate all the divisors of GCD, and store them in the array S. Then, we sort S in a decreasing order, and for each query, we can directly enumerate S from the last element to the first one while stopping if we find the first element that falls into the interval.

It seems that the above algorithm might lead to a risk of TLE. However, it turns out that the number of divisors of GCD cannot be very large, even if the maximum integer is up to 1E+9. Suppose that one integer only has 2 as its prime divisor. Then, it cannot exceed 2^36, and thus the number of divisors is at most 37. If it has 2 and 3 as its prime diviosrs, the number turns out to be at most 18*18. Furthermore, if it has 2, 3 and 5, the number seems to be less than 10^3. According to these observations, the above enumeration algorithm almost surely works well.

75D - Big Maximum Sum

A well designed problem! We should first implement some pre-calculation before solving it. For the i-th small array a[n], we compute its total sum T[i], the maximum prefix sum P[i], the maximum suffix sum S[i] and the maximum sum of sub-sequence M[i].

For the large array b[m], we use b_end[m] to denote the maximum sum with b[j] as the ending. This can be calculated by the following formula:

1)if b_end[j-1]+T[b[j]]>S[b[j]], then b_end[j]=b_end[j-1]+T[b[j]]

2)otherwise b_end[j]=S[b[j]]

with b_end[0] initialized as S[b[0]].

Then, we enumerate b_end[m] and find out the maximum b_end[j]+P[j]. Note that we should further compare this value with all the M[j] that have appeared in b[m], and find out the maximum one as the final answer.

Read more »

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

By pleasurepain, 7 weeks ago, In English,

73A - The Elder Trolls IV: Oblivon

I think there exists a general method to solve any n-dimensional cases. Suppose that we are given n elements, and we denote them as a[0], a[1],.... At first, we calculate k/n (integer division) and k%n. Then, we find out every a[i] such that a[i]-1≤k/n, and denote the number of such elements as NUM. Furthwrmore, we update the following values:

k=k-(a[i]-1), a[i]=1, n=n-NUM

We repeat the above steps until at least one of the following conditions is satisfied:

  1. n=0, i.e., no more a[i] can be cut.

  2. k=0, i.e., we have no more chances to cut any a[i].

  3. k/n=0, i.e., we only need to deal with the left k%n chances.

If k/n=0 but k%n>0, we can just find all the a[i] that satisfies a[i]>1, and update a[i]=a[i]-1 and k=k-1. This operation stops if either k=0 or no more such a[i] can be found.

73B - Need For Brake

This is a very "brain storm" problem. Although only m new scores are given, we can add n-m zeros to obtain a n-length sequence, denoted as S, which is further sorted in a decreasing order. We first try to find the worst rank.

It is obvious that to obtain the worst rank, the target racer should add the minimum value of S. Then, we sort all the racers in a decreasing order, and denote the current rank of target racer as R. For the racers with better rank than R, we should assign the minimum values of S to them, too. Thus, we use a pointer R2 to denote the rightmost position of S, which is still not assigned to any racer. We scan the racers with rank worse than R, and calculate whether it is possible to achieve a better rank if the score with index R2 is added. If yes, we move on to check next racer and update R2=R2-1. Otherwise, we only decrease R2 by one check again. During this process, we should record the number of racers which have better ranks than R, and this is just answer.

Now, we try to find the best rank. We give the target racer the highest score, and sort all the racers again in a decreasing order. For the racers who have better rank than R, we should assign the maximum scores to them, since they have already got better ranks even without any extra scores. We need to introduce another pointer R1 to denote the leftmost position of S which has not been assigned to any racer. Then, we scan the racers with worse ranks, and check whether it is possible to obtain a better rank than R if giving the score at R2. If yes, we in fact should give the score R1 rather than R2 to him, since "he is surely" to achieve a better rank, while updating R1++. If no, we should decrease R2 by one and check again. For this case, we should introduce a variable RES, which is used to denote the number of skipped R2. In fact, the previous opeartions under "YES" is not correct.... Instead, if yes, we should first check whether RES is larger than zero or not. If RES>0, we add R by one while decreasing RES by one; otherwise we update R1=R1+1, and also add the number of racers who have better ranks by one.

73C - LionAge II

This is a standard DP problem. It suffices to use dp[n][z][k] to denote the maximum value under the state of "dealing with the n-th character in the given string, changing this letter to 'z', the number of changed letters being no larger than k". The updating formula is

1) z=s[n], dp[n][z][t]=max(all z', dp[n][z'][t]+weight[z'][z])

2) z!=s[n], dp[n][z][t]=max(all z', dp[n][z'][t-1]+weight[z'][z])

Read more »

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

By pleasurepain, 2 months ago, In English,

71A - Way Too Long Words

For the given string, if its length is not larger than 10, we shloud output it directly; otherwise we should output the first letter, the length minus 2, and the last letter.

71B - Progress Bar

It can be observed that a reasonable answer must always be writen as x*k+y, where x denotes the number of values that are equal to k while y denotes the unique value which is neither k nor zero. Note that y can be zero.

According to the conditions, we have (x*k)/(n*k)≤(t/100), and thus x≤t*n/100. We can first compute x as t*n/100, where "/" denotes the integer division. Then, we can enumerate y from 0 to k-1, inclusively, to find out the answer.

71C - Round Table Knights

It seems that we have to enumerate all the feasible polygons and their rotation angles to find out the answer, which leads to complexity of O(N^2). However, one can check that if a polygon with M edges is found to be reasonable, then we can always find at least another one polygon with Q edges, where Q is a divisor of M, which is reasonable as well. The reason is simple. As all the M points are reasonable, we can select the first points of every M/Q points to form the target polygon.

Therefore, it is sufficient to test the polygons which have 3, 4, 5, 7, 11, 13... edges. It can be seen that all the integers are prime except for 4. The left work is to find out all the prime numbers from 3 to the given n. There exists a famous algorithm with complexity O(NlogN), and one can search on the internet for more details. I remember that the number of prime integers from 1 to some constant N is O(logN). If I am correct, the total complexity turns out to be O(NlogN).

71D - Solitaire

The solution is straightforward, and one should just follow the steps to calculate the results. However, the coding is fairly complicated....

71E - Nuclear Fusion

This is a nice problem to practice DP based on bitmask technique.

We use an integer i from 0 to (1<<n) to denote the "states". For a bit, "1" means that the corresponding element is used to generate a new element; while "0" means that it has not been used. At the first step, for each state, we take out "1"s and calculate the sum weight that it can achieve. Moreover, for each sum, we store all the states that can achieve this value. Then, we use dp[1<<n][k] to denote that whether it is possible or not to generate the first several target elements, while achieving the corresponding states. The 0-th column of dp is initialized to zero except for the first row, which is set to 1 to indicate that it is possible to generate 0 target element while achieving the all-zero state, i.e., no given elements are used. Then, to update dp[row][col], we first enumerate all the values of dp in column col-1, and find out those with dp[row'][col-1]=1, since only these states are reasonable. Next, we enumerate all the states S that can generate the col-th target element. Note that only those satisfying S & row'=0 should be considered as reasonable states, and this in fact leads to a new state S | row', and thus we should update dp[S | row'][col]=1. Furthermore, we should keep S so that we can backtrace the equation required by the problem.

Read more »

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

By pleasurepain, 2 months ago, In English,

70A - Cookies

We use a[n] to denote the number of empty cells for a square of size 2^n*2^n. The square of size 2^(n+1)*2^(n+1) can be built from the smaller one of size 2^n*2^n. Moreover, it can be observed that if we divide the larger square into four smaller ones, the left upper, left bottom and right bottom ones are just exactly the same copies of the smaller one, while the right upper one is fully filled. Thus, a[n+1]=3*a[n]. Note that for the special case n=0, the answer should be 1.

70B - Text Messaging

At first, we find out all the independent sentences, and store them in the same order as they are given. Then, we keep merging the sentences into a message as long as its length does not exceed the requirement. Be careful that if two messages are combined together, the space between should also be counted, while if they belong to different messages, the space must be omitted.

70C - Lucky Tickets

We use rev[i] to denote the integer obtained by reversing i. Next, we use g[i] to denote the GCD of i and rev[i]. Note that i/rev[i] can be further reduced to (i/g[i])/(rev[i]/g[i]), and thus it can be observed that j must be a multiple of rev[i]/g[i].

With the above observations, we can directly enumerate x from 1 to maxx while y from 1 to maxy bit with j=j+rev[i]/g[i]. During this process, once we find that i*j=rev[i]*rev[j], we store j by using the segment tree. Then, we implement binary search to find out the smallest y so that the number of i*j=rev[i]*rev[j] is no less than w. Therefore, we can check the value of x*y and obtain the minimum answer.

Remember to calculate all g[i] and rev[i] previously; otherwise it might lead to TLE.

Read more »

 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it  

By pleasurepain, 2 months ago, In English,

69A - Young Physicist

Add all the vectors together, and check whether the result is a zero vector or not.

69B - Bets

We first enumerate all the sections, and for each section we check all the players to find the one who participates and has the minimum time to finish this section. Then, for this section, we can just bet on this selected player and obtain the corresponding profit. Finally, we add the profits of all the sections together to obtain the required answer.

69C - Game

This problem is solved by straightforward implementation. One should be careful that whenever a new query comes, we should immediately check whether a new composite element can be obtained. If yes, we should implement this operation and update the results at once.

69D - Dot

I think this is a very nice problem to practice dealing with a game, which two people take turns to play using the optimal strategy.

At first, one can find that it is not necessary to take the "reflection" operations into consideration. When someone first chooses to reflect x and y, it in fact means that he must have been in a losing state. However, the competitor can reflect the coordinates again, and thus it returns to the previous state. In other words, the two reflection operations from different players cancel each other.

Next, for each coordinate (x, y), we assign it with a state, indicated by 'losing and winning', which gives the final result that one player can achieve if he starts to move from this position. For each position, we can obtain all the feasible positions that he can move to according to the given vectors (note that only the positions inside the circle should be viewed as "feasible"). Moreover, if any of them is a losing state, this position should be assigned with winning state, otherwise with losing state. We can start from the initial position and implement DFS to calculate the states. Note that for some position, if all the next positions to which it can move fall outside the circle, it is definitely a losing state, and this serves as the "return condition" in DFS.

This sort of problem in fact has a general solution, which uses BFS rather than DFS. It looks a little like Topological Order. One can check the book in http://codeforces.com/blog/pllk for more details.

69E - Subsegments

This problem turns out to be quite easy if one uses the "set<>" in STL of C++. When a new element enters the sliding window, we increase the times that it appears by one, while if an element moves out of the sliding window, we decrease it by one. If one element appears exactly once, then we insert it into the set; otherwise we erase it from the set. Sorting is automatically implemented and maintained in set, and thus the maximum value can be obtained at any time with constant complexity O(1). "Insert, erase, sort" are all implemented with complexity O(logN), which leads to a total complexity of O(NlogN).

Read more »

 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

By pleasurepain, 2 months ago, In English,

68A - Irrational problem

This problem can be solved by direct implementation as it requires. The main issue involved is the generation of all permutations for some given sequence. As the problem guarantees that all the given integers are different, a simple recursive backtracing algorithm is sufficient. Completing this, we can count the number of integers that satisfy the conditions.

68B - Energy exchange

This is a very nice problem to practice binary search. Different from the conventional binary search based on index, this one has to deal with "float type", and thus the loop should be terminated by limiting the number of search.

We can directly search the required answer. During each search, we enumerate all the elements and calculate two results, denoted as E_out and E_in as follows. If the element is no less than the current answer, then we add the difference to E_out; otherwise we add the difference to E_in. Note that here the difference is always larger than or equal to 0. Then, we compare whether E_out*(1-k/100) is no less than E_in or not. If yes, it means that the answer for the next loop should be increased; otherwise it should be decreased.

68C - Synchrophasotron

This problem has given me a deeper understanding of DFS, or backtracing.

We should adopt an array FLOW[n] to denote the fuels that are currently stored at some node, and later these fuels will flow to other nodes. As we start at node 1, we can enumerate all the possible values of fuels that are initially stored at node 1. It is sufficient to begin with 0 and end with 26, since there are at most 5 edges going out from node 1, and each of them is at most 5. The enumeration should be immediately terminated once we have found a reasonable value, since the problem asks to find out the minimum flow.

The DFS function should handle three cases depicted as follows:

  1. For some node i, all the nodes to which it directs have already been processed. Then, we check FLOW[i], and if FLOW[i]=0, we should call this DFS function again but start at node i+1;

  2. For node n-1, all the nodes that it directs to have already been processed. We should immediately "return" and update the maximum cost;

  3. For some node i, we enumerate all the possible fuels X that can flow to some other connected node j, while decreasing FLOW[i] by X and increasing FLOW[j] by X. Then, we call the DFS function for the next node. Remember that after the function returns, FLOW[i] and FLOW[j] should be changed back to their original values.

68D - Half-decay tree

Although the complete binary tree will have about 2^30 nodes, only a small fraction of them will be used, since the number of queries is limited to 10^5. Thus, we should first use map<int ,int > to compress the indices of nodes that we are going to deal with. Then, the problem can be solved based on the following two steps:

1) Update: We use cost[n] to denote the number of electrons that node-n and all its child nodes currently contain. Whenever a node with some electrons X is added, we find out the path from this node to the root node, and add the same number of electrons to all the nodes involved in this path. In other words, cost[n]=cost[n]+X, cost[n/2]=cost[n/2]+X, cost[n/4]=cost[n/4]+X...

2) Calculate: When a query comes, we calculate the required result, denoted as ANS. If the decay occurs at the first leaf node, we will obtain a component which consists of node-1, node-3 and all the child nodes of node-3 (there are other components, but we first only focus on this one). If the decay occurs at the second leaf node, we will obtain the component consisting of node-1, node-3 and all the child nodes of node-3 again. Besides, it can be seen that if decay occurs at any leaf node with index from [1, 2^(h-1)], i.e., the first half leaf nodes, we will always obtain the component with node-1, node-3 and all the child nodes of node-3. Moreover, we can compute that this special component has a charge of cost[1]-cost[2], while for the other components, it will have charges of at most cost[2]. Therefore, if we have cost[2]<cost[1]-cost[2], it means that if decay occurs at the first half leaf nodes, it will always contribute to the final expectation with 2^(-1)*(cost[1]-cost[2]), i.e., ANS=ANS+2^(-1)*(cost[1]-cost[2]). Thus, we can skip the first half leaf nodes and consider the case that the decay occurs at the second half leaf nodes, i.e., we can move to node-3. On the other hand, if cost[2]>cost[1]-cost[2], it means that cost[3]<cost[1]-cost[3]. This can be proved by using

cost[1]-cost[3]=cost[2]+C(some constant)>cost[2]>cost[1]-cost[2]=cost[3]+C(some constant)>cost[3]

This implies that we can skip the second half leaf nodes, and ANS=ANS+2^(-1)*(cost[1]-cost[3]), and we can move to node-2.

In fact, the problem has been reduced to another one with height h-1, and we can thus repeat the above arguments again. Suppose that we are now at node-3, and thus we should compare cost[3] and cost[3]-cost[6]. However, remember that as we are at node-3 now, and thus the decay should occur at leaf nodes with indices from [2^(h-1)+1, 2^h]. This implies that we will always have a component which consists of node-1, node-2 and all the child nodes of node-2, with charge of cost[1]-cost[3]. We use another variable max_cost to denote this value, i.e., max_cost=cost[1]-cost[3]. This will affect the calculation of ANS. Suppose that cost[3]<cost[3]-cost[6], and then we should compute ANS=ANS+2^(-2)*max(max_cost, cost[3]-cost[6]) rather than directly adding cost[3]-cost[6] to ANS. After this, we should update max_cost=max(max_cost, cost[3]-cost[7]).

Read more »

 
 
 
 

By pleasurepain, 2 months ago, In English,

67A - Partial Teacher

This is a very tricky problem... For instance, given RRL, my first solution will output 1 2 3 2, however it is obvious that a better sequence 1 2 3 1 exists.

For each integer, we have known that it must be at least 1. However, the "L" letters on its right side mean that it should be some larger integer. Thus, we should count the number of "L" on its right side until a "R" is met (note that we should continue if any "=" is met but this is not counted) or arrive at the end, which is denoted as nL. Similarly, we count the number of "R" on its left side until a "L" is met or reach the starting position, which is denoted as nR. The value of this integer is thus max(nL, nR).

For an intuitive understanding, nL implies that there are exactly nL integers on its right side, which are smaller, and thus it must be at least as large as nL.

67B - Restoration of the Permutation

We can check array b[ ] from left to right, and find the first element that is 0. Suppose that we are trying to restore a[i], and find b[j]=0. It means that the number of integers to the left of "j" which are larger than "j+k" is zero (the indices are counted from 1). Thus, we can set a[i]=j. Next, we should enumerate array b[ ] again, and for each b[j], if a[i] is no less than "j+k", we should decrease b[j] by 1. The total complexity is O(N^2).

However, in fact, I do not know why the above algorithm works... i.e., why it will give the optimal answer...

67D - Optical Experiment

I think this is a very nicely designed problem!! The solution turns out to be clear, if we replace the indices upside from left to right by 0,1,2,..., i.e., "remap" them to a naturally increasing order, while the indices downside should be "remapped" correspondingly.

After the above operations, we in fact have obtained two sequences, one of which is in an naturally increasing order, denoted as a[n] (a[1]=1, a[2]=2,...,a[n]=n), while the other one can be viewed as a permutation sequence of the first one, denoted as p[n]. Suppose that rays with indices i<j<k (these indices are in a[n]) intersect with each other. This means that if b[x]=i, b[y]=j, b[z]=k, we must have x>y>z. In other words, we can always find some z<y<x so that

b[z]>b[y]>b[x]

It can be seen that the original problem in fact has been converted to an equivalent one, which asks to find out the longest decreasing sub-array in array b[n]. One can find a lot of information about this classic and well investigated problem on the Internet. To avoid Time Limited Error, one should adopt the algorithm with complexity O(NlogN).

Read more »

 
 
 
 

By pleasurepain, 2 months ago, In English,

66A - Petya and Java

As the input only contains positive integers, it is sufficient to just consider the right border of each type, and we can store them as strings. Similarly, the input should be stored as a string as well. Then, we compare the input with the right borders from small to large. For each border, if the length of the input is smaller, this type is just the answer, while if they have the same length, then we can compare them using the "string comparison".

66B - Petya and Countryside

A straightforward solution has complexity O(N^2). We check every element, and find the longest non-increasing sub-arrays that both start from this element but extend to the right and left direction. Then, we add their length together, and the answer is just the maximum one. In fact, the longest non-increasing sub-arrays mentioned above can be computed with complexity O(N) in advance, and thus an improved solution has linear complexity.

66D - Petya and His Friends

For any n that is larger than 2, the required sequence always exists. One feasible sequence is 3*2, 5*2, 3*5, 3*2*2, 3*2*2*2, 3*2*2...*2.

66E - Petya and Post

This is really a well designed problem. One can check http://codeforces.com/blog/entry/1452 for more details. I think the most tricky part is that

(a1+a2+...an)-(b1+b2+...bn)=0

Thus, we have

0-(a1-b1)=(a2+a3+...an)-(b2+b3+...bn)

which is just the metric calculated if we start from position a2.

Read more »

 
 
 
 

By pleasurepain, 2 months ago, In English,

65A - Harry Potter and Three Spells

One should be very careful of this problem...If a*c*e<b*d*f, it is obvious that we can obtain infinite gold. Besides, if c=0 and d>0, it implies that we can obtain infinite gold as well. Next, if a=0 but all of b, c and d are not 0, we can still obtain infinite gold since we can first obtain infinite lead and thus convert all of them to gold.

65B - Harry Potter and the History of Magic

This problem can be solved by adopting a greedy algorithm. We first introduce a variable Y which is initialized with value 1000, i.e., the minimum year that meets the requirements. Then, we enumerate the input integers in the given order. For each integer, we start with the current Y, and increase Y by 1 until it reaches 2011. During this process, we check whether we can convert this integer into Y by changing no more than one digit. If the answer is yes, we can immediately stop the loop and just replace this integer with the current value of Y, and store the current Y for the next loop which deals with the next integer; otherwise it means that there is no solution.

65C - Harry Potter and the Golden Snitch

This is a nice problem for practicing binary search as far as I consider. We can use binary search to search for the earliest time when they will meet. As the search is based on "float types", it is better to limit the times of search to terminate the loop rather than adopting a small constant like /epsilon to check whether the answer has converged.

At first we set t_l=0 and t_r to be some sufficiently large value. Then, for each loop we will check whether they can meet at time t_m=(t_l+t_r)/2 or not. With this t_m, we can first calculate the ranges that the player can reach, which turns out to be a circle. Therefore, the left work is to calculate the position of the ball at time t_m, and check whether it falls inside the circle or not. If it is inside the circle, it means that they can meet at some earlier time, and thus we should set t_r=t_m for the next search; otherwise we should set t_l=t_m. At time t_m, we can first compute the total distance that the ball has moved, and then we can find out the segment at which the ball will appear. With this result, we can further calculate the exact position (x,y,z) of the ball, and thus determine whether the ball is inside the circle or not.

65D - Harry Potter and the Sorting Hat

A straightforward solution is to enumerate all the possible final patterns, and thus find out the houses that one can select. This process can be simulated by building a tree, and each node denotes the current pattern while each branch denotes the letter given in the string. However, we might run into a severer situation due to the huge expansion of the tree. To alleviate this problem, we can adopt set< > in C++ STL, since some patterns are the same in the trees. As a simple example, suppose that we first meet ????. It can be seen that no matter what the intermediate states can be, they will finally reach the state (GHRS). As set< > produces an efficient way to delete the duplicate states, the total number of states that we have to visit can be significantly reduced.

Read more »

 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it  

By pleasurepain, 3 months ago, In English,

63A - Sinking Ship

The solution to this problem is straightforward. We can enumerate the elements in the given order, and store every one of them in an appropriate array. For instance, we can adopt four arrays A, B, C and D, which represent "rat", "woman and child", "man" and "captain", respectively. For each element, we just put it into the correct array and finally we output the elements stored in the arrays in the order of A, B, C and D.

63B - Settlers' Training

We can simulate the process of training and count the number of coins that we need to meet the requirement. We can adopt a hash table H[n] to represent the number of people belonging to different ranks. For instance, H[i] denotes the number of people belonging to rank i. Then, we scan the hash table H[n] from k-1 to 1, and as the problem claims, whenever we find that H[i]>0, we just decrease H[i] by 1 while increasing H[i+1] by 1. The above operations should be repeated until we find that H[k]=n is satisfied, and the number of loops is just the answer.

63C - Bulls and Cows

At first, we enumerate all the integers from 0 (in fact this is 0000) to 9999, inclusively. For each enumeration, if all the four digits are different, then it can be viewed as a reasonable integer that is selected by the thinker. Given such an integer, for each guessed number, we can directly calculate the number of digits that give both correct values and positions, and the number of digits that only give correct values but incorrect positions as well. Then, we compare these results with the number of "bulls" and "cows". If they are exactly the same for all the guessed numbers, it means that the integer in the current enumeration can serve as a correct "data". After all the enumeration has been completed, if the number of correct "data" is larger than 1, it means that we "Need more data"; if the number of correct "data" is exactly equal to 1, it means that the "data" is enough and we can just output this correct "data"; if the number of "data" is equal to 0, it means that the thinker must have made a mistake and we should output "Incorrect data".

63D - Dividing Island

For problem like this one, we can fill the grids like a snake. If a is an even number, we can start from the upper left corner and go down first to fill the first column, and then we reach the bottom of the second column and go up to fill the second column, and so on. If a is an odd number, we should start from the bottom left corner and go up first to fill the first column, and then we arrive at the top of the second column and go down to fill the second column, and so on. With the above operations, it can be seen that we can "safely" switch from the last column of "b*a square" to the first column of "d*c square".

63E - Sweets Game

I think this is really a nice problem to practice the bit-mask technique, and be familiar with the transition among different states, which has also been frequently used in bit-mask Dynamic Programming technique. I think it mainly contains the following steps:

1) Given M positions, we usually use "1" to denote that some position has been taken while "0" to denote that the position is NULL. Therefore, the total number of states should be (1<<M)=2^M. If M<32, it suffices to use an "int" to cover all the potential states, since the binary form of "int" just consists of "0" or "1". For instance, for an integer i=5 with binary form of i=(101), it means that the first and third position have been taken while the other ones are NULL. Alternatively, one can also use the most significant bit to denote the first position.

2) For each state S, it can transit to another state T by implementing some "move". In general, we still use an "int" to denote the "move", as done in step 1). However, for many problems (not all), a reasonable "move" should satisfy the following condition

(S & move) == move

This constraint implies that we can only take away "1" at state S rather than "0", since "0" means NULL and there is nothing can be taken. For instance, S=(101), thus move=(100) is reasonable however move=(110) is not.

3) With a reasonable move, another state T can be reached by T= (S ^ move). (S ^ move) in fact achieves the effect that some "1"s at state S have been taken by the "move". For instance, S=(101), move=(100), and thus we have T= S ^ move=(001).

4) In general, we can enumerate all the states from 0 to (1<<M)-1, inclusively, or from (1<<M)-1 to 0, according to the problem. For each enumeration, we generate all the possible "move" and only select the reasonable ones to obtain the next states that can be transited to. For instance, for this problem we are taking away "1" from some state S, and thus we can start the enumeration from 0 to (1<<M)-1. The state S=0 is initialized to be "losing state". Note that for each state S during the enumeration, (S ^ move)< S always holds. Thus, the next states that S can transit to have been already determined to result in "winning state" or "losing state", and the current state S can be determined as well.

Read more »

 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it  

By pleasurepain, 3 months ago, In English,

A. A Student's Dream

We use Gn and Bn to denote the number of fingers of hands, which the girl and boy hold, respectively. According to the problem, Bn>=Gn-1 should hold, since otherwise at least two fingers of the girl will touch. Moreover, Bn<=2*(Gn+1) should hold as well, since otherwise at least three fingers of the boy will touch.

B. Tyndex.Brome

We first deal with the address entered by the user. As only lowercase letters are involved, we can adopt 26 arrays and use each of them to store all the positions at which the corresponding letter has appeared in the entered address, and sort the positions in an increasing order. Then, we calculate the value of the error function for each potential address. As the problem requires, for each letter at position j in some potential address, we try to find the closest position at which the same letter appears in the entered address. To find this, we can implement index-based binary search on the previously stored array H[n], and find the position i such that H[i]=<j<H[i+1]. Thus, min(j-H[i],H[i+1]-j) is just the value of error function for the current letter.

In fact, I find it more difficult than I thought to write a correct index-based binary search... Therefore, I give some of the details that I think are quite important.

Suppose that a[0],a[1],...,a[n-1] have been sorted in an increasing order, and T is the "target". The following index-based binary search will find the largest a[num_L] such that a[num_L]<=T<a[num_L+1] (assuming that num_L+1 is reasonable, i.e., num_L+1<=n-1). The comments have been added in the corresponding places.

int num_L=0;  // num_L denotes the left border, and one should guarantee that a[0]<=T, which can be tested in advance;  if a[0]>T, it is even not necessary to implement such a binary search;
int num_R=n-1; // num_R denotes the right border, and one should guarantee that it is initialized so that the whole range can be covered
while (num_L<num_R)  // note that the termination condition is num_L<num_R but not num_L<=num_R, while the latter one might lead to an infinite loop
{
	int num_M=(num_L+num_R+1)/2;  // num_M denotes the middle point which we are going to check, and note that using (num_L+num_R)/2 might lead to an infinite loop as well
	if (a[num_M]>T)  // this is not a[num_M]>=T, since we are to find a[num_L]<=T rather than a[num_L]<T
	{
		num_R=num_M-1;  // update the right border as num_M-1 for the next loop; note that here is not num_R=num_M, since num_M has been checked and it can definitely not satisfy a[num_M]<=T in the current loop
	}
	else
	{
		num_L=num_M;  //update the left border as num_M for the next loop; note that this is not num_M+1, since we can only guarantee that num_M is safe for the next loop as a[num_M]<=T holds in the current loop
	}
}

One can check that, when the loop terminates, num_L will always satisfy that a[num_L]<=T<a[num_L+1].

Read more »

 
 
 
 
  • Vote: I like it  
  • -3
  • Vote: I do not like it  

By pleasurepain, 3 months ago, In English,

A. Ultra-Fast Mathematician

This is a simple problem, and the result can be obtained by implementing "Xor" operations to the given two sequences. The "Xor" operation is also referred to as "mod-2 sum", which has been widely used in channel coding theory. In channel coding theory, for any two codewords c1 and c2, which both consist of only 0 and 1, the result of "c1 Xor c2" is referred to as the Hamming Distance between c1 and c2, and this distance in fact describes the capability to tell one of them from the other one.

B. Hard Work

This problem is really a "hard work"... At first, for the given three initial strings, we should delete all the signs since they do not affect the results, and then we should generate all the 3!=6 possible concatenations. Next, for the students' strings, we first delete all the signs as well, and then compare it with every one of the 6 concatenations. If it is equal to any one of the 6 concatenations, the answer is "ACC"; otherwise it should be "WA". Note that the uppercase and lowercase letters should be omitted during the comparison.

C. Capture Valerian

As the given integer c is in base a, we should first convert it back into an integer in base 10. If b is also an integer, the left task is just to convert c into an integer in base b and output the result. It turns out to be a little complicated if b is 'R'. For this case, we deal with the digit in a (the given integer) from the least significant digit to the most significant one. For each digit, denoted as D, it should be converted into Roman forms according to the following 5 cases.

1) D=1,2,3: repeat the corresponding symbols in Roman forms for D times;

2) D=4: this has a unique Roman form;

3) D=5: this has a unique Roman form;

4) D=6,7,8: first write down the Roman form of '5', and then repeat the corresponding symbols for D-5 times;

5) D=9: this has a unique Roman form.

Note that when we deal with the above cases, the position of the digit matters as well. For instance, a=xxxD, and we are dealing with D, then the "corresponding" symbols can only be 'I' and 'V'. For a=xxDx, the related symbols are 'X' and 'L'.

D. Eternal Victory

The hint is that "He can finish his travels in any city". Suppose that we are now at node-1, and node-1 has three child nodes, node-2,3,4. Without loss of generality, we visit the child nodes just in the natural order. We first move to visit node-2, and to visit node-3, we have to come back from node-2 to node-1. This means that the edge between node-1 and node-2 has been used twice. Furthermore, if node-2 has child nodes as well, by some simple induction, we can see that all the edges have to be visited for at least twice. However, when we finally visit node-4, it is sufficient to use the edge between node-1 and node-4 only once since "He can finish his travels in any city", which implies that "He does not have to come back to node-1 again".

With the above arguments, it can be seen that we will finally arrive at some leaf node, and finish the travel at that leaf node. Therefore, only the edges from the root node-1 to this special leaf node are used once while the other ones have been used at least twice. Thus, it suffices to find out the farthest leaf node from the root node-1, and the answer is just 2*sum(E[i])-D_max, where E[i] denotes the length of the i-th edge, and sum(E[i]) denotes the total length of all the edges while D_max denotes the maximum distance from node-1 to some leaf node.

E. Enemy is weak

This is really a nice problem to practice Segment Tree techniques as far as I consider...One can search on the internet and will find a lot of information about Segment Tree techniques. Thus, I will not give the details but only how I understand it, and when we should use it based on my own understanding.

We first give a trivial solution which has complexity O(N^2). We enumerate the integers in the given order, and adopt a hash table to record the integers that have been visited. When we are visiting a[i], we should find out the number of integers such that a[k]>a[i] with k<i, denoted as Head[i], and also the number of integers such that a[i]>a[j] with i<j, denoted as Tail[i]. It can be seen that the required answer is just Head[0]*Tail[0]+Head[1]*Tail[1]+...Head[n-1]*Tail[n-1]. To find out Head[i], we just query the hash table to count the number of recorded integers that are larger than a[i]. To find out Tail[i], we can enumerate the integers in a reversal order, and adopt another hash table. When we are visiting a[i] (note that reversal order), similarly we query the hash table but should find out the number of stored integers which are less than a[i].

However, the above solution has complexity O(N^2). Specifically, the first "N" comes from the enumeration of array a[n], which cannot be avoided. The second "N" comes from the query of hash table, which can be reduced to logN by using the Segment Tree technique. The trick is that when we try to count the number of stored integers which are larger (or less) than a[i], it is equivalent to adding all the "flags" and the sum is just the answer (for instance, we set flag=1 to denote that some integer has been visited while flag=0 means that it has not been visited), and Segment Tree technique can reduce the complexity of computing the sum to O(logN). Therefore, whenever we are using hash table to store the integers that we have visited, and we have to frequently query the hash table to find out the total number of some special integers, it is perhaps the right time to use Segment Tree technique.

Finally, one might have noticed that in many problems, often the range of integers is quite large compared with the total number of elements. To alleviate this dilemma, we can map the elements to a "new" but "small" range, and I think one can also find a lot of information about this step on the internet, which might be referred to as discretization.

Read more »