Suppose there is a computer game, Land-of-Candy (LoC), where a player moves through a three-dimensional world defined
Question:
Suppose there is a computer game, Land-of-Candy (LoC), where a player moves through a three-dimensional world defined by the cells in an n × n × n array, C. Each cell, C[i, j, k], specifies the number of points that a player in LoC gets when they are at position (i, j, k). At the start of a game in LoC, there are only O(n) nonzero cells in C; all the other O(n3) cells in C are equal to 0. During the course of the game, if a player moves to a position (i, j, k) such that C[i, j, k] is nonzero, then all the points in C[i, j, k] are awarded to the player and the value of C[i, j, k] is reduced to 0. Then the game picks another position, (i , j , k ), at random and adds 100 points to C[i , j , k ]. The problem is that this game was designed for playing on a large computer and now must be adapted to run on a smartphone, which has much less memory. So you cannot afford to use O(n3) space to represent C, as in the original version. Describe an efficient way to represent C, which uses only O(n) space. Also describe how to lookup the value of any cell, C[i, j, k], and how to add 100 points to any cell, C[i, j, k], efficiently so that looking up the value of any cell, C[i, j, k], can be done in O(log n) worstcase time or better.
Step by Step Answer:
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia