USACO 2022 December Contest Bronze Division - Reverse Engineering

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

One valid strategy to solve this problem consists in checking at each step whether there is any answer at a given position which uniquely determines the outcome of the entire subset of values.

If this happens, we remove these positions and we proceed with the remaining set of undecided strings and answers, thus making the process easier and easier gradually.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main() 
{
    int t;
    cin >> t;

    while(t--)
    {
        int n, m;
        cin >> n >> m;
        vector<string> vs(m+1);
        vector<int> vals(m+1);
        vector<int> valid;
        for(int i = 1; i <= m; i++)
        {
            cin >> vs[i] >> vals[i];
            valid.push_back(i);
        } 

        bool okk = 1;
        for(int i = 1; i <= m; i++)
            for(int j = i+1; j <= m; j++)
                if(vs[i] == vs[j] && vals[i] != vals[j])
                    okk = 0;

        if(okk == 0)
        {
            cout << "LIE\n";
            continue;
        }
        // we will run the process 1000 times for the input values and check the valid positions left

        for(int i = 1; i <= 1000; i++)
        {
            bool ok = 0;
            for(int j = 0; j < n; j++)
            {
                int zz = 0, zu = 0, uz = 0, uu = 0;
                for(int x = 0; x < valid.size(); x++)
                {
                    if(vs[valid[x]][j] == '0' && vals[valid[x]] == 0)
                        zz++;
                    if(vs[valid[x]][j] == '0' && vals[valid[x]] == 1)
                        zu++;
                    if(vs[valid[x]][j] == '1' && vals[valid[x]] == 0)
                        uz++;
                    if(vs[valid[x]][j] == '1' && vals[valid[x]] == 1)
                        uu++;
                }
                if(zz+zu && (zu == 0 || zz == 0))
                {
                    vector<int> valid2;
                    for(int x = 0; x < valid.size(); x++)
                    {
                        if(vs[valid[x]][j] == '0' && vals[valid[x]] == 0);
                        else
                            if(vs[valid[x]][j] == '0' && vals[valid[x]] == 1);
                            else
                                valid2.push_back(valid[x]);
                    }
                    valid = valid2;
                    ok = 1;
                    break;
                }
                else
                {
                    if(uz+uu && (uu == 0 || uz == 0))
                    {
                        vector<int> valid2;
                        for(int x = 0; x < valid.size(); x++)
                        {
                            if(vs[valid[x]][j] == '1' && vals[valid[x]] == 0);
                            else
                                if(vs[valid[x]][j] == '1' && vals[valid[x]] == 1);
                                else
                                    valid2.push_back(valid[x]);
                        }
                        valid = valid2;
                        ok = 1;
                        break;
                    }
                }
            }
            if(ok == 0)
                break;
        }

        if(valid.size() == 0)
            cout << "OK\n";
        else
            cout << "LIE\n";
    }

    return 0;
}

t = int(input())
for _ in range(t):
    empty = input() # python specific line
    n, m = map(int, input().split())
    vs = []
    vals = []
    valid = []
    for i in range(m):
        parts = input().split()
        vs.append(parts[0])
        vals.append(int(parts[1]))
        valid.append(i)
    okk = True
    for i in range(m):
        for j in range(i + 1, m):
            if vs[i] == vs[j] and vals[i] != vals[j]:
                okk = False
    if not okk:
        print("LIE")
        continue
    for _ in range(1000):
        ok = False
        for j in range(n):
            zz = zu = uz = uu = 0
            for x in valid:
                if vs[x][j] == '0' and vals[x] == 0:
                    zz += 1
                if vs[x][j] == '0' and vals[x] == 1:
                    zu += 1
                if vs[x][j] == '1' and vals[x] == 0:
                    uz += 1
                if vs[x][j] == '1' and vals[x] == 1:
                    uu += 1
            if (zz + zu) and (zu == 0 or zz == 0):
                valid2 = []
                for x in valid:
                    if vs[x][j] == '0':
                        continue
                    else:
                        valid2.append(x)
                valid = valid2
                ok = True
                break
            elif (uz + uu) and (uu == 0 or uz == 0):
                valid2 = []
                for x in valid:
                    if vs[x][j] == '1':
                        continue
                    else:
                        valid2.append(x)
                valid = valid2
                ok = True
                break
        if not ok:
            break
    if len(valid) == 0:
        print("OK")
    else:
        print("LIE")