"有道难题2009"复赛题目与解题报告

题目: UnrepeatingNunbers (350 points)
Problem Statement:
如果一个数字十进制表达时，不存在连续两位数字相等，则称之为“不重复数”。例如，105，1234和12121都是“不重复数”，而11，100和1225不算。给定一个long类型数字A，返回大于A的最小“不重复数”。
Definition:
Class: UnrepeatingNumbers
Method: next
Parameters: long
Returns: long
Method signature: long next(long A)
(be sure your method is public)
Constraints:
A 取值范围是[0， 10^17]，注意是闭区间。
Examples:
0)    54
    returns： 56
    大于54的最小数字是55，但55不是“不重复数”。下一个数字是56，它满足条件。

1)    10
    returns： 12

2)    9
    returns： 10

3)    98
    returns： 101
    99和100都不是“不重复数”， 101是。

4)    21099
    returns： 21201
解题报告:
The first solution that one could think of is to just increase A until it becomes a "unrepeating" number. Verifying that a number is unrepeating requires to decompose it into a list of digits, which is a simple task. Unfortunately, the constraints for the problem said that A can be as large as 10^17, we can notice that with a value of A equal to 1 and 17 zeros, our algorithm would take a lot of time before the two most significant repeated digits are dealt with.

However, the observation about spending too much time before dealing with significant repeated digits can be helpful. A good idea to optimize the previous algorithm would be to simply increase the digits that we need to increase. Instead of increasing the whole number until the repetition is handled correctly. This is actually an idea good enough to solve the problem. Unfortunately a lot of coders didn't consider special cases when implementing it which caused plenty of failed solutions. This was mostly due to the examples all having the repeated numbers in the least significant digits, which made it challenging to analyze the problem correctly. Let's analyze a good case in order to design an algorithm, A = 122055123, since the result must be greater than A, we will begin with 122055124:

We find a first pair of repeated digits "22", the number needs to be changed within the second '2', we might increase the left side of the number and leave the other side intact.



Is this a good result? It probably isn't. Although we have dealt with the pair of '2's , the right side of the number could actually be smaller (we need to find the smallest "unrepeating number" greater than A). Some quick analysis could show that the minimum 9 digits unrepeating number beginning with 123 would be : "123010101", although we could base our solution on adding this repeating 01.. pattern to the right side of the number, it is not convenient as we will have to deal with special cases. (I.e: pairs of 99 may add new repeating pairs in more significant digit positions) Not handling these special cases correctly caused many solutions to fail. A more convenient solution would be to replace the right side of the number with zeros, and just repeat this process going from the most significant digit to the least significant digit until the number becomes unrepeating:

A big numbers class or string manipulation would be helpful in Implementing this algorithm but was not necessary, it was possible to implement it using arithmetic and powers of 10 to handle the digits:

1. long getNext( long A)
   
2. {
   
3.     A++;
   
4.     bool done = true;
   
5.     do {
   
6.         long d = 1;
   
7.         while (d*10 < A) //find the higest power of 10
   
8.            d*=10;            // that is smaller than A
   
9.         
   
10.         done = true;
    
11.         while (d > 1) {  //iterate valid powers of 10 from highest to lowest (10)
    
12.             long nd = d / 10;
    
13.             if ( (A / d) % 10 == (A / nd) % 10 ) { //compare the digits at these two consecutive positions
    
14.                 A/= nd;    //increment the left  side
    
15.                 A++;      
    
16.                 A*= nd;   //replace the right side with zeros.
    
17.                 done = false;
    
18.             }
    
19.             d = nd;
    
20.         }
    
21.     }
    
22.     while (! done);
    
23.     return x;
    
24. }

复制代码

题目: UnrepeatingNunbers (350 points)
Problem Statement:
“回文分数”游戏并不简单，游戏目标是修改最多maxChanges个字符使得一个字符串的回文分数最高。只允许修改，不许增加或者删除字符。一个字符串的回文分数定义如下：

&#61550;- 如果字符串不是回文串，则分数为0。
&#61550;- 如果字符串是回文串，且长度为奇数，则分数为1。
&#61550;- 如果字符串是回文串，且长度为偶数，设它的一半子串的回文分数为K（两个一半子串得分一定相同），则分数为K + 1。

给定一个字符串word和一个int型数maxChanges，返回最多修改maxChanges个字符后最大可能的回文分数。
Definition:
Class: MaximumPalindromeScore
Method: maximize
Parameters: String, int
Returns: int
Method signature: int maximize(String word, int maxChanges)
(be sure your method is public)
Notes
回文串的定义是一个字符串从前向后读和从后向前读完全一样。
Constraints
- word包含1到50个字符。
- word 只包含小写字母 ('a'-'z')。
- maxChanges 取值范围是[0，50]，闭区间。
Examples
0)    "coder" 2
    returns： 1
    把c改成r，把e改成o，得到“rodor”，这是一个奇数长度的回文串，所以得分为1。

1)    "abcbxabcba" 1
    returns：2
    把x改成a，得到“abcbaabcba”，偶数长度，它的一半子串是“abcba”，该子串是一个奇数长度的回文串，所以子串分数为1，因而最后得分是2。

2)    "abcdefghijklmnop" 15
    returns： 5
    可以把这个字符串修改成“aaaaaaaaaaaaaaaa”，“eeeeeeeeeeeeeeee”等串，回文得分为5。

3)    "ssssssssssssssss" 15
    returns：5
    无需做改变。

4)    "vyyvvzzvvxxvvxxv" 4
    returns：3

5)    "a" 0
    returns：1
解题报告:
A first useful observation is to notice that the palindrome score of a word cannot become too high, in fact, the maximum score a word of length n could have is log2(n). This means that even for n=64, the maximum score possible is 6.

It would be possible to make a function isPossible(word,S,maxChanges) that verifies a palindrome score S is possible for a certain word after maxChanges character changes. This algorithm can help us solve the problem, we can iterate for all possible values of S from larger ones to 0. Once we find a value of S that is possible, return it since it is the maximum palindrome score for that case.

The problem is reduced to how to code the isPossible() function. A way to solve this subproblem is to first calculate the minimum number of characters in the word that have to be modified for the word to have a palindrome score of S. For a word to have a certain score S, it needs certain characters in specific indexes to be equal. Let's first verify the case for which S=1, in this case, we simply require the word to be a palindrome. This means that the characters in the first half of the word must be equal to the opposite characters in second half of the word. If one of these pairs of characters contains two different ones, then at least one of them must be modified.



In the above example, to the 'a' characters do not need to be modified, but 'b' or 'd' have to be changed. Since 'c' does not have a pair we do not need to change it either. Larger values of S are similar, for S=2 we require both halves to be palindrome and the word itself to be a palindrome as well:



In this case, 'a','d','a' and 'h' and 'b','b','b' and 'c' are groups of indexes that must be equal. For the first group it is convenient to change 'd' and 'h' to 'a', for the second group change the 'c' to 'b'. The minimum number of changes necessary for the word to have a palindrome score of 2 becomes 3.

This allows us to determine an algorithm:

Group the indexes of the word into groups of indexes that must be equal.

For each group, pick the most common character and count the number of indexes of the group with a different character. The sum of all these counts becomes the minimum number of changes that is necessary for the word to have a score S.

Grouping the indexes can be done easily by, for example, using a recursive algorithm. The rest of the solution can be coded once we have this grouping function.

1. int totalGroups = 0
   
2. int group[]
   
3. 
   
4. // Groups the first L indexes of a word in groups such that if the indexes
   
5. // of a word of length L of each group were equal, the palindrome score
   
6. // for the word would be S
   
7. GroupIndexes(L, S)
   
8. {
   
9.     // Calculate groups for the first half:
   
10.     if ( S == 0) {
    
11.         // If S is 0, then each character can be different:
    
12.         for (int i=0; i<=j)
    
13.         {
    
14.             group[j] = group[i];
    
15.             i++, j--;
    
16.         }
    
17. 
    
18.     }
    
19. }
    
20. 
    
21. maximize(String word, int maxChanges)
    
22. {
    
23.     L=word.length();
    
24.    
    
25.     // what is the maximum valid score for a word of this length?
    
26.     int S = 1;
    
27.     int x=L;
    
28.     while( x%2 == 0) { //the length must be even to allow
    
29.         x/=2;          //a higher score.
    
30.         S++;
    
31.     }   
    
32.    
    
33.     while (S > 0) {
    
34.         GroupIndexes( L, S);
    
35.         int required = 0;
    
36.         for (int i = 0; i< totalGroups ; i++) {
    
37.             int x = MAX_INT; // number of changes required for this group
    
38.             
    
39.             // Try assigning each possible character to this group, pick
    
40.             // the one that requires least changes
    
41.             for ( ch = 'a'; ch<='z'; ch ++) {
    
42.                 int t = 0 ;
    
43.                 for (int j=0; j< L; j++)
    
44.                     if( group[j] == i) {  //only consider indexes in the current group
    
45.                         if ( word[j] != ch)
    
46.                             t ++;
    
47.                     }
    
48.                 x = min( x, t )
    
49.             }
    
50.             required = required + x;
    
51.         }
    
52.         if ( required <= maxChanges) //if the required of modifications does not exceed
    
53.             return S;                // maxChanges, then S is our result.
    
54.             
    
55.         S--;
    
56.     }
    
57.     return 0; // We could not find a better score than 0.
    
58. }
    

复制代码

题目: RobotKing (1000 points)
Problem Statement:
“机器人国王”是一个比较复杂的游戏。一个矩形棋盘包含了NxM个单元。选手必须把棋盘上的国王移动到多个胜利单元中的任一个以获得胜利。但是同时还有多个机器人也能够移动国王，这使得选手的目标很难达到, 选手唯一的优势是他有先手。

在选手每次移动时，他可以按照对角线，水平或者垂直方向把国王移动到一个相邻的空单元中。他也可以选择不移动国王。之后每个机器人会依次进行决策。每个机器人都有一个预定好的方向 (上，下，左，右)，他们会按照各自预定的方向移动国王。只要该方向没有障碍物就会移动，如果碰到障碍物，机器人在该轮不会移动国王。

选手在国王移动到胜利单元时获得胜利，无论是选手自己还是机器人把国王移动到胜利单元选手都算胜利。有两种情况选手会失败：

- 某个机器人把国王移动到棋盘外
- 选手和每个机器人每次决策(即便不移动)都算一轮，在maxTurns轮移动后，国王一直没有到达过胜利单元

选手在最开始是不知道机器人的预定方向的。他只知道每个机器人有且仅有两个可能的预定方向和各自的概率。这个信息会通过String[] robotMoves给出，其中每个元素表示一个机器人。每个元素都为“Direction1 Direction2 P”这样的格式(引号只是用于解释)，其中P是一个整数，代表了Direction1的概率。每个Direction1，Direction2都是"D", "U", "L", "R"中的一个(引号只是用于解释)，这些字母依次表示上，下，左，右。这些方向是在游戏一开始就被确定下来，并且在整个游戏中都不会被改变。机器人在 robotMoves中的顺序也就是他们做决策的顺序。

给定String[] board表示棋盘的信息。board中第i个元素的第j个字符表示棋盘的第i行，j列，其中第0行是最上面一行，第N-1行是最下面一行，第0列是最左边一列，第M-1列是最右边一列。'K'是国王的起始位置，'S'是胜利单元，'.'是空单元，'#'是障碍物。假设选手的决策总是以最大概率获得胜利，返回选手赢得游戏的概率。
Definition:
Class: RobotKing
Method: calculateWinProbability
Parameters: int, String[], String[]
Returns: double
Method signature: double calculateWinProbability(int maxTurns, String[] robotMoves, String[] board)
(be sure your method is public)
Notes:
虽然选手在最开始是不知道每个机器人的预订方向的，但是在每个机器人的一轮决策后(如果有实际移动)选手就能够知道对应的方向并把这个信息用于之后自己的决策中。返回值必须保证绝对和相对误差不超过1e-9。
Constraints:
maxTurns 取值于1~100, 含1和100。
robotMoves 包含1~5个元素，含1和5。
robotMoves中的每个元素都是如题目描述中所说的"Direction1 Direction2 P"格式，并且最开始和最后都没有多余空格，相邻元素之间也只有一个空格进行分割。
robotMoves 的同一个元素中的Direction1和Direction2是肯定不同的。
robotMoves中的每个P都在0~100之间，含0和100。
robotMoves中的所有P都没有无意义的0前缀。
board包含2~15个元素，含2和15。
board的每个元素包含2~15个字符，含2和15。
board的每个元素都包含相同个数的字符。
board的每个元素都只包含'K', '.', 'S'和'#'.
board包含有且仅有一个'K'.
board包含至少一个'S'.
Examples:
0)    10 {"R L 25"}
    {"S.", "..", "..", "K."}
    Returns: 0.75

1)    33 {"U D 50", "R L 100", "R L 100"}
    {"...", "K.S", "..."}
    Returns: 1.0
    这个例子中的最好战略是在第一步不移动国王

2)    5 {"R L 50", "R L 50"}
    {"S..###", "##..##", "###.K#"}
    Returns: 0.25
    只有一种可能把国王在5步或者以内移动到胜利单元，也就是两个机器人预订移动方向都是向左的情况

3)    550 {"D U 100", "U R 47"}
    {".......S", "S...####", "...#K###"}
    Returns: 1.0
    第一个机器人的移动方向是100%向下的，而第二个机器人的移动方向是向上或者向右。在选手第一次移动时，他应该把国王沿对角线向左上单元移动。之后第一个机器人因为下面单元有障碍物而不会移动国王。而第二个机器人可能向上移动或者因为右侧有障碍物而不移动。两种情况下，选手都会知道这个机器人的预订移动方向。如果是向上，则选手可以通过到达左侧的胜利单元获得胜利；如果是向右，则选手可以通过到达右侧的胜利单元而获胜。
解题报告:
This problem required knowledge of dynamic programming / memoization and also probability theory. Even though the most experienced programmers noticed the dynamic programming solution soon enough, it was still a hard to implement solution that required time to be done correctly. There are also details to consider about the situations in which the player can learn what direction was assigned to the robot and when he is not able to do it. Let us start by solving this simpler yet important subproblem first.

If it is a robot's turn and the player does not yet know what direction was assigned to it, then there are two possible cells in the board to which the robot could move, each determined by the robot's predefined directions. These cells are different most of the times, so it should be simply for the player to know what direction the robot picked by seeing the new position of the king. There is one exception though, when there is an obstacle in the new cell, the robot is not going to make a move in its turn, this adds a possibility that both of the possible directions of a robot would end in the same cell (if both directions lead the king to an obstacle). Fortunately, the case in which both directions lead to an obstacle is the only one in which the player will not know the robot's direction after its turn.

Let us now verify a player's turn, the player must decide between up to 8 possible cells to move the king to. The player may also decide not to move the king, for simplicity, we will consider the decision not to move the king as a decision to "move" the king to the cell in which it already is. Let's say the player knows in advances what the probability to win for each of these moves is. The player's moves should be done in a way that increases his probability to win, and therefore he will always pick the cell that will give the maximum probability to win.

The problem becomes how to know the probability of these cells. In fact, the game itself does not depend only on the cell where the king is located. A more accurate state of the game considers also the number of turns that we have had so far, whether the current turn goes to the player or a robot (we can find this based on the number of turns) and the current location of the king. There is another piece of information left, for each robot in the game, the player may already know that the robot has picked its first direction or the second one, or the player may ignore what direction the robot chose. Since there are 3 states for each robot (unknown, direction 1 picked, direction 2 picked) and we will need at most 3number of robots states to describe what we know about the robots. This leads to O( w * h * maxTurns * 3r ) states, where w and h are the width and height of the board and r is the number of robots.

Let's define a function Probability(x,y, turn, robotvec ) that returns the probability to win for a given game state where (x,y) is the position of the king, turn is the number of turns played so far and robotvec is an array that contains for each robot, 0 if the robot's direction is unknown, 1 if it is known that the first direction was chosen and 2 otherwise. We can easily solve the most basic cases: if the king is currently at a winning cell, the probability is 1.0 (the player already won). If turn is equal to maxTurns or if the location of the king is outside the board, the probability to win is 0.0 (the player already lost).

There are other possible states, for which we must first decide whether the turn belongs to the player or to a robot. This information is implicit in turn. If there are r robots, the first turn (turn=0) belongs to the player and so do all turns for which turn is a multiple of (r+1). Otherwise, the turn belongs to a robot, we can identify the number of the robot by using a modulo operation: turn%(r+1) - 1.

In the case of a player turn, we should use the logic we described above, for each possible new location (nx,ny) the player may move the king to, calculate the probability to win the game if that movement is done (which we can recursively calculate by calling Probability(nx,ny, turn+1, robotvec ) ). Pick the cell that gives the best probability, and return this probability.

For the robots' turns, there are three possible cases:

The player may already know the direction that was picked for the robot, in which case we get the position (rx,rx) to which the robot will move the king and return Probability(rx,ry, turn+1, robotvec ).

Another case is when the player does not know yet what direction was assigned to the robot, but can find out what direction it was depending on the robot's move (i.e. when at least one of the directions can take the robot to an empty cell) in this case, we can get both possible locations (x1,y1) and (x2,y2) and using the rules of probabilities (knowing that P is the probability the robot will be assigned direction1) we may return P * Probability(x1,y1, turn+1, robotvec1 ) + (1 - P) * Probability(x2,y2, turn+1, robotvec2 ) where robotvec1 is a new version of robotvec such that the robot's state is changed to 1 and robotvec2 is the version in which the robot's state changes to 2. When both of the robot's directions would lead it to leave the king in its current cell, the state only changes in the number of turns played so far, so we return Probability(x,y, turn+1, robotvec ) .

This recursive solution correctly solves the problem. However, it will time out in its current state. We should consider memoization to improve its execution time. Since w,h<=15, maxturns<=100 and <=5, the maximum number of states is 5467500 which just fits in memory. Also, every state s result is dependent only on the solution for cases with a higher value used for turn, which means that there are no cyclecs in the recurrence so implementing memoization is possible. You can use a map / hashtable structure to associate probabilities to each of the game states. Most coders that solved the problem during the match used a double array of size [15][15][101][243] to store the information of each state, the trick was to store robotvec as a number from 0 to 242 and use base-3 logic to decode that number into the array and vice versa.