StarAdventure - TopCoder


https://community.topcoder.com/stat?c=problem_statement&pm=2940&rd=5854
    The latest version of your favorite adventure game has just been released. On each level you search for stars that earn you points. Simply moving over a location containing stars allows you to acquire them. To help you on your journey, you are given an overhead map of the level in a String[]. Each character in level describes the number of stars at that location. You begin in the upper left spot of the map (character 0 of element 0 of level). On the current stage you must move according to the following rules:
  • 1) On the first pass you may only move downward or rightward each move (not diagonally) until you reach the lower right corner.
  • 2) The second pass begins in the lower right corner where the first pass ended, and proceeds back to the beginning using only upward and leftward steps (not diagonal).
  • 3) The final pass, like the first pass, begins in the upper left corner and proceeds to the lower right corner using only rightward and downward (not diagonal) steps.
Once the stars on a spot are claimed, they cannot be claimed again on a future pass. Return the largest possible number of stars that can be acquired.

http://www.hawstein.com/posts/dp-novice-to-advanced.html
给定一个M行N列的矩阵(M*N个格子),每个格子中放着一定数量的苹果。 你从左上角的格子开始,只能向下或向右走,目的地是右下角的格子。 你每走过一个格子,就把格子上的苹果都收集起来。然后你从右下角走回左上角的格子, 每次只能向左或是向上走,同样的,走过一个格子就把里面的苹果都收集起来。 最后,你再一次从左上角走到右下角,每过一个格子同样要收集起里面的苹果 (如果格子里的苹果数为0,就不用收集)。求你最多能收集到多少苹果。
注意:当你经过一个格子时,你要一次性把格子里的苹果都拿走。
限制条件:1 < N, M <= 50;每个格子里的苹果数量是0到1000(包含0和1000)。
如果我们只需要从左上角的格子走到右下角的格子一次,并且收集最大数量的苹果, 那么问题就退化为“中级”一节里的那个问题。将这里的问题规约为“中级”里的简单题, 这样一来会比较好解。让我们来分析一下这个问题,要如何规约或是修改才能用上DP。 首先,对于第二次从右下角走到左上角得出的这条路径, 我们可以将它视为从左上角走到右下角得出的路径,没有任何的差别。 (即从B走到A的最优路径和从A走到B的最优路径是一样的)通过这种方式, 我们得到了三条从顶走到底的路径。对于这一点的理解可以稍微减小问题的难度。 于是,我们可以将这3条路径记为左,中,右路径。对于两条相交路径(如下图):
在不影响结果的情况下,我们可以将它们视为两条不相交的路径:
这样一来,我们将得到左,中,右3条路径。此外,如果我们要得到最优解, 路径之间不能相交(除了左上角和右下角必然会相交的格子)。因此对于每一行y( 除了第一行和最后一行),三条路径对应的x坐标要满足:x1[y] < x2[y] < x3[y]。 经过这一步的分析,问题的DP解法就进一步地清晰了。让我们考虑行y, 对于每一个x1[y-1],x2[y-1]和x3[y-1],我们已经找到了能收集到最多苹果数量的路径。 根据它们,我们能求出行y的最优解。现在我们要做的就是找到从一行移动到下一行的方式。 令Max[i][j][k]表示到第y-1行为止收集到苹果的最大数量, 其中3条路径分别止于第i,j,k列。对于下一行y,对每个Max[i][j][k] 都加上格子(y,i),(y,j)和(y,k)内的苹果数量。因此,每一步我们都向下移动。 我们做了这一步移动之后,还要考虑到,一条路径是有可能向右移动的。 (对于每一个格子,我们有可能是从它上面向下移动到它, 也可能是从它左边向右移动到它)。为了保证3条路径互不相交, 我们首先要考虑左边的路径向右移动的情况,然后是中间,最后是右边的路径。 为了更好的理解,让我们来考虑左边的路径向右移动的情况,对于每一个可能的j,k对(j<k), 对每个i(i<j),考虑从位置(i-1,j,k)移动到位置(i,j,k)。处理完左边的路径, 再处理中间的路径,最后处理右边的路径。方法都差不多。
https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/
Given a matrix with M rows and N columns (N x M). In each cell there’s a number of apples.
You start from the upper-left corner of the matrix. You can go down or right one cell. You need to arrive to the bottom-right corner. Then you need to go back to the upper-left cell by going each step one cell left or up. Having arrived at this upper-left cell, you need to go again back to the bottom-right cell.
Find the maximum number of apples you can collect.
When you pass through a cell – you collect all the apples left there.
Restrictions: 1 < NM <= 50 ; each cell contains between 0 and 1000 apples inclusive.
First of all we observe that this problem resembles to the classical one (described in Section 3 of this article), in which you need to go only once from the top-left cell to the bottom-right one, collecting the maximum possible number of apples. It would be better to try to reduce the problem to this one. Take a good look into the statement of the problem – what can be reduced or modified in a certain way to make it possible to solve using DP? First observation is that we can consider the second path (going from bottom-right cell to the top-left cell) as a path which goes from top-left to bottom-right cell. It makes no difference, because a path passed from bottom to top, may be passed from top to bottom just in reverse order. In this way we get three paths going from top to bottom. This somehow decreases the difficulty of the problem. We can consider these 3 paths as left, middle and right. When 2 paths intersect (like in the figure below)


we may consider them as in the following picture, without affecting the result:


This way we’ll get 3 paths, which we may consider as being one left, one middle and the other – right. More than that, we may see that for getting an optimal results they must not intersect (except in the leftmost upper corner and rightmost bottom corner). So for each row y (except first and last), the x coordinates of the lines (x1[y] x2[y] and respectively x3[y] ) will be : x1[y] x2[y] x3[y] . Having done that – the DP solution now becomes much clearer. Let’s consider the row y. Now suppose that for any configuration of x1[y-1] x2[y-1] and x3[y-1] we have already found the paths which collect the maximum number of apples. From them we can find the optimal solution for row y. We now have to find only the way for passing from one row to the next one. Let Max[i][j][k] represent the maximum number of apples collected till row y-1inclusive, with three paths finishing at column ij, and respectively k. For the next row y, add to each Max[i][j][k] (obtained previously) the number of apples situated in cells (y,i) , (y,j) and (y,k). Thus we move down at each step. After we made such a move, we must consider that the paths may move in a row to the right. For keeping the paths out of an intersection, we must first consider the move to the right of the left path, after this of the middle path, and then of the right path. For a better understanding think about the move to the right of the left path – take every possible pair of, k (where j<k), and for each i (1 i<j) consider the move from position (i-1,j,k) to position (i,j,k). Having done this for the left path, start processing the middle one, which is done similarly; and then process the right path.
https://github.com/gabesoft/topc/blob/master/src.archive.1/dynamic/StarAdventure.java

  int N;
  int M;
  int[][] data;
  int[][][] best;
  int[][][] sums;

  public int mostStars(String[] level) {
    N = level.length;
    M = level[0].length();
    data = new int[N][M];
    sums = new int[N][M][M];

    for (int i = 0; i < N; i++) {
      char[] chars = level[i].toCharArray();
      for (int j = 0; j < M; j++) {
        data[i][j] = chars[j] - '0';
      }
    }

    computeSums();

    if (M <= 3) { return sumAll(); }

    best = new int[M][M][M];
    for (int y = 0; y < N; y++) {
      int[][][] curr = new int[M][M][M];
      for (int i = 0; i < M - 2; i++) {
        for (int j = i + 1; j < M - 1; j++) {
          for (int k = j + 1; k < M; k++) {
            curr[i][j][k] = findBest(y, i, j, k);
          }
        }
      }
      best = curr;
    }

    return best[M - 3][M - 2][M - 1];
  }

  int findBest(int row, int i, int j, int k) {
    int curr = 0;

    for (int ip = 0; ip < i + 1; ip++) {
      for (int jp = i + 1; jp < j + 1; jp++) {
        for (int kp = j + 1; kp < k + 1; kp++) {
          curr = Math.max(curr, best[ip][jp][kp] + sums[row][ip][i] + sums[row][jp][j] + sums[row][kp][k]);
        }
      }
    }

    return curr;
  }

  void computeSums() {
    for (int y = 0; y < N; y++) {
      for (int i = 0; i < M; i++) {
        for (int j = i; j < M; j++) {
          sums[y][i][j] = sum(y, i, j);
        }
      }
    }
  }

  int sum(int row, int start, int end) {
    int res = 0;
    for (int i = start; i < end + 1; i++) { res += data[row][i]; }
    return res;
  }

  int sumAll() {
    int res = 0;
    for (int i = 0; i < N; i++) { res += sums[i][0][M - 1]; }
    return res;
  }

http://blog.gogo244.tw/2015/07/30/topcoder-srm-208-div1-staradventure/
    public int mostStars(String[] level) {
        int row = level.length;
        int col = level[0].length();
        int[][] map = new int[row][col];
        int total = 0;
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                map[i][j] = level[i].charAt(j) - '0';
                total += map[i][j];
            }
        }
        if (col < 4 || row < 4) {
            return total;
        }
        int[][][][] max = new int[row][col-2][col-1][col];
        for (int r=0; r<row; r++) {
            for (int i=0; i<col-2; i++) {
                for (int j=i+1; j<col-1; j++) {
                    for (int k=j+1; k<col; k++) {
                        if (r == 0) {
                            for (int l=0; l<=k; l++) {
                                max[r][i][j][k] += map[0][l];
                            }
                        } else {
                            // Find the max for max[r][i][j][k] form max[r-1]...
                            int maxp = 0;
                            for (int ii=0; ii<=i; ii++) {
                                for (int jj=ii+1; jj<=j; jj++) {
                                    for (int kk=jj+1; kk<=k; kk++) {
                                        int tmp = max[r-1][ii][jj][kk];
                                        if (ii < i) {
                                            // Add move
                                            for (int a=ii; a<i; a++) {
                                                tmp += map[r][a];
                                            }
                                        }
                                        tmp += map[r][i];
                                        if (jj < j) {
                                            for (int b=jj; b<j; b++) {
                                                // Avoid duplicate add
                                                if (b > i) {
                                                    tmp += map[r][b];
                                                }
                                            }
                                        }
                                        tmp += map[r][j];
                                        if (kk < k) {
                                            for (int c=kk; c<k; c++) {
                                                // Avoid duplicate add
                                                if (c > j) {
                                                    tmp += map[r][c];
                                                }
                                            }
                                        }
                                        tmp += map[r][k];
                                        if (tmp > maxp) {
                                            maxp = tmp;
                                        }
                                    }
                                }
                            }
                            max[r][i][j][k] = maxp;
                        }
                    }
                }
            }
        }
        // debug
        /*
        for (int i=0; i<col-2; i++) {
            for (int j=i+1; j<col-1; j++) {
                for (int k=j+1; k<col; k++) {
                    System.out.printf("max[0][%d][%d][%d] = %d%n", i, j, k, max[0][i][j][k]);
                }
            }
        }
        for (int i=0; i<col-2; i++) {
            for (int j=i+1; j<col-1; j++) {
                for (int k=j+1; k<col; k++) {
                    System.out.printf("max[1][%d][%d][%d] = %d%n", i, j, k, max[1][i][j][k]);
                }
            }
        }
        */
        return max[row-1][col-3][col-2][col-1];
    }

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts