pleasurepain's blog

By pleasurepain, 24 hours ago, In English,

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.

Read more »

 
 
 
 

By pleasurepain, 3 days ago, In English,

129A - Cookies

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.

129C - Statues

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.

Read more »

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

By pleasurepain, 5 days ago, In English,

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

127D - Password

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.

127E - E-reader Display

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

Read more »

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

By pleasurepain, 11 days ago, In English,

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.

Read more »

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

By pleasurepain, 12 days ago, In English,

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.

Read more »

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

By pleasurepain, 3 weeks ago, In English,

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.

Read more »

 
 
 
 

By pleasurepain, 3 weeks ago, In English,

118A - String Task

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

118E - Bertown roads

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.

Read more »

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

By pleasurepain, 3 weeks ago, In English,

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.

Read more »

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

By pleasurepain, 4 weeks ago, In English,

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.

Read more »

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

By pleasurepain, 5 weeks ago, In English,

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 - Уроки грамматики

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 - Счастье на двоих

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.

Read more »

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

By pleasurepain, 5 weeks ago, In English,

112A - Петя и строки

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

112B - Петя и квадрат

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 - Петя и неравенства

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 - Петя и делители

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.

Read more »

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

By pleasurepain, 6 weeks ago, In English,

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.

Read more »

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

By pleasurepain, 6 weeks ago, In English,

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.

108D - Basketball Team

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.

Read more »

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

By pleasurepain, 7 weeks ago, In English,

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

Read more »

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

By pleasurepain, 2 months ago, In English,

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.

Read more »

 
 
 
 

By pleasurepain, 2 months 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, 2 months 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, 2 months 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, 2 months 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 months ago, In English,

94A - Восстановление пароля

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 - Друзья

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 - Рамочки

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 - Окончание сессии

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 - Аземблер

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 - Лостборн

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 months 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 months 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, 3 months 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, 3 months 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, 3 months 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