Submission #404388

#	Time	Username	Problem	Language	Result	Execution time	Memory
404388		fvogel499	Bootfall (IZhO17_bootfall)	C++14	100 / 100	642 ms	31812 KiB

bootfall

// analysis by Francois Vogel

// first we check if when Tina stands out, two teams can be created using knapsack DP over bitset. if no : ouput 0 and return. if yes : proceed to the next step

// for every possible configuration of a player "recording", we find all possible values of Tima's strength using knapsack DP over bitset.
// to be a final Tima's possible strength, this strength must be possible for EVERY possible configuration, meaning we can just do a bitwise AND operation

// to optimize, i created startToEnd and endToStart arrays so that when calculating the knapsack in the loop, I actually only traverse at most half of the values

#include <iostream>
#include <bitset>

using namespace std;

const int siz = 250001; // consider something like n = 500 (maximum val) and ai = 500 (max val) for every i, then the biggest possible value for Tima's strength would be at most 500*500 because if it is more then Tima's strength will be bigger than the sum of the strength of all the other players, and thus no team can be created

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;

    int raw [n];
    for (int i = 0; i < n; i++) cin >> raw[i];

    bitset<siz> check(0);
    check[0] = 1;
    int checkSum = 0;
    for (int i = 0; i < n; i++) {
        check |= check<<raw[i];
        checkSum += raw[i];
    }
    if (checkSum%2 == 1 or check[checkSum/2] == 0) {
        cout << 0;
        return 0;
    }

    bitset<siz> startToEnd [n];
    startToEnd[0] = bitset<siz>(0);
    startToEnd[0][0] = 1;
    for (int i = 1; i < n; i++) {
        startToEnd[i] = startToEnd[i-1]|(startToEnd[i-1]<<raw[i-1]);
    }

    bitset<siz> endToStart [n];
    endToStart[n-1] = bitset<siz>(0);
    endToStart[n-1][0] = 1;
    for (int i = n-2; i >= 0; i--) {
        endToStart[i] = endToStart[i+1]|(endToStart[i+1]<<raw[i+1]);
    }

    bitset<siz> even;
    bitset<siz> uneven;
    even.set();
    uneven.set();
    even[0] = 0; // 0 is not a possible value for Tima's strength
    bool evenKilled = false;
    bool unevenKilled = false;
    bitset<siz> cur;
    int locSum;
    for (int i = 0; i < n; i++) {
        if (i > n/2) {
            cur = startToEnd[i];
            for (int j = i+1; j < n; j++) cur |= cur<<raw[j];
        }
        else {
            cur = endToStart[i];
            for (int j = i-1; j >= 0; j--) cur |= cur<<raw[j];
        }
        locSum = checkSum-raw[i];
        // let's say j is a possible tina's strength
        // then locSum+j % 2 == 0, so either only even values or only uneven values work
        if (locSum%2 == 0) {
            even &= cur>>(locSum/2); // if Tima's strength is 0 (virtual value as this case is actually not possible), it only works if cur[(locSum+0)/2] = 1 <--> cur[locSum] = 1, so we can simply bitshift
            if (!unevenKilled) { // unevenKilled simply tells us that it is already impossible that uneven values work so that we don't have to set them all to 0 again
                uneven &= 0; // set all bits to 0
                unevenKilled = true;
            }
        }
        else {
            uneven &= cur>>(locSum/2+1); // same logic as for locSum%2 == 0 case just that since integer division is performed and the first value taken into consideration for uneven values is 1, we must add 1 to the shift
            if (!evenKilled) { // evenKilled simply tells us that it is already impossible that uneven values work so that we don't have to set them all to 0 again
                even &= 0; // set all bits to 0
                evenKilled = true;
            }
        }
    }

    cout << even.count()+uneven.count() << endl;
    for (int i = 0; i < siz; i++) {
        if (even[i]) cout << i*2 << " ";
        if (uneven[i]) cout << i*2+1 << " ";
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 35 / 35