### pleasurepain's blog

By pleasurepain, 6 months ago, ,

A. Presents

This problem can be solved by starting from the 0-th day and implement the following operations.

For the i-th day (initially i=0), we check the next K days, i.e., from (i+1)-th to (i+K)-th day. If no holidays are included, we increase the number of presents by one and move to the (i+K)-th day; otherwise we add the number of holidays to the current number of presents and move to the last holiday. Note that if i+K>N, it is sufficient to only count the number of holidays from the i-th day to the N-th day, and add it to the number of presents.

B. Cutting Jigsaw Puzzle

The solution is straightforward but might be a little complicated to code.

At first, we should enumerate all the feasible sizes of pieces. A size with x*y is feasible if x and y are factors of A and B, respectively. For each feasible size x*y, we find out all the pieces and check if there exist any two pieces that are exactly the same. Any two pieces are exactly the same if at least one of the following conditions can be satisfied:

1) They are the same without any rotations;

2) They are the same if the second one is rotated with 180 degrees;

3) They are the same if the second one is rotated with 90 degrees;

4) They are the same if the second one is rotated with 270 degrees;

If there are not any two pieces that are the same, then this size x*y results in a good puzzle, and we should further record the minimum size according to the requirements.

C. First Digit Law

This problem can be divided into two subproblems.

Subproblem 1): given the interval [L,R], how to count the number of integers whose most significant digit is 1? Suppose that F(n) is a function which calculates the number of integers from 1 to n, and thus this subproblem can be solved by computing F(R)-F(L). To implement such a function, we can try 1,10,100,...,10^m, until 10^m<=n, and the answer will be 1+10+100+...+10^(m-1)+min(10^m, n-10^m+1). Moreover, we can immediately calculate the probability of selecting an integer whose most significant digit is 1 as (F(R)-F(L))/(R-L+1);

Subproblem 2): given N events and the probability that every event occurs, how to calculate the probability that at least K of them occur? A straightforward method that enumerates all the feasible combination may fail since the number is likely to be quite huge. However, we can use DP, like Pascal's Triangle, to avoid the above difficulty. We use D[n][m] to denote the probability that for the first n events, exactly m of them occur. One can check that D[n][m]=D[n-1][m-1]*p[n]+D[n-1][m]*(1-p[n]), where p[n] denotes the probability that the n-th event occurs, while the initialization is done by setting D[0][0]=1. Then, the answer is just D[N][K]+D[N][K+1]+...+D[N][N].

By pleasurepain, 6 months ago, ,

A. Autocomplete

We can enumerate all the given strings, and for each one that has the required beginning, we select the lexicographically minimal one as the answer.

B. Blog Photo

The problem requires that at least one of the sides should have a length of form 2^n. Thus, we can first let the length of height have a form of 2^n,2^(n-1),...,2^0, where 2^n should be no larger than h. For each height=2^i, we calculate the largest length of width so that it will not exceed the given w and meanwhile the area can achieve the maximum value. Next, we let the length of width have a form of 2^n,2^(n-1),...,2^0, and calculate the height in a similar manner.

As an example, we investigate how to calculate the width, denoted as W, given that the current length of height is H=2^i. Due to the constraints, we have 0.8<=H/W<=1.25, which means that H/1.25<=W<=H/0.8. As both the height and width are integers, one might use ceil(H/1.25)<=W<=floor(H/0.8) to obtain the values that W can take. However, this may lead to some unexpected precision problem. In fact, we can completely avoid this problem by using the "integer division" and "integer module" operations.

We can solve a more general problem, which gives two decimal numbers a and b (like 0.64, 0.2347, etc.) and an already known integer X, and we are asked to find out the exact range of values that another integer Y can take with the constraints that a*X<=Y<=b*X. We first transform a and b into a fractional form, i.e., a=p/q, b=s/t. Note that this is always possible. For instance, we can transform 0.2347 into 2347/10000, and the fractional form does not have to be irreducible. Then, we also transform the original constraints into

p*X/q<=Y<=s*X/t

Therefore, floor(b*X)=s*X/t, where the '/' in s*X/t is an "integer division" operation. For p*X/q, if (p*X)%q==0, we can directly use p*X/q as the lower bound, where '/' in p*X/q is an "integer division" operation, too; otherwise, ceil(a*X)=p*X/q+1, where '/' in p*X/q is still an "integer division" operation. In summary, the upper bound is s*X/t while the lower bound is ((p*X)%q==0?p*X/q:p*X/q+1).

Now, we go back to the original problem. As we still have another constraint 1<=W<=w, if ceil(H/1.25)>w, it means that we cannot obtain a reasonable value for the width; otherwise, the maximal value of width is just min(w,floor(H/0.8)). After we obtain the width, we first compare the area and then the height, and select the answer carefully as the problem requires.

C. Little Frog

For the given n integers 1,2,3,...,n, we can immediately find out that the absolute difference between any two integers is at least 1 while at most n-1. The problem asks to arrange the n integers in an appropriate order Q so that the absolute difference between any two neighboring integers should not be the same. Note that we will have n-1 absolute differences, and if they are all different from each other, they have to be exactly S={1,2,3,,,n-1}.

Note that the absolute difference can be at most n-1, which is achieved if and only if 1 is next to n or n is next to 1. Therefore, we can first set Q=(1,n) and S is reduced to S={1,2,3,,,n-2}. Similarly, one can check that to obtain the absolute difference n-2, we have to put 2 next to n, which gives Q=(1,n,2) and S is reduced to S={1,2,3,,,n-3}. Again, we deal with the absolute difference n-3, and one can find that Q=(1,n,2,n-1) and S is reduced to S={1,2,3,,,n-4}. In summary, we deal with S in a decreasing order, and when S is reduced to empty set, we will have obtained the required sequence Q.

D. Physical Education

This is like Selection Sort. We start from the first value of a and check whether it is the same as the first value of b. If they are the same, we move to the second one; otherwise, we enumerate array b from the second value and find out the one at some position j that is the same as the first value of array a. Then, we swap the value at position j with the second one. The swap is implemented like Bubble Sort, and the process should be recorded as part of the final answer. Similarly, we deal with the other values one by one, and will finally obtain the required answer.

•
• +5
•

By pleasurepain, 6 months ago, ,

A. 123-sequence

Suppose that the number of integers 1, 2 and 3 are denoted as x[1], x[2] and x[3]. To obtain the minimum number of replacements, we should find out the minimum value among x[1]+x[2], x[1]+x[3] and x[2]+x[3], and output it as the answer. One could also find out the maximum value of x[3], x[2] and x[1], and then use x[1]+x[2]+x[3]-x[i] as the answer.

B. Right Triangles

We count the number of right triangles based on the intersection from which two sides that form a 90 degree extend. We use R[r] to denote the number of '*' in the r-th row, and C[c] to denote the number of '*' in the c-th column. Then, if we select any '*' as the point where two sides that form a 90 degree intersect with each other, the number of different right triangles is just (R[r]-1)*(C[c]-1). The reason is that the first side can be selected from all the (R[r]-1) points at the current row, except for the intersection. Similarly, the second side can be selected from all the (C[c]-1) points. Therefore, we can enumerate all the '*' points, and add the corresponding (R[r]-1)*(C[c]-1) together, which is the final answer.

C. Circular RMQ

I find out that this is a famoue RMQ problem, where range minimum query is asked, with range modification, i.e., increase all the elements belonging to some range by the same constant number.

I searched on the internet, however only found out some materials that did not provide quite many details talking about how to solve such a problem (Most of them just show the codes but without many arguments or principles...). May any coders recommend me some articles talking about this :D 52C - Circular RMQ

•
• +3
•

By pleasurepain, 7 months ago, ,

A. Cheaterius's Problem

We can adopt a linear array a[4] to denote any 2*2 square, with a[0] being the upper left cell, a[1] being the upper right cell, a[2] being the bottom left cell and a[3] being the bottom right cell. Then, the rotation of 0, 90, 180 and 270 degrees can be viewed as a circular shift of array a[4], with length of 0, 1, 2 and 3. Therefore, for any two squares, they are exactly the same if one of them can be obtained by implementing a circular shift with some length to the other one.

B. bHTML Tables Analisys

One can check that whenever we meet a '', it means that we have met a new cell. Thus, we can adopt a variable S to count the number of cells that we have met. Note that when we detect a '', it means that all the cells that we have counted should belong to this table. Therefore, we can store the current value of S, and set it to zero again, since the following cells, if there are any, should belong to some other table.

C. Three Base Stations

We use x[0],x[1],...,x[n-1] to denote the cities, counted from left to right. Assume that the center of the most left circle is located at position t, and the radius is R. Then, if t-R<x[0], we can always update t by t'=t+x[0]-(t-R), i.e., the circle is moved to the right, and all the cities that have been covered by the original circle can surely be covered by the new one as well. This implies that for any optimal solution, the center of the most left circle must be located at position x[0]+R, while that of the most right circle is located at position x[n-1]-R.

With the above arguments, we can use binary search to find out the optimal radius R. Specifically, we use R_L and R_R to denote the lower bound and upper bound, respectively, and we check R_M=(R_L+R_R)/2 can cover all the cities or not. We start from x[0], and find out the first city x[s] that satisfies x[s]>x[0]+2*R_M. Similarly, we start from x[n-1] and find out the first city x[t] that satisfies x[t]<x[n-1]-2*R_M. Note that there may not exist such a position s or t, but if they both exist, we can check whether x[t]-x[s]<=2*R_M holds or not. If it holds, it means that the current radius R_M is large enough to cover all the cities, and thus we should update R_R=R_M for the next implementation of binary search; otherwise we should modify R_L as R_L=R_M. To achieve the requirement of precision, we can find a value T that satisfies (R_R-R_L)/2^T<E, where R_R and R_L are the initialized values before implementing binary search, and E is the inaccuracy. Thus, it is sufficient to implement binary search for T times.

D. Geometrical problem

Instead of using a[i]/a[i-1] to calculate the common ratio, I suggest using a[i]*a[i]=a[i-1]*a[i+1] to determine whether it is a geometric series or not.

We start from index i=1 to i=n-2, and test a[i]*a[i]=a[i-1]*a[i+1] for every index i. We adopt another array s[i], and use s[i]=0 to denote that a[i]*a[i]=a[i-1]*a[i+1] holds; otherwise we set s[i]=1. Note that only s[1],s[2],...,s[n-2] are assigned values. To check whether it is possible to form a geometric series by deleting a single element, we can just try to delete from the first one to the last one, and test whether all the left elements can satisfy a[i]*a[i]=a[i-1]*a[i+1]. To avoid Time Limited Error, we should introduce another two arrays, prefix[n] and suffix[n]. We use prefix[i] to denote that all the elements with indices no larger than i satisfy a[i]*a[i]=a[i-1]*a[i+1], while using suffix[i] to denote that all the elements with indices no less than i satisfy a[i]*a[i]=a[i-1]*a[i+1]. With the help of prefix[n] and suffix[n], we can claim that the sequence forms a geometric series after deleting some element a[i] based on the following conditions:

1) prefix[i-2]==0;

2) suffix[i+2]==0;

3) a[i-1]*a[i-1]==a[i-2]*a[i+1];

4) a[i+1]*a[i+1]==a[i-1]*a[i+2];

Nevertheless, we still need to take special care of the following two cases:

Case 1) if n is two, it is always a geometric series unless that the first element is zero but the second one is not;

Case 2) if a[i-1]=a[i]=0 but a[i+1]!=0, although a[i]*a[i]=a[i-1]*a[i+1] holds, it is still not a geometric series, and thus s[i] should be set to 1 rather than 0.

By pleasurepain, 7 months ago, ,

A. Domino piling

If at least one of M and N is an even number, then the answer will be m*n/2; otherwise exactly one square cannot be covered, and gives (m*n-1)/2 as the answer. Nevertheless, by using integer division, m*n/2 will give the correct result for both the case.

B. Choosing Symbol Pairs

For a given string, we should calculate how many times a character has appeared in it. If a character 'c' has appeared for a[c] times, then the answer is just the sum of a[c]*a[c] where all the characters that have appeared should be considered.

C. Happy Farm 5

At first, I chose to "scan" first from left to right, and then from right to left, and during this process, I tried to find out the convex hull and record its length. However, this kept failing even though I have tried a lot of times...

Finally, I studied the codes from the other coders, and found out that most of them had used a quite simple method. The main idea is to first draw two lines with -45 degree, and one of them should pass the most upper right point while the other one should pass the most bottom left point. Similarly, we draw another two lines with +45 degree, and let one of them pass the most upper left point while the other one pass the most bottom right point. These four lines will form a rectangular (this is not always true, for instance if only one point exists, however it does not affect the following results), and the answer is just the perimeter plus 4. This works from an intuitive understanding, however I cannot figure out how to prove that it always works.

D. Bombing

I think two programming techniques are involved in this problem.

1) For given N events and the probabilities that each of them occurs, how to calculate the probability that at least K of them occur? A direct enumeration might fail since C(N,K), which means the number of diffierent ways to choose K elements from N elements, turns out to be quite large even for N=100 and K=50. An efficient solution is to use Dynamic Programming to calculate the result. We use Pr[n][m] to denote the probability that among the n events, exactly m of them occur. One can check that this can be computed according to the recursion

Pr[n][m]=Pr[n-1][m-1]*p[n]+Pr[n-1][m]*(1-p[n])

where p[n] denotes the probability that the n-th event occurs. With this recursion, we can calculate Pr[i][j] for every feasible i and j. Then, the required result is Pr[N][K]+Pr[N][K+1]+...+Pr[N][N].

2) Binary serach with required precision. The problem asks to compute the minimum radius R which can meet the requirement. We can start with R1=0 and R2=4000, and then check Rm=(R1+R2)/2 and update the values for the next loop according to the current results. The frequently used termination condition in binary search, i.e., the value that we have found out is exactly equal to the target value, cannot work successfully if we are dealing with "float" number rather than "integer" number. Instead, we can limit the maximum number of implementing the binary search to achieve a similar effect. If we set the maximum number of binary search to T, then the total search space M has been divided into 2^T intervals and each of them has length M/(2^T). To achieve the precision requirement, for instance, an absolute inaccuracy less than some E, we can just choose an appropriate value of T which can satisfy that M/(2^T)<=E.

E. Square Equation Roots

At first, we write the roots as -b+sqrt(b^2-c) and -b-sqrt(b^2-c), and consider the conditions under which two different pairs (b1,c1) and (b2,c2) can have at least one same root. Suppose that -b1+sqrt(b1^2-c1) and -b2+sqrt(b2^2-c2) are the same. If both sqrt(b1^2-c1) and sqrt(b2^2-c2) are not rational numbers, then we must have b1=b2 and b1^2-c1=b2^2-c2, which gives that b1=b2 and c1=c2. Therefore, no different pairs of (b1,c1) and (b2,c2) can have at least one same root unless both sqrt(b1^2-c1) and sqrt(b2^2-c2) are rational numbers.

With the above arguments, for each b, any c that results in an irrational value of sqrt(b^2-c) will contribute two different roots, while for the other c, their roots will form two integer intervals as we will see later. Therefore, we can first implement a loop for b, and for each b, we adopt the following steps:

1) Compute the maximum value that c can take, i.e., c<=c_min=min(b^2,m);

2) Compute all the feasible c that can result in a rational value of sqrt(b^2-c); suppose that x^2=b^2-c, then c=b^2-x^2, and thus 1<=b^2-x^2<=c_min, which gives ceil{sqrt(b^2-c_min)}<=x<=b-1; if ceil{sqrt(b^2-c_min)}<=b-1, we will have num2=b-1-ceil{sqrt(b^2-c_min)}+1 values of c that leads to a rational value of sqrt(b^2-c);

3) For those values of c that lead to an irrational value of sqrt(b^2-c), they will contribute 2*(c_min-num2) different roots to the final answer; while for the other values of c, it can be seen that the roots are -b+x and -b-x, with x belonging to [ceil{sqrt(b^2-c_min)}, b-1]; for convience, we can add 2b to the original roots to "move" all the intervals to the right so that we can adopt a hash table to record the intervals; therefore, we have obtained two intervals [b+ceil{sqrt(b^2-c_min)}， b+b-1] and [b-(b-1), b-ceil{sqrt(b^2-c_min)}], which just give the corresponding roots;

4) As we can have at most 5000000 values of b, it will cost a huge complexity if we "map" each point of an interval into the hash table; instead, for some interval [S,T], we can just set H[S]++ and H[T+1]--, where H[ ] denotes the hash table; when all the intervals have been processed, we scan from the start of the hash table to the end and calculate the prefix sum; the number of non-zero prefix sum is just the number of different points that all the intervals can cover up; intuitively, H[S]++ means that a new interval has began at point S while H[T+1]-- implies that some interval has just terminated at point T+1; whenever the prefix sum is larger than zero, it means that the current point is still covered by at least one interval.

•
• +3
•

By pleasurepain, 7 months ago, ,

A. Sleuth

Be careful that only the last letter rather than the last character that determines the answer. Therefore, we can scan the string from the last character to the first one, and stop immediately when a Latin letter is met.

B. Sum

At first, we find out the largest digit that has appeared in the two integers, and denote it as B. Thus, the base must be strictly larger than B. If we want to achieve a longer length of the sum, the only hope is that the carry at the most significant position can be "1" but not "0", which in fact implies that the base should be too large. Therefore, we can just adopt B+1 as the base, and the following work is to simulate the operations of adding up the two integers. If the carry at the most significant position is "1", the answer will be the longest length of the given two integers plus by 1; otherwise it is just the longest length of the two integers.

C. Disposition

The description of the problem seems a little bit difficult to understand. It actually asks that to arrange integers from 1 to n in an appropriate manner so that the total number of such pairs, a[i] and i, which are relatively prime, are as many as possible, where a[i] denotes one of the integers from 1 to n. A simple solution might be a[n] = {n, 1, 2, 3,...,n-1}, and one can check that all the pairs a[i] and i are relatively prime (note that the index i starts from 1 but not 0).

D. Game

For this problem, it seems a little complicated to figure out how to select two neighbouring cells at each step. However, if we start from the final state and consider what should be done to move from the initial state to the final one, the solution is straightforward.

As the final sequence cannot have any two neighbouring cells that are both 0 or 1, there are only two feasible candiate sequences, i.e., 01010.... and 101010.... Therefore, we first assume that s[0] is correct, and then we alter the following values to satisfy that s[2i]=s[0] while s[2i+1]=(s[0]+1)%2, and meanwhile count the number of operations as C1. Be careful that we can only alter one cell if and only if at least one of its two neighbouring cells have the same value. Thus, it is likely that the target state (or sequence) cannot be achieved. Similarly, we next assume that s[0] is not correct, and then the following values should be changed so that s[2i]=(s[0]+1)%2 and s[2i+1]=s[0] hold, and count the number of operations as C2. Finally, we calculate min(C1,C2) and output it as the answer.

•
• -3
•

By pleasurepain, 7 months ago, ,

A. Triangular numbers

An integer n is a triangular number if we can find such an integer m that n=m*(m+1)/2. As n is not larger than 500, we can enumerate all integers from 1 to 1000 (not necessarily 1000, for instance 500 is also enough) and check whether we can find such an integer m or not.

B. Coins

If a team T wins against another one, we can add one point for team T. Thus, for team A, B and C, if they have points with forms of {0,1,2}, the results are not contradictory; otherwise this is impossible.

C. Crossword

A little bit complicated problem for me..

As there are only 6 words, we can enumerate all the feasible 6!=720 patterns and check if they can form a reasonable crossword puzzle. Without loss of generality, we denote the 6 strings as s[6], and further assume that s[0], s[2], s[4] are parallelly placed while the other three strings are vertically placed. Thus, a reasonable crossword puzzle should satisfy the following several conditions:

1) The total length of s[0] and s[4] is exactly the same as that of s[2], and the total length of s[1] and s[5] is the same as that of s[3] as well;

2) s[0], s[2], s[4] can be connected one by one, i.e., the last letter of the former one is exactly the same as the first letter of the latter one (so as s[1], s[3] and s[5]);

3) The first letters of s[0] and s[1] are the same while the last letters of s[4] and s[5] are the same;

4) The common letters of s[2] and s[3] are the same;

If all the above conditions can be satisfied, we have obtained a reasonable crossword puzzle, and by storing the lexicographically minimum one, we obtain the answer.

D. Safe

This problem can be solved by using a tree search algorithm with branch and bound, i.e., only some of the nodes in the tree are visited while the others are not visited by cutting off some branches (or subtrees).

We actually try to enumerate all the feasible code patterns, whose number is at most 2^35, a huge amount. Specifically, we start from the leftmost position, and for each feasible value (in fact only 0 or 1), we move on to the next position and select one feasible value as well (also 0 or 1) until the rightmost position is determined. At each position, we also check all the given m attempts. For each attempt, if the value is "correct", we decrease the system's reponse by 1 while do nothing if it is "incorrect". Note that if some of the system's responses are reduced to some negative integers, it means that the current code pattern, although there may still exist several positions that have not been enumerated, can definitely not be a feasible one since contradictions have been observed. Therefore, the current enumeration can be immediately terminated. In fact, the enumeration of code patterns can be viewed as a search in a complete binary tree with 2^n leaf nodes, and these leaf nodes just correspond to all the candidate code patterns. The termination mentioned above is equivalent to cutting off branches when we are implementing search in the binary tree, so that we can avoid visiting some of the leaf nodes and possibly some intermediate nodes. As a result, the complexity may be less than 2^n.

The complexity for the worst case is difficult to analyze, since the cutting off of branches is an implicit process and it depends on the specific structures of each attempt. However, for each attempt, due to its constraints on the code patterns, at most C(n,k) ones are feasible, where C(n,k) means n!/(n-k)!/k!. Therefore, we have at most m*C(n,k)<=10*C(35,6) code patterns that can serve as feasible ones. Intuitively, this implies that the complexity may be about 10*C(35,6), however this is just my guess... The solution based on this idea has been accepted, so I think that at least the test cases are not "difficult" ones for such a solution, but I cannot guarantee that there exist no test cases that this solution will fail or give a "Time Limited Error".

•
• +1
•

By pleasurepain, 7 months ago, ,

A. Football

This is one feasible solution. We can use the "map<string, int>" provided by C++ to record the number of goals for each team. Moreover, we should also store the name of the two teams, i.e., the two strings (note that it is likely to have only one string appearing in the input). Then, we just compare the number of goals for each team and output the answer.

B. Letter

We can use "getline(cin,s)" provided by C++ to deal with a string containing blank space as input. We first deal with the input s1 and use the "hash" idea to record the number of letters that have appeared. Note that the blank space should not be considered as the problem requires. Then, we deal with the input s2 and similarly adopt the "hash" idea to record the number of letters appearing in s2. Finally, for each letter that has appeared in s2, we check whether s1 has provided enough such a letter or not.

C. Lucky Tickets

For an integer, it is divisible by 3 if and only if the sum of its digits is divisible by 3. A simple proof is that we write the integer as

A=a0*10^0+a1*10^1+...an*10^n

=a1*(10^1-1)+a2*(10^2-1)+...an*(10^n-1)+(a0+a1+a2+...an)

It is obvious that a1*(10^1-1)+a2*(10^2-1)+...an*(10^n-1) is divisible by 3 and thus the conclusion is straightforward.

Therefore, we can count the number of tickets that are divisible by 3 as x, and the number of tickets divided by 3 resulting in a remainder 1 and 2 as y and z, respectively. The answer is x/2+min(y,z), where "/" is integer division.

D. Journey

One can first prove that if both n and m are odd integers, we can definitely not return back to (1,1) without using any teleporter. The proof is based on painting colors. We first paint (1,1) with black and the next cell that we move to with white. Then, for the following steps, we just paint the cells with black and white in an alternative manner. As we visit each cell exactly once except for (1,1), this means that if we successfully achieve this goal, the last cell we reach must be painted with white color, which is contradictory with the fact that we have painted (1,1) with black color. Furthermore, we can always construct a feasible route for the case where at least one of n and m is an even number, and thus the solution can be summarized as follows:

1) Both n and m are odd integers. We start from (1,1) and visit all the cells in the first row and then the second row and so on. At last, we will always reach the cell (n,m), and by building a teleporter at cell (n,m) we can return back to (1,1);

2) At least one of n and m is an even integer. Without loss of generality, assume that n is an even number. We start from (1,1) and move on to (1,m). Then, we visit all the cells in the second row except for (2,1), i.e., we will reach cell (2,2). Next, we go to (3,2) and move on until we reach (3,m). In a word, we just visit the cells row by row but leaving the first column unvisited. Finally, we will surely arrive at (n,2). By visiting the first column, we just return back to (1,1) without using any teleporter.

Note that there exist several special cases. One case is (n=1, m>2), or (m=1, n>2). For this case, we have to build a teleporter at cell (n,m) and then can return back to (1,1). Another case is (n=1,m=2), or (n=2,m=1), where no teleporter is necessary.

E. Race

As both n is not quite large, we can count the number of "lead" for every two cars, which contributes O(n^2) complexity. For the i-th car and j-th car, we adopt two pointers pi and pj to enumerate (or scan) their time segments independently. Moveover, we adopt a "flag" to denote which car is leading over another one. We first find out the shortest time segment T for the current pi and pj, and use it to compute the current distance of the two cars. Then, we compare which car is leading over another one and update the number of "lead" accordingly. Finally, we should decrease the two time segments with T, and if any of them is reduced to zero, we just add pi or pj by 1 so that we move on to check the next time segment. As these operations will change the original values of time segments, we should backup them before implementing such operations so that when we deal with another two cars, the time segments are not "zero". By some simple amortized analysis, the total complexity is O(n^2*k).

I think for this problem, the most difficult step is how to "scan" any two time segments in an efficient and correct manner.

•
• +4
•

By pleasurepain, 7 months ago, ,

A. Guilty — to the kitchen!

Suppose that the maximum volume is x, and then we can derive several inequalities that x should satisfy.

1) For each index i, x*a[i]/(a[1]+a[2]+a[3]+...a[N])<=b[i], where "/" means float division;

2) x<=V

Therefore, x=min(V, min(b[i]*(a[1]+a[2]+a[3]+...a[N])/a[i]) )=min(V, (a[1]+a[2]+a[3]+...a[N])*min(b[i]/a[i])). This implies that we can first find out the minimum value of b[i]/a[i], and then the answer is straightforward.

B. Game of chess unfinished

For each rook, we can calculate the positions that it can take. Note that the white king (or another rook) might serve as an obstacle and thus "protect" some positions from being taken by the current rook, even though these positions lie in the same row or column as the rook. For instance, consider a rook with "b2" and a white king with "b4", in which case all positions with "b5,b6,b7,b8" cannot be taken by this rook (however they may be taken by another rook or the white king). Similarly, we can obtain the positions that the white king can take as well.

Now, we can first check whether the white has checkmated the black. Then, we move the black king to the eight adjacent positions (if these positions are reasonable), and check whether it will be taken by the white or not. As long as there exists one sinlge position at which the black king can avoid being taken by the white, the answer is "OTHER". Note that one of the white rooks might be taken by the black king, as the problem says.

C. Safe cracking

Well, this is a somewhat weird problem...

A feasible solution is shown as follows:

1) if all the four integers are reduced to 1, stops; otherwise go to step 2);

2) find out the maximum integer a[max_n] and denote its left and right integer as a[L] and a[R], respectively. Then, select one of the following branches to implement:

A) a[max_n]%2=0: if at least one of a[L] and a[R] is an even integer, divide it and a[max_n] by 2 (if they are both even integers, we can select the larger one); if both of them are odd integers, increase the larger one and a[max_n] by 1; after this, go to step 1);

B) a[max_n]%2=1: if at least one of a[L] and a[R] is an odd integer, increase it and a[max_n] by 1 (if they are both odd integers, we can select the larger one); if both of them are even integers, increase the larger one and a[max_n] by 1; after this, go to step 1);

In genreal, for a given integer N, by dividing it by 2, it takes us log(N) times to reduce it to 1. However, sometimes the intermediate result may turn out to be an odd integer and it might take 3 more times to go on with division. For instance, a[L] is even; a[max_n] is odd; a[R] is even. Therefore, it takes 4*(3*log(N)) operations, which is about

4*(3*log(10^9))<=12*log((2^4)^9)=12*36=432<1000

D. Strange town

I was inspired by the other solutions. Suppose that we assign an integer a[i] to node with index i. Then, for two nodes i and j, if we assign a value a[i]+a[j] to the edge between node i and node j, one can check that for any Hamilton cycle, the total value will always be 2*(a[1]+a[2]+...a[N]), which just meets the request in the problem. Therefore, the problem is solved if we can guarantee that there exists no a[i]+a[j] that is equal to any other a[s]+a[t]. Specifically, we can adopt the "hash idea" to record all the values of a[i]+a[j] that have been appeared for the first N-1 nodes, and for the N-th node, we can enumerate from 1 to 1000 to select an appropriate integer for a[N], which leads to no contradiction, and finally update the "hash table" for the newly added a[N].

Well, this is really a wonderful solution which transforms the original problem into a simpler one, but how could the first person come up with such an idea.....

•
• +5
•

By pleasurepain, 7 months ago, ,

A. Translation

This is a simple problem. If the two strings have different length, then the answer must be "NO"; otherwise, we just reverse one of the strings and compare whether they are exactly the same or not.

B. Martian Dollar

A straightforward solution is to first enumerate the days when to sell, and for the i-th day, enumerate all days from the first one to the i-th one and find out the j-th day when one can buy with the cheapest price, where 1=<j<=i. Then, the money will be b%a[j]+b/a[j]*a[i], where "x/y" means "integer division". Finally, we output the maximum value as the answer. This solution has complexity O(N^2). However, we can further reduce it to O(N). The idea is to build another array p[N], where p[i] denotes the minimum value of a[0],a[1],...,a[i]. p[0] is initialized as p[0]=a[0], while p[i] can be computed as p[i]=min(a[i],p[i-1]), which takes O(N) complexity. Thus, if we sell on the i-th day, the money will be b%a[i]+b/p[i]*a[i], and the maximum one is just the answer. The total complexity will be O(N).

A feasible solution consists of the following steps:

1) change all the "dot" into '.';

2) change all the "at" into '@';

3) if the first or the last character is '.', then change it back to "dot"; while if the first or the last character is '@', change it back to "at" as well;

4) if there exists any other '@', change all of them back to 'at' except for the first one.

D. Pawn

A nice DP problem for a competitive programming beginner like me.

We use an array F[n][m][k+1] to implement the DP algorithm, where F[r][c][z] denotes the maximum value one can obtain in the r-th row and c-th column while the remainder divided by k+1 is z. Suppose that another array b[r][c] denotes the number of peas initially given in the r-th row and c-th column. Then,

F[r][c][z]=max(F[r-1][c-1][z-b[r][c]%(k+1)], F[r-1][c+1][z-b[r][c]%(k+1)]).

Remember to check whether the position (r-1,c-1) or (r-1,c+1) is a reasonable one or not. One should also note that if z-b[r][c]%(k+1) turns out to be a negative integer, modify it as z-b[r][c]%(k+1)+k+1. Once we have completed filling every cell of F[n][m][k+1] with a reasonable value, we can obtain the answer by finding out the maximum one of F[1][c][0], where c=1,2,...,m. Furthermore, we should adopt another array S[n][m][k+1] to store the steps by which we can reach the maximum value. The value of S[r][c][z] can immediately be computed when we update F[r][c][z], i.e.,

if F[r-1][c-1][z-b[r][c]%(k+1)]>F[r-1][c+1][z-b[r][c]%(k+1)], then S[r][c][z]=c-1;

if F[r-1][c-1][z-b[r][c]%(k+1)]<=F[r-1][c+1][z-b[r][c]%(k+1)], then S[r][c][z]=c+1.

When we trace back the steps, we can start from the first row, i.e., S[1][max_c][0], where max_c denotes the column in which we obtain the answer, and if S[1][max_c][0]=c-1, we move to S[2][max_c-1][0-b[1][max_c]%(k+1)]; otherwise we go to S[2][max_c+1][0-b[1][max_c]%(k+1)]. Similarly, if 0-b[1][max_c]%(k+1)<0, we just modify it by 0-b[1][max_c]%(k+1)+k+1.

E. 3-cycles

A famous problem in graph theory, and the solution is referred to as Turan's theorem. The original problem investigated by Turan's theorem is a more general one, which gives n points and asks what is the maximum number of edges one can connect while under the condition that the graph is (r+1)-cycle free. One can search on the internet to find some details about this problem. For this special one, the answer is just (n/2)*(n-n/2) with "/" meaning "integer division".

By pleasurepain, 8 months ago, ,

A. Find Color

As the problem has stressed that all the points locating at the border of any areas are considered to be black, if x==0 or y==0, the answer will be black. For the other points, we should find out a radius r which satisfies that

(r-1)^2 < x^2+y^2 <= r^2

Then, if x^2+y^2 == r^2, the answer is black as well. For x^2+y^2 < r^2, we can consider the following two cases:

1) r%2==0, if x*y>0, the answer is white; otherwise is black;

2) r%2==1, if x*y>0, the answer is black; otherwise is white.

B. Repaintings

By some careful induction, we will find that the original problem is equivalent to the following one:

For a chessboard with a=n-(x-1)*2 rows and b=m-(x-1)*2 columns, how many black squares are there on the four edges, given that the square at the left upper corner is black?

The solution can be divided into the following steps:

1) Count the number of black squares in the first row. It is straightforward to find that the number is (b+1)/2.

2) Count the number of black squares in the last row. The number turns out to be (b+1)/2-(a+1)%2.

3) Count the number of black squares in the first column, which should be (a+1)/2.

4) Count the number of black squares in the last column, which is (a+1)/2-(b+1)%2.

5) Count the number of black squares at the four corners, if they have been repeatedly counted. Left upper corner: 1; Left bottom corner: a%2; Right upper corner: b%2; Right bottom corner: (b%2+a%2-1).

Therefore, the answer should be (b+1)/2+(b+1)/2-(a+1)%2+(a+1)/2+(a+1)/2-(b+1)%2-1-a%2-b%2-(b%2+a%2-1). However, a special case where a=b=1 is not included in the above formula, and also note that if a<=0 or b<=0, the answer is 0 as well.

E. Number Table

An interesting problem!!

The hint  k < max(n, m) might shed some light on how to think about the solution. Suppose that the table has been filled with +1 and -1, and met the requirement as well. Then, we try to multiply all the +1 and -1 together. At first, we implement this operation column by column to obtain (-1)^m, and similarly repeating it row by row will give (-1)^n. Thus, (-1)^m=(-1)^n, and this means that (m+n)%2=0 must be satisfied, and it serves as a necessary condition.

We will first deal with the case n<m. As  k < max(n, m), it implies that there must be at least one column in which no cells are preserved, while for the other columns, some or even all of the cells have been filled with some +1 and -1. An intuitive idea is to first fill the columns except for the one in which absolutely no cells are preserved (there may exist multiple such columns, but it is sufficient to consider only one of them). It is obvious that these m-1 columns can always meet the requirement, and then we try to fill the special column. It is obvious again that all the n rows can meet the requirement. The only question to ask is that whether the special column can meet the requirement or not. In fact, the answer is YES, and the proof is as follows:

Proof: We use A[i][j] to denote the value in the i-th row and j-th column. According to our operations, it has been guaranteed that A[1][j]*A[2][j]*A[3][j]*...*A[n][j]=-1 holds for all the columns except for the special one. Without loss of generality, we denote the special column as A[ ][s]. Furthermore, we also have A[i][1]*A[i][2]*A[i][3]*...*A[i][m]=-1. Therefore, we multiply all the values row by row and will obtain

A[1][1]*A[1][2]*A[1][3]*...*A[1][m]*

A[2][1]*A[2][2]*A[2][3]*...*A[2][m]*

...

A[n][1]*A[n][2]*A[n][3]*...*A[n][m]=(-1)^n

If we combine them column by column, we have (-1)^(m-1)*A[1][s]*A[2][s]*A[3][s]*...*A[n][s]=(-1)^n, and thus A[1][s]*A[2][s]*A[3][s]*...*A[n][s]=(-1)^(n+m-1)=(-1)^(n+m)*(-1)=-1.

According to the above arguments, the problem can be solved by the following steps:

1) check if (n+m)%2=0 holds or not;

2) fill the preserved cells with the corresponding values, and if for some column, all the cells are preserved, we should check whether the column meet the requirement or not;

3) calculate the number of feasible combination of +1 and -1 for all the columns except for the special one, and multiply the results together.

Finally, we have to deal with another two small problems. The first one is that if n>m, we can swap the value of n and m, but be careful that we should swap the values of a and b as well. The second problem is that for some column possibly filled with +1 or -1 in some preserved cells, how to calculate the number of different methods to fill the left cells. Suppose that we have N cells to fill with +1 or -1. The number can be calculated according to the following two cases, where C(x,y) means the number of feasible combination by choosing y elements from the total x ones.

1) an even number of -1 should be filled, which gives S1=C(N,1)+C(N,3)+...C(N,2k-1)+...;

2) an odd number of -1 should be filled, which leads to S2=C(N,2)+C(N,4)+...C(N,2k)+...;

Now we are going to prove that both S1 and S2 are equal to 2^(N-1).

Proof: we first consider (1+1)^N=sum{C(N,i)(1)^i(1)(N-i)}=C(N,1)+C(N,3)+...C(N,2k-1)+...+C(N,2)+C(N,4)+...C(N,2k)+...=S1+S2=2^N. Then, we consider (1-1)^N=sum{C(N,i)(-1)^i(1)(N-i)}=S2-S1=0. Therefore, S1=S2=2^N/2=2^(N-1).

•
• +3
•

By pleasurepain, 8 months ago, ,

A. Towers

As the range of N is from 1 to 1000, we can adopt a "hash table" to record how many times an integer appears. Then, to find the height of the largest tower, it is sufficient to find the integer that has appeared for the most times, and the times it appears is just the answer. The total number of towers is just the number of distinguishing integers.

B. Computer Game

This is really a tricky problem. We should use several variables to record and update "states", which include:

1) The current health point of the boss at each second, denoted as Cur_HP;

2) The accumulated damage that has been cast on the boss for each second, denoted as Damage.

With the above variables, we can simulate what happens from the zero second to some T-th second (the value of T will be discussed later). At each second, we first calculate Cur_HP-Damgae, and if the result is negative or zero, we can immediately terminate the simulation since the boss has been defeated. On the contrary, we increase Cur_HP-Damgae by the regeneration rate and obtain the updated health point of the boss; however we should remember that the updated health point cannot be larger than the initial amount of health. Then, we enumerate the scrolls and find out the one that satisfies the following conditions: it has not been used; it can be used according to the given rules; it can lead to the largest damage. Then, we update the value of variable Damage, and move on to the next second.

Finally, we consider up to what time is sufficient to implement the above simulation, i.e., what value should T have, since if T is too small we may not get the right result while otherwise may lead to a Time Limited Error. The initial amount of health point of the boss is at most 1000, and if Damage becomes larger than the regeneration rate by only 1 at the 1000-th second, then it takes another 1000 seconds to defeat the boss. Therefore, the simulation should be implemented for at least 2000 seconds, and we had better set it to 3000 seconds, just in case.

C. Old Berland Language

This is a problem about prefix code, which is often related to the uniquely decodable codes in Coding Theory, or Information Theory.

A well known method is to establish a binary tree, whose left branch and right branch denote 0 and 1, respectively. For any node, we can obtain a code sequence consisting of 0 and 1 by walking along the branches from the root node to the current one. Whenever we obtain a code sequence, we should cut off all the child nodes rooted at the current node to guarantee the "prefix code" property.

However, for this problem, the above idea perhaps cannot be directly applied since N, which corresponds to the height of the tree, is up to 1000 and thus intractable as far as I consider. In fact, it might not be necessary to explicitly build such a tree, since the total number of each code sequence will not exceed 1000. One straightforward solution is to build a set which only contains a null string "" at first. Then, we enumerate from length-0 to length-1000, and for each length, we first take out the required number of code sequence (if we cannot it means that the answer is "NO") and then for each unused code sequence, we append '0' and '1' to obtain two new sequences for the next length.

•
• +2
•

By pleasurepain, 8 months ago, ,

A. Extra-terrestrial Intelligence

As the size n is no larger than 100, we can adopt a "vector" to record the indices of "1" which appear in the given sequence. Then, we calculate the difference between every two neighbouring indices, and if they are the same, the answer is "YES"; otherwise is "NO".

B. Fractal

This problem reminds me of Kronecker Product, which is often mentioned in the theory of matrix. In fact, this problem just asks to simulate the operation of Kronecker Product as far as I consider. For the first provided example, if we replace '.' with integer "1" while '*' with integer "0", we will obtain a matrix [1 0 ; 1 1]. If you are familiar with Matlab, you can use the function "kron" to calculate the finla matrix, and by mapping "1" and "0" back to '.' and '*', you will find that it is just the answer!! This conclusion holds for all values of n and k.

D. New Game with a Chess Piece

This is a rather complicated problem...

We might need do some pen and paper work to find out some principles hidden behind the game. We can start from the right bottom point, and consider the result if one should start moving from this point. For simplicity, we use 'L' and 'W' to denote that one loses and wins, respectively, if he starts from some point, and we use an array R[n][m] to record the results.

At first, we consider the case where k>1. Obviously, R[n-1][m-1]='L', and R[n-1][m-2]='W',R[n-1][m-3]='L'. This means that for the (n-1)-th row, 'L' and 'W' appear alternatively, and similarly one will find that for the (m-1)-th column, 'L' and 'W' appear alternatively as well. Then, we consider what happens in the (n-2)-th row. One will find that R[n-2][m-2]='L' since only R[n-1][m-2]=R[n-2][m-1]='W' can be reached from this point, i.e., the next person who moves will win. By some careful deduction, one will find that 'L' and 'W' appear alternatively for the (n-2)-th row and (m-2)-th column. In fact, this holds from the (n-1)-th row to the (n-k)-th row. For the (n-k-1)-th row, we can find that it is always 'W' from R[n-k-1][0] to R[n-k-1][m-k-1]. From the (n-k-2)-th row to the (n-(2*k+2))-th row, 'L' and 'W' appear alternatively again. In fact, we will find that from the (n-(2*k+2+1))-th row, the same pattern as that starts from the (n-1)-th row repeats. Therefore, we can calculate min(n,m)%(2*k+2) and find out which row between the (n-1)-th one and the (n-(2*k+2))-th it belongs to, and select 'L' or 'W' according to whether |n-m| is even or odd.

Then, we consider the case that k=1, which is quite similar to k>1. We also start from the (n-1)-th row and find out the corresponding pattern, and then move up to the upper row until we find that the same pattern starts to repeat.

•
• +6
•

By pleasurepain, 8 months ago, ,

A. Alphabet Cake

I solved this problem by first filling the array row by row, and then column by column.

For each row, at first I enumerate from the first element to the last one until I find an element that is not '?', and then break the loop. If such an element that is not '?' does not exist, it means that this row consists of only '?'. Such a row is skipped, however do not worry since it will be implemented later. Now suppose that we have found such an element which is not '?' and denote it as a variable x (char x;). Then, I enumerate from the first element again, and

1) when a '?' is met, just replace it with x;

2) when x is met (note that x must be the first letter that is met, since I immediately break the loop when the first element that is not '?' is found), do nothing (or replace it with x, which achieves the same result);

3) when a letter different from x is met, just update x with this letter, and go to step 1).

After the above operations, for instance, ???A??B??CD? will be changed into AAAAAABBBCDD. However, it can not cover the case where some row consists of only '?', and thus we repeat the above operations again column by column, i.e., the three steps are exactly the same but the enumeration is implemented in a column.

For instance,

???A??B??CD?

????????????

E????F???GHI

will be first changed into

AAAAAABBBCDD

????????????

EEEEEFFFFGHI

then

AAAAAABBBCDD

AAAAAABBBCDD

EEEEEFFFFGHI

B. Ratatouille

Well, this is a tough problem for me. At first, I could not figure out how to solve large input so I wrote a special version for small input. It was about 15 minutes before the end that I finally realized how to deal with N>2...

At first, we should consider under what conditions that two packages corresponding to different ingredients can be used to constitute a kit (or can be paired). For some given two packages, we denote the quantity they contain as Q1 and Q2, while the number of corresponding ingredients are R1 and R2. If we want to use Q1, we must find some integer K1 that satisfies R1*0.9*K1<=Q1<=R1*1.1*K1, and similarly R2*0.9*K2<=Q2<=R2*1.1*K2 if we want to use Q2. Therefore, if both Q1 and Q2 can be used as a kit, there must be at least one common integer K that satisfies K1=K=K2. Moreover, it is not necessary to find out such a precise K since we can find out the intervals that K1 and K2 falls into, respectively, and then check whether the two intervals intersect with each other or not. If they intersect with each other, it means that at least one common integer K=K1=K2 can be found. According to R1*0.9*K1<=Q1<=R1*1.1*K1, we have Q1/(1.1*R1)=<K1<=Q1/(0.9*R1). Note that the "double division" should be avoided since otherwise you might get stuck in "precision problem". We can multiply both denominator and nominator by 10, which gives (10*Q1)/(11*R1)<=K1<=(10*Q1)/(9*R1). Then, as K1 is an integer, we can use "integer division" to obtain the lower bound (inclusive) as (10*Q1)/(11*R1)+((10*Q1)%(11*R1)!=0), and the upper bound (inclusive) as (10*Q1)/(9*R1), where the '/' is "integer division". Therefore, we can check whether the intervals [(10*Q1)/(11*R1)+((10*Q1)%(11*R1)!=0), (10*Q1)/(9*R1)] and [(10*Q2)/(11*R2)+((10*Q2)%(11*R2)!=0), (10*Q2)/(9*R2)] intersect with each other or not.

Then, suppose that there are only two ingredients, and we consider how the corresponding packages can be "paired" to achieve the maximum number of pairs (or kits). We adopt a greedy idea. We adopt an array Q[N][P] (specifically N=2), where Q[i][j] denotes the quantity of the j-th package corresponding to the i-th ingredient. We first sort the packages in an increasing order of their quantities for each ingredient, i.e., Q[i][0]<=Q[i][1]<=...Q[i][P-1]. Then, we enumerate from the first package to the last one for the 0-th ingredient (a simple example will be shown later). For each enumerated package Q[0][j1], we enumerate from the first package to the last one for the 1-th ingredient, and find out the first one Q[1][j2] that can be paired with Q[0][j1]. Then, we break the loop for Q[1][j2] and go back to the loop for Q[0][j1]. However, for this time, when we deal with Q[0][j1+1], we should start from Q[1][j2+1] but not Q[1][0]. The correctness of such greedy idea can be proved but omitted here. Here is a simple example. Suppose that we have

Q[0][0], Q[0][1], Q[0][2], Q[0][3]

Q[1][0], Q[1][1], Q[1][2], Q[1][3]

We first deal with Q[0][0], and try from Q[1][0] to Q[1][3] one by one, and assume that Q[1][1] is the first one which can be "paired" with Q[0][0]. Then, we deal with Q[0][1], and try from Q[1][2] to Q[1][3], and assume that Q[1][3] is "paired" with Q[0][1]. Then, for Q[0][2] and Q[0][3], they cannot be "paired".

Finally, I introduced a "flag" array to denote whether a package has been selected to be "paired" with some other package or not, i.e., flag[N][P] where flag[i][j]=0 means that the j-th package corresponding to the i-th ingredient is not "paired" while flag[i][j]=1 means that it is "paired" with some package corresponding to the (i+1)-th ingredient. With such a "flag", I can deal with N>3 case. For Q[N][P], I enumerate from N-2 to 0, and for each Q[i][j1], I use the above greedy idea to find out which Q[i+1][j2] can be "paired" with Q[i][j1]. The 'can be "paired"' condition is: Q[i+1][j2] intersects with Q[i][j1] (recall the intervals mentioned above) and flag[i+1][j2]==1. Specifically, the row of flag[N-1][ ] is initialized with all "1" values. When Q[i][j1] is "paired", I update flag[i][j1]=1. Here is a simple example:

Q[0][0], Q[0][1], Q[0][2], Q[0][3]

Q[1][0], Q[1][1], Q[1][2], Q[1][3]

Q[2][0], Q[2][1], Q[2][2], Q[2][3]

with flag as

0, 0, 0, 0

0, 0, 0, 0

1, 1, 1, 1

We first deal with the 1-th row and 2-th row. For Q[1][0], we try from Q[2][0] to Q[2][3] and find Q[2][1] "paired" with Q[1][0], then flag is changed into

0, 0, 0, 0

1, 0, 0, 0

1, 1, 1, 1

For Q[1][1], we try from Q[2][2] to Q[2][3] and find no Q[2][] "paired" with Q[1][1], then nothing is doen.

For Q[1][2], we try from Q[2][2] to Q[2][3] and find no Q[2][3] "paired" with Q[1][2], then the flag is changed into

0, 0, 0, 0

1, 0, 1, 0

1, 1, 1, 1

For Q[1][3], it cannot be "paired". Then, we deal with Q[0][0], and try from Q[1][0] to Q[1][3] but note that Q[1][1] and Q[1][3] must be skipped since flag[1][1]=flag[1][3]=0. Assume that Q[0][0] is not "paired", and then we move on to Q[0][1], and try from Q[1][0] to Q[1][3] (Q[1][1] and Q[1][3] are skipped), and suppose that Q[1][2] is "paired", then the flag is changed into

0, 1, 0, 0

1, 0, 1, 0

1, 1, 1, 1

For Q[0][2] to Q[0][3], they cannot be "paired".

The answer is just the number of "1" in the 0-th row of flag, i.e., 0+1+0+0=1. I think this is similar to the idea of dynamic programming. To constitue as many kits as possible, the packages corresponding to the last row (ingredient) Q[N-1][ ] must be "paired" with some other ones. Thus, we start from Q[N-2][ ] and Q[N-1][ ], and try to find out as many "pairs" as possible. Then, we deal with Q[N-3][ ] and Q[N-2][ ], but the "pairs" must be made based on the "pairs" already exist in Q[N-2][ ], which is indicated by flag[N-2][ ]. The last row flag[N-1][ ] is initialized with all "1" since for Q[N-2][ ], any Q[N-1][ ] can be selected without any restriction. This implies that the number of "1" in flag[0][ ] is just the maximum number of kits (pairs). Finally, I deal with N=1 as a special case.

•
• -22
•

By pleasurepain, 8 months ago, ,

A. Shell Game

The solution is straightforward by swapping the integers as required by the problem.

B. Warehouse

The warehouse can be viewed as a two-dimensional array. If '+1' is met, we just enumerate the positions from the given one to the final one in the order required by the problem, and put the drink into the first empty box if there exist any. If '-1' is met, we can enumerate from the first position to the final one, and if any one that has the same ID is found, we just output the corresponding position; otherwise output "-1 -1".

C. Fire Again

Suppose that the position at which the fire begins is denoted as (f1,f2). Then, for any position (r,c), the fire gets to it after time |r-f1|+|c-f2|, which is referred to as Manhattan Distance as far as I consider. Therefore, we can first enumerate the positions where fire starts, and for each such position, we enumerate every feasible position and calculate the time when the fire arrives at it. As all the fires start at the same time, we should only record the shortest time when the fire gets to some position during the above enumerating process. Finally, we enumerate all the positions again and find out which is the last one that the fires reach. The total complexity is O(NMK).

Later, I noticed that some people used another simpler method. The formula |r-f1|+|c-f2| in fact has shed some light on this idea. It can be observed that the first term |r-f1| and the second one |c-f2| are independent of each other. Therefore, it is not necessary to enumerate positions "r" and "c" at the same time, but can be implemented respectively. In other words, we can first enumerate "r" and record the time when the fire gets to it, and then repeat this for "c". Finally, we find out the largest "r" and "c", and combine them as the position, which serves as the answer.

D. Animals

As provided by the problem, c[1],c[2],...,c[n] denotes the food that an animal eats every day if it arrives at the farm on the i-th day. We can further calculate the total amount of food that an animal eats if it joins the farm, which can be written as f[1],f[2],....,f[n], where f[i]=c[i]*(n-i+1). As the problem asks to find out the maximum number of animals that can join the farm, it is equivalent to maximizing the number of terms in the sum f[i1]+f[i2]...+f[im] under the condition that f[i1]+f[i2]...+f[im]<=X. Therefore, we can first sort f[1],f[2],....,f[n] in an increasing order of their values. Then, we enumerate from the first one and count the number at the same time until the sum exactly exceeds X. The number just serves as the answer.

By pleasurepain, 8 months ago, ,

A. Reconnaissance 2

This problem asks to find out two neighbouring elements with the minimum difference. Specifically, the difference between the first element and the last one should be taken into consideration as well.

B. Sale

Bob can only earn money by "buying" those TVs with negative price. Therefore, we can sort all the TVs in an increasing order of their price, and denote the number of TVs with negative price as M. Then, we add the prices of the first min{M,m} TVs together to obtain the final answer.

C. Page Numbers

This problem is straightforward however a little bit complicated. As the largest page number does not exceed 1000, we can adopt a "hash table" to record which pages have appeared in the sequence. At first, we should calculate the exact page number from the given sequence. Then, we set the value of hash table corresponding to the current page number to 1 to denote that this page is required to print. Finally, we enumerate the hash table from the first index to the last one. Whenever we meet a "1", we check whether the next one is "1" or not. If it is, then we move on to check the following one until we meet a "0", and output them in a "i-j" manner; otherwise we directly output the current page number. Take care of the position at which we should output a comma ','.

This problem is in fact equivalent to reversing a single linked list.

The map can be viewed as a tree, and thus the representation of the road provides the parent node for each node. Suppose that we write the connection relationship between r2 to the original root node r1 as r2->A->B->...->r1. When the root node is changed from r1 to r2, it can be observed that only the parent nodes of r2,A,B,...,r1 should be altered. More specifically, the connection should be altered as r2<-A<-B...<-r1. Therefore, it is sufficient to reverse such a single linked list with complexity O(n).

By pleasurepain, 8 months ago, ,

A. What is for dinner?

The problem in fact asks to find out the minimum number in each row. As the number of rows is not quite large, less than 1000, we can adopt an array to record the minimum integer in each row, i.e., whenever a new integer is added to some row, we compare it with the previously stored integer and update the entry with the smaller one. Finally, we add up the minimum integer in each row together, and obtain the possibly "maximum amount of crucians". By comparing it with k, we select the smaller one as the output.

B. String Problem

Well, I got stuck in this problem for a quite long time, until I realized that not only can we change letter A into B or B into A, but also we can change both A and B into some other letter C, which may achieve a smaller sum of money...

This problem can be solved based on graph, where a letter is viewed as a node. The solution can be summarized as the following several steps:

1) Whenever a possible changing from letter A to B is provided, we can build a directed edge from A to B with the money as the cost; as more than one directed edge from A to B might be provided, we should only store the one with minimum cost to avoid multiple edges between any two nodes;

2) Implement the famous "Floyd-Algorithm" to calculate the shortest path between any two nodes; here is a simple example; suppose that letter 'a' can be changed into 'b' with cost 2 while 'b' can be changed into 'c' with cost 1; then 'a' can be changed into 'c' with cost 3, which can be updated by floyd-algorithm;

3) Compare each letter in string s1 with that in string s2; whenever they are different, enumerate every feasible changing, i.e., from letter 'a' to 'z', and select the one with the minimum cost as the common letter into which both letters should be changed.

C. Wonderful Randomized Sum

At first, we consider what form will the optimal option have. In fact, we can prove that the optimal prefix and suffix should not intersect with each other, since if they do, the integers belonging to the intersection will be multiplied by -1 for two times, which just gives their original values, and this results in a new prefix and suffix which do not intersect with each other at all. Therefore, the optimal prefix and suffix should not intersect.

Inspired by the above arguments, we can immediately come up with a straightforward method that enumerates the ending position of prefix and starting position of suffix, and find out the optimal one. However, this takes O(n^2) complexity, and it will almost surely lead to a Time-Limited-Error. To avoid this, we can try to reduce the number of enumeration, which actually turns out to work successfully by only enumerating the starting position of suffix. For each starting position of suffix, the original problem is equivalent to finding out the optimal prefix, which can be computed previously. The optimal prefix is in fact the one which has the minimum sum, since by multiplying -1 it turns out to be the maximum sum. However, this conclusion holds only if the minimum sum is less than 0, i.e., if no sum of prefix is less than 0, the optimal prefix is just empty.

Suppose that we use prefix[n] to denote the sum of a[0]+a[1]+...+a[n], which can be computed with complexity O(n) by using prefix[n]=prefix[n-1]+a[n]. Then, we use min_prefix[n] to denote the minimum sum of some prefix with ending position before n or at n. The initialization can be implemented by min_prefix[0]=min{a[0], 0}, and generally we have min_prefix[n]= min {prefix[n], min_prefix[n-1]}. Moreover, we use suffix[j] to denote the sum of a[n]+a[n-1]+...a[n-j], which can be calculated with complexity O(n) in a similar manner as computing prefix[n].

Now, we are ready to solve the problem. For each starting position j of suffix, the current maximum sum is just (prefix[n]-suffix[j]-min_prefix[j-1]) + (-min_prefix[j-1]) + (-suffix[j]). The maximum sum obtained during the enumeration of j serves as the final answer, which takes O(n) complexity.

D. Knights

This problem turns out to be not quite difficult if we have realized that it in fact asks to compute the total number of distinguishing circles that encircle the given two points.

At first, we sort the circles in an increasing order of their radiuses with complexity O(mlogm). Then, for each point, we calculate the number of circles that encircle it with complexity O(nm). Finally, we count the number of different circles that encircle the requested two points with complexity O(km). Thus, the total complexity is O(km). (I have hearded of an offline Tarjan' algorithm which can be used to solve this problem, also known as Lowest-Common-Ancestor problem)

•
• -11
•

By pleasurepain, 8 months ago, ,

A. Reconnaissance

The solution to this problem is straightforward. As it is stressed that (i,j) and (j,i) are different, we can adopt a nested-2-loop to enumerate all the feasible combination of i and j, and check whether the difference of height satisfy the condition or not.

B. Borze

The problem is simplified since it is guaranteed that the given sequence is valid Borze code. We can enumerate the letters from the first one, and implement the decoding according to the following rules:

Rule 1): whenever we meet a '.', decode it as "0" and move to the next letter;

Rule 2): whenever we meet a '-' and the next one is '-' as well, decode it as "2" and skip the next letter and move directly to the one following it;

Rule 3): whenever we meet a '-' and the next one is '.' as well, decode it as "1" and skip the next letter and move directly to the one following it;

C. Flea

Note that at first the flea is at the center of the cell, and no matter how it jumps later, it should always stay at the center of some cell. Therefore, although there are n*m cells, the board can in fact be viewed as a grid with (n-1)*(m-1) points and the flea can only jump from one single point to the other ones. Suppose that the flea first starts from point (1,1), then it can jump to point ( 1+(m-1)/s*s, 1) along the parallel axis, while jumping to point ( 1, 1+(n-1)/s*s ) along the perpendicular axis (note that only "integer division" is included here, i.e., 5/2=2 but not 2.5). Therefore, we have found out ( (m-1)/s+1 )*( (n-1)/s+1 ) points which are completely equivalent to each other. Note that (m-1)/s*s<(m-1) might hold since we adopt "integer division", and the different is just (m-1)%s. This implies that if the flea starts from points (2,1), (3,1),...( 1+(m-1)%s, 1 ), it can also cover ( (m-1)/s+1 )*( (n-1)/s+1 ) points. Similarly, it leads to the same result if it starts from points (1,2), (1,3), ... ( 1+(n-1)%s, 1). Therefore, there are totally ( (m-1)/s+1 )*( (n-1)/s+1 ) * ( 1+(n-1)%s )*( 1+(m-1)%s ) points which are equivalent, and this is just the answer.

D. Constellation

At first sight, it seems that we should find out all the reasonable constellation and then sort them as the problem asks, while taking out the k-th one as the answer. However, we soonly realize that the number might be too large to store. In fact, we can just enumerate the constellation one by one in the order requested by the problem, by adopting a nested-3-loop. At first, we enumerate every feasible x, which will not exceed max(n,m) (in fact it might be half of max(n,m), but later you will find that this constant 1/2 is not important as ususally done in the analysis of computational complexity), then for the second loop, we enumerate indices i from 1 to n (or 0 to n-1), and the third loop deals with j from 1 to m. Whenever we find a reasonable constellation, we increase the "counter" by 1, and when the k-th constellation is reached, we store the positions of the five stars, and give the final answer, while outputing "-1" if the counter is still less than k after the last reasonable constellation is counted.

•
• -2
•

By pleasurepain, 9 months ago, ,

A. Worms Evolution

As n is at most as large as 100, we can adopt a nested-3-loop to find out the answer, i.e., we enumerate all the possible positions of i, j and k in turn, and check whether the condition a[i]=a[j]+a[k] can be satisfied or not. One more thing to notice is that i, j and k should be three distinct integers.

This problem is not quite difficult but one should be very careful.

At first, notice that if '@' appears at the first position or the last position, the answer will be "No solution". Then, if there exist any two successive positions i and i+1 with s[i]=s[i+1]='@', the answer should be "No solution" as well. Except for this, if one can find out two positions i and i+2 with s[i]=s[i+2]='@', it also results in "No solution". Finally, if no '@' can be found, the answer is still "No solution".

After excluding the above cases, all the other cases should have reasonable answers. Without loss of generality, once we have reached the first letter following '@', we can immediately add ',' to obtain a reasonable solution. However, there is one exception, i.e., no ',' shoulbe be added after the last '@'.

C. Schedule

At first, we can sort the groups in an increasing order of the starting time of their lessons. Then, we enumerate the groups from the first one to the last one, and for each group, we check whether it is possible to achieve the state where no two time periods of lessons intersect by deleting this group. The test can be simply implemented by comparing the i-th group and (i+1)-th group, for every feasible i. In other words, we check whether the finishing time of group i is later than the starting time of group i+1, and if all the pairs lead to answers "NO", then it means that the remaining groups can achieve the state at which no two time periods of lessons intersect.

D. Chocolate

I solve this problem by using a divide-and-conquer technique. I also find that many people solved this problem based on DFS. But I do not quite understand the principle behind this idea. It would be very nice if anyone can shed some light on this idea...

I adopt an array perpendicular[x1][y1][y2] to denote that there is a line with two ends (x1,y1) and (x2=x1,y2). Similarly, I use another array parallel[y1][x1][x2] to denote a line with ends (x1,y1) and (x2,y2=y1). Then, we can start with the whole plane, i.e., (x1=0,y1=0,x2=W,y2=H), and try to calculate the areas, which consists of the following three phases:

phase 1): enumerate x from x1+1 to x2-1 (note that x1 and x2 are not included since the problem guarantees that the plane is cut into two pieces which are not empty) and check whether perpendicular[x][y1][y2]=1 or not. If perpendicular[x][y1][y2]=1, it implies that the current considered piece is cut into at least another two pieces since there is a line with two ends (x,y1) and (x,y2). Thus, we can divide it into two subproblems (x1,x,y1,y2) and (x,x2,y1,y2);

phase 2): enumerate y from y1+1 to y2-1 (similar reasons as above), and check whether parallel[y][x1][x2]=1 or not. If parallel[y][x1][x2]=1, it means that the current piece is cut into at least another two pieces by a line with ends (x1,y) and (x2,y). Thus, it can be divided into two subproblems (x1,x2,y1,y) and (x1,x2,y,y2);

phase 3): no lines cut the current piece and it stays as it is. We can directly calculate the area by (x2-x1)*(y2-y1), which is referred to as "conquer".

Finally, we sort the areas as the problem requests and output them.

E. TV Game

This problem can be solved by adopting a dynamic programming technique. We use F[x][y] to denote that for the first x+y digits, x of them are taken by person H while y of them are taken by person M, and the value of F[x][y] is the maximum sum that can be achieved. Suppose that by giving the (x+y)-th digit to H will increase the sum by number(x+y,H) while giving to M leads to an increment number(x+y,M). Then, F[x][y] is only determined by F[x-1][y] and F[x][y-1]. In detail, F[x][y]=MAX(F[x-1][y]+number(x+y,H), F[x][y-1]+number(x+y,M)). F[][] is initialized by setting F[0][1]=number(1,M) and F[1][0]=number(1,H). When updating F[x][y], we should implement this process by increasing x+y from 1 to 2n, i.e., first update all F[x][y] with x+y=2, then x+y=3, and finally x+y=2n. To record the digits taken by H and M, we can further introduce another array R[x][y], which is initialized by setting R[0][1]='M' and R[1][0]='H'. R[x][y] is updated as F[x][y] is calculated, i.e., if F[x-1][y]+number(x+y,H)>F[x][y-1]+number(x+y,M), then we have R[x][y]='H'; otherwise R[x][y]='M'. Finally, we start with F[n][n], also R[n][n], and backtrack until F[0][0] is reached. This can be implemented by comparing F[x-1][y]+number(x+y,H) and F[x][y-1]+number(x+y,M), and then we know which one to backtrack.

•
• +6
•

By pleasurepain, 9 months ago, ,

A. Accounting

This problem asks to find out a feasible solution to the equation A*X^n=B. This can be solved based on the following cases:

1) A=0, B!=0: this results in no solution;

2) A=0, B=0: any integer can serve as a feasible solution;

3) A!=0, B%A!=0: this leads to no solution;

4) A!=0, B%A=0, A*B<0, n%2=0: this means that X^n should be a negative integer, however this is impossible since any X^n with n%2=0 must be a positive integer;

5) A!=0, B%A=0, A*B<0, n%2=1: this is equivalent to finding out a solution to A*X^n=(-B), which turns out to be case 6);

6) A!=0, B%A=0, A*B>0: as both the values of A and B are limited to be less than 1000, we can enumerate X from 1 in an increasing order until A*X^n>=B is satisfied. Then, for this X, by checking whether A*X^n=B holds or not, we can obtain the final answer.

B. Codeforces World Finals

This problem is a little complicated to deal with. To obtain the final answer, we have to check all the feasible 3*2*1=6 dates when Bob "can be born". As the number of permutation is rather small, we can previously generate it with an array

int permutation[6][3]={ {0,1,2}, {0,2,1}, {1,0,2}, {1,2,0}, {2,0,1}, {2,1,0} };

to simplify the following operations. Besides, we can store the number of days in each month by using two arrays as well, one for leap year and one for nonleap year:

int nonleap[12]={31,28,31,30,31,30,31,31,30,31,30,31};

int leap[12]={31,29,31,30,31,30,31,31,30,31,30,31};

For each feasible permutation, we generate the birthday of Bob, and first check whether the month is between 1 and 12, and then check whether the day is between 1 and the last date of this month, to guarantee that this is a reasonable birthday. Then, we compare it with the date of the final. The comparison can be implemented in the order of year, month and day. Take care that all the above operations should be implemented for leap year and nonleap year, respectively.

C. Shooting Gallery

At first, we should sort all the targets in an increasing order of the time of their appearance. From now on, we assume that the sorting has been completed and the following arguments are all based on the sorted targets.

Then, we can solve the problem based on dynamic programming. It asks to compute the maximum expected value of the amount of targets, and this is in fact equivalent to finding out the the maximum sum of pi we can obtain. We use f[n] to denote the maximum sum of pi we can obtain when the n-th target is exactly hit. Then, we consider what might happen before the n-th target is hit. We can directly aim at the n-th target from the first start while skipping the previous n-1 targets. Besides, we might have hit the i-th target, where i<n, and immediately move to the n-th target. Therefore, f[n] can be calculated in the following manner. For each f[i], i<n, we calculate the time it takes to move from target-i to target-n, and if this time is shorter than the interval between which they appear before and after, we compare f[i]+p[n] with the current value of f[n], and select the larger one to update f[n]. Do not forget that we can aim at the n-th target from the first start. Thus, f[n] cannot be less than p[n], and p[n] can just be used to initialize the value of f[n].

Finally, we find out the maximum one of f[1],f[2],...,f[n], and it just serves as the answer.

•
• +6
•

By pleasurepain, 9 months ago, ,

A. Spit Problem

For a camel with given parameters x[i] and d[i], he (or it) can hit at position x[i]+d[i] according to the problem. As the number of camels is at most up to 100, it is feasible to check for any two camels whether they can hit each other or not.

B. Traffic Lights

When the car arrives at the traffic light, if it is green, then the car can move on as if there were no traffic lights; while if it is red, the car has to wait until the light turns to be green, and then it can reach the destination. Therefore, the key point is in fact to determine whether the car has to wait or not, and if yes, how much time should it wait for.

We can take the total time that green light and red light lasts as an entirety (or a cycle), i.e., t=g+r, and then we should find out at which cycle does the car reach the traffic light. At first, we compute k=d/((g+r)*v), where "integer division" is adopted. The value of k means that when the car reaches the traffic light, it takes at least k cycles. Then, the problem can be solved based on the following two cases:

1) (g+r)*v*k<=d && d<(g+r)*v*k+v*g: this means that when the car arrives at the traffic light, it is green, and thus the car can directly pass the light and the total time is l/v (mathematical division, or 1.0*l/v);

2) d>=(g+r)*v*count+v*g: this means that when the car reaches the traffic light, it is red, and the car has to wait for (g+r)*(k+1)-1.0*d/v, and therefore, the total time is (g+r)*(k+1)-1.0*d/v+1.0*l/v.

C. Mail Stamps

The indices of cities are integers from 1 to 10^9, which makes it difficult to directly deal with since the indices are too large. Thus, we can adopt a 'map<int , int>' (Standard Template Library in C++) to reduce the indices to a smaller range, i.e., from 1 to 10^5, due to that n is up to 10^5. Whenever a city is processed, we can use function ".find(key)" to check whether this index (or called key) has occurred before or not, if no, we can map this index to a smaller one. As ".find(key)" is implemented based on a binary search (perhaps a balanced binary tree), the complexity O(logN) is fast enough. Moreover, we should maintain another array reverse[n] to indicate the real index corresponding to the one after mapping, i.e., reverse[value]=key, to output the correct route.

After the above process, the left problem is relatively simpler. We can establish a graph, in fact a link, and implement a traversal from any starting city to obtain the route. The starting city can be found by checking the degree of each city after the graph is established. As the problem guarantees, there should be exactly two cities with degree one, and any one of them can serve as the starting city.

D. Ant on the Tree

This problem can be solved by directly visiting the leaf nodes in the requested order. At first, we can establish an adjacency matrix to indicate the connection relationship. Then, the nodes with degree one are leaf nodes (note that the root node may have degree one as well, and take care for this case). Then, we can implement a BFS (Breadth First Search) to generate another array parent_node[] which stores the parent node of any node. Specifically, the parent node of root node can be set to -1.

Next, we go to the first leaf node. This route just starts from the root node and ends at the leaf node, which is not difficult to find out. Then, we move from one leaf node leaf[i] to the next one leaf[i+1]. With the help of parent_node[], we can find the nearest common parent node of leaf[i] and leaf[i+1]. Then, the route first starts from leaf[i] and ends at this common parent node, and then moves on to leaf[i+1]. For the last leaf node leaf[k-1], the route starts from leaf[k-1] and ends at the root node. During the above process, we can count how many times one edge has been visited. If some edge has been visited for more than two times, then the answer is "-1"; while on the other hand, the requested route exists, and we can directly output the route that has been stored before.

•
• -9
•

By pleasurepain, 9 months ago, ,

Well, this is a tough round...

A. Bender Problem

The description of this problem might seem to be a little bit complicated, however, it turns out to be not that difficult as it looks like. Using a mathematical language, at first we have n points, and they can be connected only in the order as they are given. Then, we have m segments, and for each of them, we can fold it at any points to form an angle of 90 degrees. The problem asks to find out whether it is feasible to connect all the given points by using the provided m segments while any folded position must overlap with some one of the given points.

Suppose that we connect the n points (0,1,2,...,n-1) in the order as they are given, and denote the segments as a[0],a[1],...a[n-1]. Now, we consider the condition under which the given n points can be precisely connected by only using the provided segments. As the segment is folded at some position, it can cover exactly two segments of a[0],a[1],...a[n-1]. Thus, we have the following two cases.

1) (a[0],a[1]), (a[2],a[3]),...,(a[n-2],a[n-1]) are paired, which implies that we should have segments whose length is a[0]+a[1], a[2]+a[3],....,a[n-2]+a[n-1]. Therefore, we can check whether the provided m segments contain all the requested length, and if it is "YES", the folded position is thus 1,3,5,...,n-1;

2) (a[1],a[2]), (a[3],a[4]),...,(a[n-3],a[n-2]), (a[n-1],a[0]) are paired, which means that the provided m segments contain the length a[1]+a[2], a[3]+a[4], .... a[n-1]+a[0], the answer is "YES", and the folded position is 2,4,6,...,n-2,0;

As the maximum length is no longer than 200 000, we can adopt the hash idea to store the number of rods for some given length, and check whether one the above two cases can be satisfied.

B. pSort

At first, we provide some claims which might help to understand the problem. We use A->B->C to denote that A can directly interchange with B, but cannot directly interchange with C.

Claim 1: Suppose that a chain A->X[1]->X[2]->....->X[m]->B exists for some integer m. Then, we can interchange A with B without changing the positions of the other elements.

Proof: As A->X[1]->X[2]->....->X[m]->B, by first interchanging A with X[1], we obtain X[1],A,X[2],....,X[m],B. By repeating the above operations for m+1 times, we have X[1],X[2],....,X[m],B,A. Then, we interchange B with X[m] to get X[1],X[2],....,B,X[m],A, and by repeating this operation for m times, we arrive at the state B,X[1],X[2],...,A.

According to the problem, the i-th cell can interchange with cells i+di and i-di, while take care that these two positions may not be reasonable (out of the range). Therefore, we can form one or several independent chains as in Claim 1. The given permutation in fact asks to interchange some A with B while not affecting the other elements. According to Claim 1, if both A and B belong to the same chain, they can successfully interchange with each other. Thererfore, the problem is equivalent to finding out whether a pair of two elements that are requested to interchange with each other belongs to the same chain or not.

We can adopt the union-find idea to solve the problem. At first, the root of each element is itself, i.e., they belong to their own chain. When we deal with i and di, we may find that two elements can interchange with each other and thus should belong to the same chain. To achieve this, we find out the root of the two elements, and connect one root to the other one (which serves as the root does not matter). Finally, when we deal with the permutation sequence, we just check the roots of any two elements that should interchange with each other, and if they are the same, the ans is "YES"; otherwise it is "NO".

•
• +1
•

By pleasurepain, 9 months ago, ,

A. Next Test

As the range of input size is only up to 3000, we can maintain an array to indicate which number has appeared in the given test. Then, we enumerate this array from index 1 to n, and the first number that cannot be found is the answer.

B. Tournament

It seems that there exist some other simpler methods than mine... The key idea of my solution is to build a directed graph. The players can be viewed as nodes in a directed graph, and node A has en edge directed to node B if we can find a match in which A wins against B. Then, we can maintain an array to count the number of matches that a player has participated in. It is straightforward that we will find out two players who have only participated in n-2 matches while the other ones all have participated in n-1 matches. After finding out the two players, without of loss generality, we denote them as A and B, and then we implement "graph traversal" for two times witht the starting point as A and B, respectively. If we can reach node B from node A, then it means that A wins against B, or if we can reach node A from node B, it implies that B wins against A. However, we might arrive at the third case where we cannot reach B from A or reach A from B, either. For this case, it means that we cannot tell who wins against whom based on the results of provided matches, and we can select any result as the answer.

C. Unordered Subsequence

It is easy to find out that if unordered subsequence exists, the shortest length should always be 3. Assuming that the shortest length should be some integer larger than 3, without loss of generality, we write the subsequence as x[1],x[2],...x[m], where m>3. Now, let us focus on the first three elements. Their relationship can only be x[1]>x[2] && x[2]<[3], or x[1]<x[2] && x[2]>x[3], since otherwise we can achieve a shorter length by deleting x[1]. However, this in fact has indicated that the shortest length is 3 since it is enough to keep x[1], x[2] and x[3] only while deleting all the following elements. For the following arguments, we denote the three indices as 'left', 'middle' and 'right', which should be initialized as '-1'.

Now, we can first enumerate the sequence and when we find that the next number is larger or smaller than the current one, we stop and adopt a 'flag' to indicate which case it belongs to. For instace, if a[i+1]>a[i], we denote flag=1 while if a[i+1]<a[i], we set flag=-1. Next, we enumerate the sequence from the first element again, and we have the following cases.

1) a[i+1]>a[i], if flag==1, then we can set left=i and middle=i+1; otherwise, we set middle=i and right=i+1 and stop the enumeration;

2) a[i+1]<a[i], if flag==1, then we set middle=i and right=i+1 and cease the enumeration; otherwise we set left=i and middle=i+1.

Finally, we check whether all 'left', 'middle' and 'right' have been given reasonable values, if it is, output them as the answer; otherwise we can conclude that no such unordered subsequence exists.

I think this is well known as the "2-sat" problem. I hope that the following arguments can serve a general method to solve such problems.

At first, for two given roads, we need to judge whether they are mutual exclusive, i.e., if they have to be built as 'io' or 'oi', they are mutual exclusive. For instance, for roads [4,6] and [1,5], they are mutual exclusive, and we cannot build both of them inside or outsied the ring. Without loss of generality, we denote any two roads as [a1,b1] and [a2,b2]. It is obvious that if they have common ends (a1==a2 || a1==b2 || b1==a2 || b1==b2), they are not mutual exclusive; otherwise, we can enumerate from a2 to b2 and if we can meet exactly one single end belonging to road [a1,b1], then they are mutual exclusive. Be careful that this enumeration should be done by implementing 'module operation' based on the number of cities 'n', so that it does not matter even if a2>b2. It is important to notice that when we obtain '0' during the 'module operation', it in fact means that we have reached position 'n', which should be handled specifically.

Then, for every road, we find out its mutual exclusive roads, which can be done with complexity O(m^2). We can build an adjacent matrix E[m][m] to store the results and thus establish a graph, for instance, if road A is mutual exclusive with road B, then E[A][B]=E[B][A]=1. Next, we implement breadth frist search (BFS) based on this graph, and when we meet a new node, set it as 'o' if its parent node is 'i' and vice versa. The root node is free to choose 'i' or 'o' (it can be proved that this will not affect the final answer). After all the nodes (or roads) in the graph have been visited, they are exactly divided into two groups with type 'i' and 'o'. The left thing to do is to check again whether there are any two roads that are mutual exclusive in one single group.

The above arguments can be summarized as the following steps:

1. find out a method to judge whether two nodes are mutual exclusive;

2. build a graph, and the edge means a mutual exclusive relationship between two nodes;

3. implement BFS and guarantee that all the nodes have been visited, while dividing the nodes into two groups;

4. for each group, check that whether there are mutual exclusive nodes

E. Number With The Given Amount Of Divisors

A little difficule problem for me...

At first, we should figure out how to compute the number of divisors for some given integer N. According to the Fundamental Theorem of Arithmetic, N can be uniquely written as N=(p1^n1)*(p2^n2)*..., where pi is a prime number. For any divisor of N, it must be some combination of p1, p2,.... Therefore, the total number of divisors can be calculated as n=(n1+1)*(n2+1)*...

The problem asks to find the minimum number which has exact n divisors, where n takes values from [1,1000]. As ni=0 means that N does not have a prime divisor pi, we only consider those prime divisors which has ni>=1. Thus, ni+1>=2, and it can be observed (n1+1)*(n2+1)*...(n10+1)>=1024>1000. This implies that it is sufficient to consider only the first ten prime divisors, i.e., {2,3,5,7,11, 13,17,19,23,29}.

With the above arguments, we can adopt Dynamic Programming to solve the problem. Let us use dp[i][j] to denote the minimum number which has exactly n divisors and the first j prime divisors, where i>=1 and j>=1 to simplify the description. Note that "has exactly the first j prime divisors" means that n1, n2,...nj should all take values that are larger than zero. Now we try to figure out how to calculate dp[i][j]. In fact, dp[i][j] can be uniquely determined based on dp[1][j-1], dp[2][j-1],...dp[1000][j-1]. The reason can be clearly seen through the following simple example. Assuming that N=(2^4)*(3^2)*(7^2) is the minimum number which has (4+1)*(2+1)*(2+1) divisors, nevertheless, this is incorrect sine we can immediately find a smaller N'=(2^4)*(3^2)*(5^2). This example implies that the prime divisors cannot "jump" but "show up" exactly one by one.

Therefore, once dp[1][j-1], dp[2][j-1],...dp[1000][j-1] are determined, dp[i][j] has already been determined as well. Thus, we can calculate dp[i][j] from every one of dp[1][j-1], dp[2][j-1],...dp[1000][j-1], and find the minimum one as the final answer. For dp[r][j-1], if r is a divisor of i and i/r-1>0, then we can obtain a reasonable dp[i][j] from dp[r][j-1], i.e., dp[i][j]=dp[r][j-1]*(p[j])^(i/r-1), where p[1]=2, p[2]=3, p[3]=5,...,p[10]=29. By enumerating all the feasible dp[r][j-1], we can find the minimum one and update dp[i][j] by this minimum number. However, the term (p[j])^(i/r-1) is likely to take a very large value. As the question ensures that the answer will not exceed 10^18, we can implement the multiplication step by step, i.e., whenever we find an appropriate dp[r][j-1], we start from dp[r][j-1]*(p[j])^(1), then dp[r][j-1]*(p[j])^(2), then dp[r][j-1]*(p[j])^(3), and so on, and if some dp[r][j-1]*(p[j])^(k)>10^18, we can immediately terminate the calculation since this is definitely not the answer. Finally, the initialization can be done by setting dp[r][1]=2^(r-1) (of course, the 10^18 limitation should be considered). As some dp[i][j] may not have a reasonable value, for instance, dp[2][2], which is at least 2^1*3^1 and thus have at least 4 divisors. For simplicity, we can assign -1 to such positions.

Now, the problem is equivalent to finding the minimum number among dp[n][1], dp[n][2],...dp[n][10], which serves as the final answer.

•
• +9
•

By pleasurepain, 9 months ago, ,

A. Almost Prime

This problem can be viewed as a special case of a more general problem, which asks to find the number of prime divisors for some given positive integer N. In general, N can be written as N=(p1^n1)*(p2^n2)*(p3^n3)*..., which is well known as "Fundamental Theorem of Arithmetic", where pi is a prime divisor. Thus, we can test from 2 to N-1, and whenever a prime divisor pi is found, we just keep dividing N by pi and update N as N=N/pi, until the updated N is not a multiple of pi. Meanwhile, we count the number of different pi, and if the result is two, it means that N is almost prime. Note that when we enumerate from 2 to N-1, it is guaranteed that only the prime divisor of N will be counted. To prove this, suppose that an integer M which is a divisor of N but not a prime oneis found. Then, M can be written as M=(p1^m1)*(p2^m2)*... As we enumerate the divisors from smaller ones to larger ones, pi must have been found before M is reached, so that M cannot serve as a divisor of N, which is contradictory to our assumption.

B. Suppose that we enumerate the bracket sequence from left to right. A pair of reasonable (or regular) bracket will be found whenever we meet a ')', under the condition that at least one '(' has been met before. As this ')' should be paired with the "nearest" '(', this '(' cannot be used to pair with the following ')'. The above process can be simply implemented by keeping a variable 'B' to store the number of currently unpaired '(', and when a '(' is met, we add B by one while subtracting it by one if ')' is met. However, one should be careful that when B=0, no subtraction should be implemented, since this situation implies that no '(' is available to be paired with the currently met ')'. The problem can be solved by doubling the number of subtraction implemented to B as the final answer.

C. Parquet

At first, we try to figure out whether it is possible or impossible, and we can consider the following four cases.

1) Both m and n are odd numbers. It is straightforward that the answer is impossible, since every kind of plank will contribute 2 or 4 meters, and thus it is impossible to perfectly cover a floor which has a size of odd number;

2) m is an odd number while n is an even number. Let us focus on one single row, and suppose that we only use planks with 1*2 and 2*2 sizes. Note that it will always contribute 2 meters to the current row whenevere we use a plank with 1*2 or 2*2 size to cover it. Therefore, we have to use at least one plank with 2*1 size if we want to cover the current row perfectly. As a 2*1 size can cover two rows, we need at least n/2 planks with 2*1 size. Therefore, if the number of planks with size 2*1 is less than n/2, the answer will be impossible; otherwise it might be possible (not surely). Furthermore, if it is possible, we can first put n/2 planks with size 2*1 at the last column, without loss of generality. Then, m becomes m-1, which is an even number, and it turns out to be the same as case 4);

3) m is an even number but n is an odd number. As in case 2), we apply similar arguments and will find that if the number of planks with size 1*2 is less than m/2, it is impossible to cover the whole floor perfectly; otherwise, it might be possible. Furthermore, we can put m/2 planks with size 1*2 first, and turn it into case 4) again;

4) Both m and n are even numbers. We can solve the problem in such a manner:

step 1: we put planks with size 2*2 from the upper left corner of the floor first to the right bottom corner; if the number of such planks is sufficient to cover the whole floor, then we are done; otherwise, we go to step 2;

step 2: we combine two planks with size 1*2 to form a virtual plank with size 2*2, and continue as step 1 indicates; if the whole floor is covered, then we are done; otherwise go to step 3;

step 3: we combine two planks with size 2*1 to form a virtual plank with size 2*2, and continue as step 1 indicates; if the whole floor is covered, then we are done; otherwise it means that the answer is impossible.

I think that the above steps will work efficiently and correctly, but I cannot figure out how to prove it... Except for this, I find it not quite easy to provide a pattern explicitly (as the problem asks) which can cover the floow perfectly. I adopt a rather complicated method. I start from the upper left point and implement the above several steps, and whenever I put down a plank, I will check the "indicators" (letters with lower case, suhc as 'a', 'b', etc.) of the adjacent points, and as there will be at most 8 adjacent points, it is always feasible to select a letter that can be used to indicate the current plank. However, this is somehow very complicated....If anyone has any better solutions, it is very nice for you to share your ideas.

By pleasurepain, 10 months ago, ,

A. IQ test

For a given array consisting of positive integers, the problem asks to find out the unique number which is different from all the other ones after implementing modulo-2 operations. We can count the number of odd integer and even integer as num_o and num_e, respectively, while storing any arbitrary positions at which an odd number and an even number appear. As the "unique" number only appears one single time, we can find out num_o==1 or num_e==1, and output the stored positions as the answer.

B. Phone numbers

This problem can be solved through a classification based on the value of n modulo 3, which contains the following cases:

1) n%3==0; the phone number can be seperated into groups of 3 digits;

2) n%3==1; we can seperate the first 4 digits into 2 groups of 2 digits, while the following digits can be seperated into groups of 3 digits;

3) n%3==2; the first 2 digits of the phone number is output, and the following digits can be seperated into groups of 3 digits

The solution is similar to the famous Floyd Algorithm. For two given cities S and T, let us consider how their minimum distance can be altered if a new road between A and B is built. We can imagine that there is a map which describes the roads between each pair of cities (if they exist), although this map is not explicitly known or given. For any given route from S to T, if this route does not use the newly built road betwwen A and B, the minimum distance between S and T stays the same, since nothing changes. Thus, the minimum distance might be updated if and only if the newly built road betwwen A and B is used. Then, the distance between S and T, d_m[S,T] can be divided into three independent parts, S to A, A to B and B to T. Note that according to the Minimum-Distance-Table, the minimum distance between S and T is d_m[S,A]+d_new[A,B]+d_m[B,T] for the current route, where d_new[A,B] denotes the length of the newly built road between A and B. Be careful that there is another feasible route which uses the newly built road as follows: S to B, B to A and A to T, which contributes a distance of d_m[S,B]+d_new[B,A]+d_m[A,T].

Finally, we should also notice that the newly built road may be "farther" then the old one. Therefore, the minimum distance between S and T should be d_m[S,T]=MIN{d_m[S,T], d_m[S,A]+d_new[A,B]+d_m[B,T], d_m[S,B]+d_new[B,A]+d_m[A,T]}. We have to implement the above operations for every pair of cities, which gives complexity O(n^2). As K roads are newly built, the total complexity is O(n^2*k). A last question to consider is the range of the final answer. Let us construct a worst case. Suppose that the cities form a linked list, where each node has exactly one single father node (except for the head node) and one child node (except for the tail node). Then, the largest answer can be

1000*(n*(n-1)/2+(n-1)*(n-2)/2+...+2*1/2)=1000/2*( (n-1)^2+(n-1)+(n-2)^2+(n-2)+...+1^1+1 )=1000/2*n*(n-1)*(n+1)/3>2^32 (choosing n=1000). Therefore, we should adopt the "long long int" type to compute the final answer.

D. Roads not only in Berland

I think perhaps I have used a little bit complicated method. One can refer to Union-Find (I am not sure of this terminology) for another simpler solution.

I adopt DFS (depth first search) for this problem. During DFS, when wemeet a node that has been visited, it means that this edge (might be referred to as backward edge) is not necessary to keep the current component connected, and thus this edge can be removed. However, there are seceral details that should be considered (all the following arguments are based on DFS).

1) Suppose that node A is the parent node of node B, and node B is the currently processed node. As the edge is not directed, node A will be visited again, but we cannot say that this edge is not necessary. The edge is not necessary if and only if the following two conditions are satisfied: a) a node that has been visited is met; b) this node is not the parent node of the currently processed node;

2) Any backward edge may be visited twice. Thus, they should be stored only once when it is visited for the first time;

3) As the graph may consist of several connnected components, it is likely to implement the DFS for several times. Whenever a new DFS is implemented, we can select any one single node belonging to this component as the "delegate";

4) Store all the backward edges and all the "delegates". The final answer is: remove all the backward edges and build new edges to connect every connected-component.