Editorial for Purple Lights


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: PHPeasant

Editorialist: PHPeasant

This is a problem that can be solved by a brute-force search with a simple implementation. The main challenge was parsing the problem description itself, formulating a solution based on iterating through all possible subsets of switching lights to 'blue' (or red if you choose). For each possible combination of blue/red lights calculate the absolute difference between the blue and red light outputting the smallest value found overall.

Problem bounds ensured that standard input/output methods would suffice and that all values would fit inside integers.

A rough sketch of the intended solution follows:

cin >> t;
for(i = 0; i < t; ++i){
    cin >> n;
    int blue[n];
    int red[n];
    for(j = 0; j < n; ++j){
        cin >> blue[j];
        cin >> red[j];
    }
    int minPurp = INT32_MAX;
    //For each possible subset of 'blue' lights
    for(j = 0; j < (1<<n); ++j){
        int currVal = 0;
        for(k = 0; k < n; ++k){
            if(j&(1<<k)){
                currVal += blue[k]
            } else {
                currVal += red[k];
            }
        }
        if(abs(currVal) < minPurp)
            minPurp = abs(currVal);
    }
    cout << minpurp << endl;
}

Comments

There are no comments at the moment.