← Back to all posts
competitive-programmingMar 20, 20221 min read

[LeetCode] 2212. Maximum Points in an Archery Competition explained

Updated: Mar 20, 2022

BitmaskBrute force
Available in:enko

#Problem

2212. Maximum Points in an Archery Competition

#Approach

Note that we have fairly short range of points { 0, 1, ... 11 }.
Total number of subsets is 212=40962^{12} = 4096, and each of them can be Bob's choice as long as he has enough arrows.

Brute force all the cases using bitmask, and find the maximum total point of Bob's satisfying certain condition:

int maxPoint= 0, maxMask;
for (int mask=0; mask < (1<<12); ++mask) {
    if (totalPoint(mask) > maxPoint &&
        arrowsNeeded(mask, aliceArrows) <= numArrows) {
        maxPoint= totalPoint(mask);
        maxMask= mask;
    }
}

Helper functions:

private:
    int totalPoint(int mask) {
        int point= 0;
        for (int i=0; i < 12; ++i) {
            if (mask & (1<<i)) point += i;
        }
        return point;
    }

    int arrowsNeeded(int mask, vi &aliceArrows) {
        int arrows= 0;
        for (int i=0; i < 12; ++i) {
            if (mask & (1<<i)) {
                arrows += aliceArrows[i]+1;
            }
        }
        return arrows;
    }

Now that you have the maxMask, construct the answer array:

vi ret(12,0);
int cnt= numArrows;
for (int i=1; i < 12; ++i) {
    if (maxMask & (1<<i)) {
        ret[i]= aliceArrows[i]+1;
        cnt -= ret[i];
    }
}
ret[0]= cnt;

#Code

typedef vector<int> vi;

class Solution {
private:
    int totalPoint(int mask) {
        int point= 0;
        for (int i=0; i < 12; ++i) {
            if (mask & (1<<i)) point += i;
        }
        return point;
    }

    int arrowsNeeded(int mask, vi &aliceArrows) {
        int arrows= 0;
        for (int i=0; i < 12; ++i) {
            if (mask & (1<<i)) {
                arrows += aliceArrows[i]+1;
            }
        }
        return arrows;
    }

public:
    vi maximumBobPoints(int numArrows, vi &aliceArrows) {
        int maxPoint= 0, maxMask;
        for (int mask=0; mask < (1<<12); ++mask) {
            if (totalPoint(mask) > maxPoint &&
                arrowsNeeded(mask, aliceArrows) <= numArrows) {
                maxPoint= totalPoint(mask);
                maxMask= mask;
            }
        }
        vi ret(12,0);
        int cnt= numArrows;
        for (int i=1; i < 12; ++i) {
            if (maxMask & (1<<i)) {
                ret[i]= aliceArrows[i]+1;
                cnt -= ret[i];
            }
        }
        ret[0]= cnt;
        return ret;
    }
};

#Complexity

  • Time: O(1)O(1)
  • Space: O(1)O(1)