Skip to content

2836. Maximize Value of Function in a Ball Passing Game

  • Time: $O(n\log k)$
  • Space: $O(n\log k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
 public:
  long long getMaxFunctionValue(vector<int>& receiver, long long k) {
    const int n = receiver.size();
    const int m = log2(k) + 1;
    long long ans = 0;
    // jump[i][j] := node you reach after jumping 2^j steps from i
    vector<vector<int>> jump(n, vector<int>(m));
    // sum[i][j] := sum of first 2^j nodes you reach when jumping from i
    vector<vector<long long>> sum(n, vector<long long>(m));

    for (int i = 0; i < n; ++i) {
      jump[i][0] = receiver[i];
      sum[i][0] = receiver[i];
    }

    // Binary lifting.
    for (int j = 1; j < m; ++j)
      for (int i = 0; i < n; ++i) {
        const int midNode = jump[i][j - 1];
        //   node you reach after jumping 2^j steps from i
        // = node you reach after jumping 2^(j - 1) steps from i
        // + node you reach after jumping another 2^(j - 1) steps
        jump[i][j] = jump[midNode][j - 1];
        //   sum of first 2^j nodes you reach when jumping from i
        // = sum of first 2^(j - 1) nodes you reach when jumping from i
        // + sum of another 2^(j - 1) nodes you reach
        sum[i][j] = sum[i][j - 1] + sum[midNode][j - 1];
      }

    for (int i = 0; i < n; ++i) {
      long long currSum = i;
      int currPos = i;
      for (int j = 0; j < m; ++j)
        if ((k >> j & 1) == 1) {
          currSum += sum[currPos][j];
          currPos = jump[currPos][j];
        }
      ans = max(ans, currSum);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
  public long getMaxFunctionValue(List<Integer> receiver, long k) {
    final int n = receiver.size();
    final int m = (int) (Math.log(k) / Math.log(2)) + 1;
    long ans = 0;
    // jump[i][j] := node you reach after jumping 2^j steps from i
    int[][] jump = new int[n][m];
    // sum[i][j] := sum of first 2^j nodes you reach when jumping from i
    long[][] sum = new long[n][m];

    for (int i = 0; i < n; ++i) {
      jump[i][0] = receiver.get(i);
      sum[i][0] = receiver.get(i);
    }

    // Binary lifting.
    for (int j = 1; j < m; ++j)
      for (int i = 0; i < n; ++i) {
        final int midNode = jump[i][j - 1];
        //   node you reach after jumping 2^j steps from i
        // = node you reach after jumping 2^(j - 1) steps from i
        // + node you reach after jumping another 2^(j - 1) steps
        jump[i][j] = jump[midNode][j - 1];
        //   sum of first 2^j nodes you reach when jumping from i
        // = sum of first 2^(j - 1) nodes you reach when jumping from i
        // + sum of another 2^(j - 1) nodes you reach
        sum[i][j] = sum[i][j - 1] + sum[midNode][j - 1];
      }

    for (int i = 0; i < n; ++i) {
      long currSum = i;
      int currPos = i;
      for (int j = 0; j < m; ++j)
        if ((k >> j & 1) == 1) {
          currSum += sum[currPos][j];
          currPos = jump[currPos][j];
        }
      ans = Math.max(ans, currSum);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
  def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
    n = len(receiver)
    m = int(math.log2(k)) + 1
    ans = 0
    # jump[i][j] := node you reach after jumping 2^j steps from i
    jump = [[0] * m for _ in range(n)]
    # summ[i][j] := sum of first 2^j nodes you reach when jumping from i
    summ = [[0] * m for _ in range(n)]

    for i in range(n):
      jump[i][0] = receiver[i]
      summ[i][0] = receiver[i]

    # Binary lifting.
    for j in range(1, m):
      for i in range(n):
        midNode = jump[i][j - 1]
        #   node you reach after jumping 2^j steps from i
        # = node you reach after jumping 2^(j - 1) steps from i
        # + node you reach after jumping another 2^(j - 1) steps
        jump[i][j] = jump[midNode][j - 1]
        #   sum of first 2^j nodes you reach when jumping from i
        # = sum of first 2^(j - 1) nodes you reach when jumping from i
        # + sum of another 2^(j - 1) nodes you reach
        summ[i][j] = summ[i][j - 1] + summ[midNode][j - 1]

    for i in range(n):
      currSum = i
      currPos = i
      for j in range(m):
        if (k >> j) & 1 == 1:
          currSum += summ[currPos][j]
          currPos = jump[currPos][j]
      ans = max(ans, currSum)

    return ans