67A - Partial Teacher

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

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

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

67B - Restoration of the Permutation

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

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

67D - Optical Experiment

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

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

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

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

66A - Petya and Java

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

66B - Petya and Countryside

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

66D - Petya and His Friends

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

66E - Petya and Post

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

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

Thus, we have

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

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

65A - Harry Potter and Three Spells

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

65B - Harry Potter and the History of Magic

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

65C - Harry Potter and the Golden Snitch

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

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

65D - Harry Potter and the Sorting Hat

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

63A - Sinking Ship

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

63B - Settlers' Training

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

63C - Bulls and Cows

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

63D - Dividing Island

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

63E - Sweets Game

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

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

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

(S & move) == move

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

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

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

A. A Student's Dream

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

B. Tyndex.Brome

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

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

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

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

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

A. Ultra-Fast Mathematician

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

B. Hard Work

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

C. Capture Valerian

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

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

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

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

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

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

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

D. Eternal Victory

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

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

E. Enemy is weak

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

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

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

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

A. Where Are My Flakes?

We can adopt two variables Lb and Rb to denote the range of values that the target can take, i.e., [Lb Rb]. Then, for each input, we update Lb and Rb accordingly to obtain a tighter range. Finally, if Lb<=Rb, it is sufficient to output Lb, Lb+1,...,Rb; otherwise output -1.

B. Serial Time!

It might take time to understand the descriptions, however it is in fact a problem about search on graph. We use P[L][R][C] to denote the character located in the L-th layer, R-th row and C-th column. The answer is just the total number of '.' that we can reach if starting from the initial given location. Thus, we can solve it by adopting BFS and count the number of '.' that we can meet. According to the problem, it is possible to reach at most another six positions from any position, i.e., P[L][R][C+1], P[L][R][C-1], P[L][R+1][C], P[L][R-1][C], P[L+1][R][C], P[L-1][R][C].

C. Mushroom Strife

By using x*y=GCD(x,y)*LCM(x,y), we can determine all the numbers in a connected component if any one of them is assigned with an initial value. Therefore, at first we select an arbitrary number x belonging to some connected component, and find out another number y to which it is connected. As we have been given GCD(x,y) and LCM(x,y), x must be a factor of LCM(x,y) and it must be no less than GCD(x,y). Thus, we can find all the factors of LCM(x,y), and only store those ones which are larger than or equal to GCD(x,y). Next, we enumerate these values, and for each of them, we implement BFS (or DFS) to calculate all the numbers belonging to this connected component. Then, for each connected pair of numbers, we check whether their GCD and LCM are exactly equal to the previously given ones or not. If they are the same during some enumeration, it means that we have found out some reasonable values for all the numbers in this connected component and thus we can move on to the next connected component; otherwise it implies that no reasonable values can be found.

For some given integer N, it takes O(sqrt(N)) complexity to find out all its factors. BFS has complexity O(n^2), and thus the total complexity is about O(sqrt(10^6)*100*100)=O(10^7).

A. Word

This is a simple problem. We can count the number of uppercase letters and lowercase letters, respectively, and then compare their results and implement operations accordingly.

B. Fortune Telling

We can adopt two arrays to store the even integers and odd integers, respectively. If there are no odd integers, we should output 0. On the contrary, we first add all the even integers together, and sort all the odd integers in a decreasing order. Then, if the total number of odd integers is odd, we add all of them together; otherwise we add all of them except for the minimum one.

C. Title

It is sufficient to deal with the first half of the string. We use s[i] to denote the i-th (index starts from 1) character in the first half of the string, and further denote the length of the string is n. For each pair s[i] and s[n-i+1], if both of them are '?', we just leave them as they are. If both of them are letters, we check whether they are the same or not, and if they are different, we can immediately output "IMPOSSIBLE". If exactly one of them is a letter while the other one is "?", we just replace "?" with this letter.

After we have completed the above operations, we start from s(n+1)/2 until we reach s[1]. During this process, whenever we meet a "?", we replace it with the "largest" letter that is still not contained in the current string; while if all the letters have been contained in the string, we replace all the left "?" with letter 'a'. Finally, remember to check whether the required letters have appeared in the string for at least once or not.

D. Team Arrangement

At first, we should find out whether the student with number k is the captain or not. To solve this, we can first find the team to which this student belongs (this is just the row index in the "members of a given team" matrix). Then, we enumerate from the first student according to the results of personal training sessions, and find the first one who belongs to the team where the student with number k is. This student must be the captain of this team.

If student with number k is not the captain, we can directly output 1,2,...,n but skipping k, since the priority list of student with number k has no effect on how the members are selected.

If student with number k is the captain, we can immediately find out his two teammates, denoted as T1 and T2, and without loss of generality, we assume that T1<T2. Then, we divide the other students into two groups G1 and G2. At first, all the students that belong to the following teams are put into G2. Then, for the students that belong to the previous teams, if his number is larger than T2, he should be put into G2; otherwise put into G1. Finally, both T1 and T2 are put into G1. After sorting G1 and G2 in both increasing order, we can output G1 and G2 in turn, and this is just the answer. This solutions works since all the students belonging to the following teams cannot be put before T1 and T2, since otherwise some one of them will be selected instead of T1 or T2. Next, all the students with number larger than T2 and belonging to the previous teams should be put after T1 and T2, since they have been selected by other teams and thus they have no effect on the current team.

A. Chat room

Suppose that the given string is denoted as S while "hello" is denoted as T. We can solve the problem by adopting two pointers pS and pT, which point to string S and T, respectively. At first, both pS and pT are set to 0. Then, we increase pS by 1 until it reaches the end of string S. During this process, once it occurs that S[pS]=T[pT], we immediately increase pT by 1 as well. Note that when pT reaches the end of string T, we can break the loop. After all the characters in string S have been visited, and the loop is over (or we break the loop), we can check whether pT has arrived at the end of string T or not. If the answer is YES, it means that we can obtain "hello" from the original given string; otherwise we should output NO.

B. Coins

For any integer N, we can find all its prime divisors and write it in the form of N=p1^a1*p2^a2*...pn^an, where pi is a prime divisor while ai denotes the number of pi that N has. Intuitively, we may come up with such a sequence which is depicted as follows:

1

1*p1

1*p1*p1

1*p1*...*p1

1*p1*...*p1*p2

1*p1*...*p1*p2*p2

1*p1*...*p1*p2*p2*...*p2

...

1*p1*...*p1*p2*p2*...*p2*pn*...*pn

It can be seen that such a sequence have (a1+a2+...an+1) integers, and this is just the maximum number of coins that we can obtain. For instance, if N=36, we have 1, 1*2, 1*2*2, 1*2*2*3, 1*2*2*3*3. We can use "proof by contradiction" to prove this claim. Assume that the optimal sequence has M>(a1+a2+...an+1) coins and we denote this sequence as S. Then, let us try to implement some subtle modification to the current sequence to obtain a better one. We first sort S in an increasing order, and use S[i] to denote the i-th integer after sorting. If S[1] is not "1", we can immediately add "1" to S since any integer is divisible by 1, and thus we have obtained a better sequence S', which is contradictory to our assumption. Then, S[2] must be equal to some prime divisor, since otherwise we can decompose S[2] and obtain a better sequence again. Next, S[3]/S[2] must be some prime divisor as well, since otherwise we can decompose S[3]/S[2]=P*Q, and add S[2]*P to obtain a better sequence. Based on similar arguments, we can find that there are exactly (a1+a2+...an+1) integers in S, which is contradictory to our assumption, and thus proof is completed.

C. Trees

Note that S=(1,2,3....,3,2,1) is always a reasonable sequence. For the given sequence A=(a[1],a[2],...,a[N]), we can calculate the difference between A and S to obtain the following sequence T=A-S=(a[1]-1,a[2]-2,...,a[N-1]-2,a[N]-1). At first, one should note that if T[i]<0, then a[i] must be changed since the problem requires that a[1]>=1. Next, suppose that the optimal sequence is S'=(x+1,x+2,...,x+2,x+1), where x is some non-negative integer. Here "optimal" means that if we change A into S', we can achieve the minimum number of changes. Then, we compute T'=A-S', and count the number of "0" in T'. It can be seen that the number of "0" must be no less than that of any other sequence S''. Furthermore, if we add all the integers in T' by x, it is just the same as T, i.e., A-S'+x=T'+x=A-S=T. Therefore, if we count the number of "x" in T, it will be exactly the same as the number of "0" in T'. Based on these arguments, we can just count the number of different non-negative integers in T, and denote the maximum number of some integer as M. Then, the answer is N-M.

D. Calendar

At first, we store all the strings according to their length, i.e., they are divided into different groups based on their length. Then, all the strings belonging to the same group are sorted in an increasing order. As the problem requires that the final output lines should have the same length, one can calculate that the length should be L=(l1+l2+...+ln)/(n/2)+1, where li denotes the length of the i-th string.

Next, we need implement a loop pf length (n/2) to obtain the answer. During each loop, we will find the first and second string in turn. To find the first string, we can take out the first string of each group and append the special symbol, and find out the smallest one, which is just the target string. Then, we denote the length of the first string as L', and it is sufficient to take out the first string in the group whose strings all have length L-L'-1. The total complexity is O(N). The above operations in fact look like Bucket Sort...

A. Square Earth?

At first, we consider the case where two points are on the same line or two neighboring lines. By denoting the two points as (x1, y1) and (x2, y2), one can check that the answer is just min(|x1-x2|+|y1-y2|, 4*n-|x1-x2|-|y1-y2|). Next, we consider the case where these two points are on two parallel lines. If |x1-x2|=n, the answer will be min(y1+y2+n, 4*n-(y1+y2+n)), while if |y1-y2|=n, the answer is min(x1+x2+n, 4*n-(x1+x2+n)).

B. Martian Architecture

For each query, we can enumerate all the roads, and if the asked number ki falls into the interval [ai, bi], then we add ci-ki+ai to the final answer.

C. Array

This is a textbook example to practice three techniques, which are referred to as Pascal's triangle, Fermat's little theorem and fast modular exponentiation.

1) Pascal's triangle

We use F(n,m) to denote the number of non-decreasing sequences which satisfy the following condition: it has length n and the first number is no larger than m. In fact F(n,m) can be calculated in a recursive manner, as indicated by Pascal's triangle, by using F(n,m)=F(n-1,m)+F(n,m-1). The first term F(n-1,m) means that the first number is set to m, and thus we only have n-1 numbers to assign values. The second term F(n,m-1) means that we select a value which is no larger than m-1 as the first number. For an intuitive understanding, the above equation holds based on what value the first number takes. One can check that F(n,m)=C(n+m-1,n), where C(n,k)=n!/(n-k)!/k! (in fact I cannot figure out how to prove this, however I compute some values with small n and m, and find out the rules). According to the problem, the total number of non-decreasing sequences is C(2n-1,n), and by reversing every non-decreasing sequence, we will immediately obtain a non-increasing sequence, and the total number of such sequences is still C(2n-1,n). However, those sequences consisting of the same numbers have been counted twice, and thus the final answer should be 2*C(2n-1,n)-n.

2) Fermat's little theorem

With the above arguments, our current task turns out to be calculating C(2n-1,n)%P, where P is the given integer by the problem. As C(2n-1,n)=(2n-1)!/n!/(n-1)! has a fractional form, we generally use Fermat's little theorem to avoid direct computation. One can search on the internet to find more details about Fermat's little theorem. The main claim is that for some integer X, its inverse element is X^(P-2) when considered under the operation of module by P (This holds under some specific conditions). Therefore, to calculate Y/X%P, we can compute Y*X^(P-2)%P instead.

3) Fast modular exponentiation

This might be a well-known technique which has been used in RSA cryptosystem. The main idea is that to calculate (a^n)%P, if n is an even number, then we can compute (a^2)^(n/2)%P; while if n is an odd number, we can calculate (a)*(a^2)^(n-1)/2%P. Therefore, the size of n is halved for each time, and the complexity of such an algorithm is merely O(logN).

A. Bar

If the current input is a number, i.e., the age, then it suffices to check whether this is not younger than 18 or not. If the current input is the name of some drink, then it is sufficient to check whether this belongs to the list of alcohol drinks or not.

B. Spoilt Permutation

We can adopt two pointers p1 and p2, which start at the first position and the last position, respectively. Then, we move p1 to the right until we meet an element which is not equal to its index. Similarlt, we move p2 to the left and find the first element that is not equal to its index. It is obvious that if p1>=p2, then the answer should be "0 0"; otherwise we should further check that whether each element a[j], where p1<=j<=p2, will satisfy the condition

a[j]=p2-(j-p1)

If for all the elements from p1 to p2, inclusively, the above equation hold, the answer will be "p1 p2"; otherwise it is "0 0".

C. Corporation Mail

At first sight, this problem might seem a little complicated. Nevertheless, it can be solved by using "stack" in a simple and straightforward manner. It is convenient to use the "vector" to simulate the "stack" (also you can directly use the "stack").

Starting from the first character, whenever a name is found, we search the vector and whenever we find a string that is the same as the name, we add the answer by 1. Then, we also push the name into the vector (push_back). Next, whenever we meet a '.', the last string (or name) in the vector is taken out (pop_back).

D. Changing a String

This is well known as "Edit Distance" problem as far as I consider. One can search on the Internet and will find a lot of useful information.

E. Domino Principle

For each domino, denoted as D[i], we assign it with four parameters, position D[i].x, height D[i].h, original index D[i].idx and the index of the most right domino that it can hit, denoted as D[i].nidx. Note that here "hit" does not mean that the current domino must hit it directly. Instead, just as domino implies, we say that it can hit another domino if we push it to the right, this domino will fall down finally.

At first, we sort the dominoes in an increasing order of their positions, and then deal with the dominoes from right to left one by one. Suppose that we are now arriving at the i-th domino. Then, we start from the (i+1)-th domino and check whether the i-th domino can hit it or not. This is straightforward by checking if D[i+1].x falls into the interval [D[i].x+1, D[i].x+D[i].h-1]. If the answer is NO, it means that D[i].idx=i, i.e., this domino can only "hit" itself. Otherwise, we further whether the i-th domino can hit that one with index D[i+1].nidx+1. The reason is that since we can hit the (i+1)-th domino, and if it falls down, D[i+1].nidx implies that the (D[i+1].nidx)-th domino will also fall down. Thus, we can directly skip to the (D[i+1].nidx+1)-th domino and check whether it can be hit or not, and repeat the above operations. During this whole process, we can update and store the number of dominoes that every domino can "hit".

The complexity can be calculated by using the "Amortized Analysis" technique. Note that checking whether some domino can hit another one on the right contributes to the total complexity, and thus we count the number of such "checking". When "checking" occurs, if the answer is YES, i.e., it can hit another one on the right, we assign this "checking" to the right one which can be hit and denote this event as Type-1; otherwise, we assign this "checking" to the current domino and denote this event as Type-2. Now we prove that for each domino, both Type-1 and Type-2 event can occur for at most once. Therefore, the total complexity is O(N).

Proof: Suppose that the (i+1)-th domino is checked whether it can be hit by the i-th domino or not. If the answer is YES, then Type-1 event occurs at the (i+1)-th domino. Note that Type-1 event will never occur at the (i+1)-th domino any more, since when we later visit the (i-1)-th domino, we will compare it with the i-th domino while the (i+1)-th domino will be skipped (the reason is that if the i-th domino can be hit, then the (i+1)-th domino can be hit as well). Similarly, if the answer is NO, Type-1 event occurs at the i-th domino, however this Type-1 event will never occur at the i-th domino, either, according to the our definition.

An intuitive understanding of "Amortized Analysis" is that the same operation is amortized, or separately counted, and finally added together.

A. Flea travel

Suppose that at first the flea is at position S. According to the problem, the flea will appear at position

(S+1+2+3+...+t-1)%N=(S+(t-1)*t/2 )%N

after the t-th minute. It seems that we have to check infinite times to find out whether it can appear at all the positions, which is in fact impossible. However, we can prove that if the flea is at position V after the t-th minute, then it must return to position V after the (t+2*N)-th minute. The proof is

(S+(t+2*N-1)*(t+2*N)/2 )%N=(S+(t-1)*t/2+(t-1)*N+t*N+2*N*N)%N=(S+(t-1)*t/2 )%N

Therefore, it is sufficient to check from 0-th minute to (2*N-1)-th minute, and then we can find out whether the flea can visit all the positions or not.

B. Smallest number

We can generate all the feasible permutation of the given four integers, and denote the them as a,b,c,d. Furthermore, we denote the operations as x,y,z. Then, we can first calculate ((a x b) y c) z d, and then calculate ((a x b) z (c y d)). For all the results that we have obtained, it is sufficient to record the minimum one and this is just the answer.

C. Pie or die

A problem that is full of tricks...

For the i-th pie, we can calculate its Manhattan distance to the four borders. Among the four Manhattan distances, we only focus on the minimum one, denoted as d[i], and the corresponding border is denoted as B[i]. Furthermore, we select the pie which has the minimum distance d[i], and this distance is denoted as D while the corresponding border is B. Then, we consider the answer based on the value of D.

1) D=0: the answer is obviously yes;

2) D=1: the answer is yes; one simple strategy is to first move one step closer to border B; if this position is not blocked, then we win; otherwise we move on to the corner along the border (we can choose any corner); as the corner in fact "provides" two "exits" to escape from the board, the two "exits" cannot be blocked at the same time;

3) D=2,3,4: the answers are all yes; the strategy is that we always first try to move to the border B and then move on along the four borders until we find a corner with two "exits" which cannot be blocked at the same time; it is guaranteed that if D<=4, there is always a corner that has two "exits" and they cannot be blocked at the same time, which can be proved as follows:

Note that it takes us four steps to reach the border B. The competitor can take advantage of these four steps to block one "exit" (or edge) for each of the four corners. However, this means that when we arrive at the border, we can successfully escape since only the "exits" at the four corners have been blocked. If the competitor only blocks one "exit" (edge) for some (not all) of the four corners, we can move on along the border B and will finally arrive at the corner which has two "exits".

4) D>=5: the answer is always no; the reason is that before we arrive at the border B, at least one of the "exits" (edges) at the four corners have been blocked; thus when we arrive at border B, the competitor can just block the edge that we are facing to, and even when we reach the corner, there exists only one "exit" and the competitor can always block it immediately after we arrive there.

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

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.

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

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.

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.

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.

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

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.

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

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

C. Email address

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

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

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.

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.