TCO qual 1A

Got a bit lucky and qualified in round 1A.

p250, easy if you see 2 counts are enough to win. An edge case is when there is only 1 player.

p500, if you see prime factoring, you got the problem. I am just slow in implementing it.

p1000, easy in algorithm but hard in implementation. Has some connection with 2SAT but you do not need that knowledge. I had the right algorithm but took two days to finalize the details of implementation. Guess my recursion/dfs implementation skills are terrible.

Here is my solution (offline)

#include <vector>
#include <string>
#include <iostream>
using namespace std;

#define MAX 1000
#define sz(a) int(a.size())

int bulb[60][5], state[60], tmp[60];
string initial;
vector<string> switches;

class EllysLights {
public:
int getMinimum(string _initial, vector <string> _switches);
};

bool dfs(int j, int st)
{
    tmp[j]=st;
    // check all bulbs
    for(int i=0; i<sz(initial); ++i) if (switches[j][i]=='Y') {
        int next;
        if (bulb[i][1]<0) { // bulb has one switch
            if (st == 0 && initial[i]=='N') {}
            else if (st == 1 && initial[i]=='Y') {}
            else return false;
        }
        else { // bulb has two switch
            next = bulb[i][0]; if (next==j) next = bulb[i][1];
            int target;
            if (initial[i]=='N') target = st;
            else target = 1-st;
            if (tmp[next]>=0) { // hit a visited switch
                if (tmp[next]!=target) return false;
            }
            else {
                if (!dfs(next, target)) return false;
            }
        }
    }
    return true;
}

int check(int j, int st)
{
    memset(tmp, -1, sizeof tmp);
    int ans=0;
    if (dfs(j, st)) {
        for(int k=0; k<sz(switches); ++k)
            ans += (tmp[k]==1);            
        return ans;
    }
    return MAX;
}

int EllysLights::getMinimum(string _initial, vector <string> _switches)
{
    int ans=0;
    initial=_initial; switches=_switches;
    memset(state, -1, sizeof state);
    // construct bulb
    memset(bulb, -1, sizeof bulb);
    for(int i=0; i<sz(initial); ++i) {
        int c=0;
        for(int j=0; j<sz(switches); ++j) {    
            if (switches[j][i]=='Y') bulb[i][c++]=j;
        }
    }
    for(int i=0; i<sz(initial); ++i) {
        if (bulb[i][0]<0 && initial[i]=='Y') return -1;
    }
    for(int j=0; j<sz(switches); ++j) if (state[j]<0) {
        int aa, bb;
        aa = check(j, 0); for(int k=0; k<sz(switches); ++k) if (tmp[k]>=0) state[k]=tmp[k];
        bb = check(j, 1);        
        if (bb < aa) {
            for(int k=0; k<sz(switches); ++k) if (tmp[k]>=0) state[k]=tmp[k];
        }
        ans += min(aa, bb);

//        cout << "switch " << j << ' ' << state[j] << ' ' << ans << endl;
    }
    if (ans <= sz(switches))
        return ans;
    else 
        return -1;
}