Skip to content

2212. Maximum Points in an Archery Competition 👍

  • Time: $O(2^{12} \cdot 12) = O(1)$
  • Space: $O(2^{12}) = O(1)$
 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:
  vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) {
    constexpr int allMask = (1 << 12) - 1;
    int maxPoint = 0;
    int maxMask = 0;

    for (int mask = 0; mask < allMask; ++mask) {
      const auto& [shotable, point] =
          getShotableAndPoint(mask, numArrows, aliceArrows);
      if (shotable && point > maxPoint) {
        maxPoint = point;
        maxMask = mask;
      }
    }

    return getBobsArrows(maxMask, numArrows, aliceArrows);
  }

 private:
  pair<bool, int> getShotableAndPoint(int mask, int leftArrows,
                                      const vector<int>& aliceArrows) {
    int point = 0;
    for (int i = 0; i < 12; ++i)
      if (mask >> i & 1) {
        leftArrows -= aliceArrows[i] + 1;
        point += i;
      }
    return {leftArrows >= 0, point};
  }

  vector<int> getBobsArrows(int mask, int leftArrows,
                            const vector<int>& aliceArrows) {
    vector<int> bobsArrows(12);
    for (int i = 0; i < 12; ++i)
      if (mask >> i & 1) {
        bobsArrows[i] = aliceArrows[i] + 1;
        leftArrows -= aliceArrows[i] + 1;
      }
    bobsArrows[0] = leftArrows;
    return bobsArrows;
  }
};

 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
class Solution {
  public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
    final int allMask = (1 << 12) - 1;
    int maxPoint = 0;
    int maxMask = 0;

    for (int mask = 0; mask < allMask; ++mask) {
      Pair<Boolean, Integer> pair = getShotableAndPoint(mask, numArrows, aliceArrows);
      final boolean shotable = pair.getKey();
      final int point = pair.getValue();
      if (shotable && point > maxPoint) {
        maxPoint = point;
        maxMask = mask;
      }
    }

    return getBobsArrows(maxMask, numArrows, aliceArrows);
  }

  private Pair<Boolean, Integer> getShotableAndPoint(int mask, int leftArrows, int[] aliceArrows) {
    int point = 0;
    for (int i = 0; i < 12; ++i)
      if ((mask >> i & 1) == 1) {
        leftArrows -= aliceArrows[i] + 1;
        point += i;
      }
    return new Pair<>(leftArrows >= 0, point);
  }

  int[] getBobsArrows(int mask, int leftArrows, int[] aliceArrows) {
    int[] bobsArrows = new int[12];
    for (int i = 0; i < 12; ++i)
      if ((mask >> i & 1) == 1) {
        bobsArrows[i] = aliceArrows[i] + 1;
        leftArrows -= aliceArrows[i] + 1;
      }
    bobsArrows[0] = leftArrows;
    return bobsArrows;
  }
}

 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
class Solution:
  def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
    allMask = (1 << 12) - 1
    maxPoint = 0
    maxMask = 0

    def getShotableAndPoint(mask: int, leftArrows: int) -> Tuple[bool, int]:
      point = 0
      for i in range(12):
        if mask >> i & 1:
          leftArrows -= aliceArrows[i] + 1
          point += i
      return leftArrows >= 0, point

    for mask in range(allMask):
      shotable, point = getShotableAndPoint(mask, numArrows)
      if shotable and point > maxPoint:
        maxPoint = point
        maxMask = mask

    def getBobsArrows(mask: int, leftArrows: int) -> List[int]:
      bobsArrows = [0] * 12
      for i in range(12):
        if mask >> i & 1:
          bobsArrows[i] = aliceArrows[i] + 1
          leftArrows -= aliceArrows[i] + 1
      bobsArrows[0] = leftArrows
      return bobsArrows

    return getBobsArrows(maxMask, numArrows)