How to solve Strength of the Game from HackerEarth July Circuits 2019?

help
, ,
1

Link to the problem- Strength of the Game

This appears to be a Dynamic Programming problem but I am not getting how and there is no editorial for the problem. Can anyone please help out?

1 Like
2

@l_returns @vijju123 @penta_gone @ssjgz anybody please help

3

Untested, but should be broadly correct.

#include <iostream>
#include <vector>

#include <cassert>

using namespace std;

template <typename T>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}

int main()
{
    const int numPlayers = read<int>();
    const int m = read<int>();

    vector<int> strengths(numPlayers);
    for (auto& strength : strengths)
    {
        strength = read<int>();
    }

    const int maxPossibleStrength = 511;

    vector<vector<int64_t>> numWaysToGetStrengthForFirstPlayers(maxPossibleStrength + 1, vector<int64_t>(numPlayers + 1, 0));

    // Only one strength that can be formed with 0 players, and that is "0"!
    numWaysToGetStrengthForFirstPlayers[0][0] = 1;

    for (int playerIndex = 1; playerIndex <= numPlayers; playerIndex ++)
    {
        // Range over the possible choices for this player's strength.  NB:  the "strengths" array is 0-relative.
        for (int playerChosenStrength = 0; playerChosenStrength <= strengths[playerIndex - 1]; playerChosenStrength++)
        {
            for (int strengthFromPreviousPlayers = 0; strengthFromPreviousPlayers <= maxPossibleStrength; strengthFromPreviousPlayers++)
            {
                const int newTotalStrength = strengthFromPreviousPlayers ^ playerChosenStrength;
                numWaysToGetStrengthForFirstPlayers[newTotalStrength][playerIndex] += numWaysToGetStrengthForFirstPlayers[strengthFromPreviousPlayers][playerIndex - 1];
                numWaysToGetStrengthForFirstPlayers[newTotalStrength][playerIndex] = numWaysToGetStrengthForFirstPlayers[newTotalStrength][playerIndex] % 1'000'000'007ULL;

            }
        }
    }

    for (int totalStrength = 0; totalStrength <= m; totalStrength++)
    {
        cout << numWaysToGetStrengthForFirstPlayers[totalStrength][numPlayers] << endl;
    }
}
1 Like
4

Can you please explain the approach?

5

Let’s say we know the number of ways of getting a game of strength X (for X = 0, 1, … maxPossibleStrength) using only the first k players - call it
numWaysToGetStrengthForFirstPlayers[X][k].

Can we deduce the number of ways of getting strength (for X = 0, 1, … maxPossibleStrength) with the first k+1 players (i.e. numWaysToGetStrengthForFirstPlayers[X][k+1]?)

Think about how we might do this (there’s obviously a big clue in the code :)) - there are strength[k] + 1 possible values for the strength of the (k + 1)th player - iterate over them, and combine them with the possible strengths that can be formed from the first k players.

2 Likes
6

Thanks buddy. Got it(from the code ofcourse :sweat_smile: but still helpful). You are awesome. Thank you.

1 Like
7

@ssjgz I have one question though, does this problem really count as Dynamic Programming one? For sure, we are caching all of the previous results and using them to compute the newer ones, which implies the existence of Overlapping Subproblems. But does it have the Optimal Substructure property? I don’t see that it does. Correct me if I am wrong.

8

IMO, there’s always a bit of subjectivity re: whether a solution counts as DP or not. I usually just avoid the question of whether it counts as DP completely :slight_smile:

1 Like
9

C++ Sol → https://ideone.com/Uch6GC