USACO 2024 US Open Contest Bronze Division - Logical Moos#
Problem link: here
Video link: here
Solution Author: Stefan Dascalescu
Problem Solution#
So in order to solve the problem, we first need to codify the strings based on the type of expression, false/true/and/or.
If we compute the sequences of AND statements, the expression can be reduced to a list of ORs and we know that if at least one of these variables is true, the entire expression will be true.
So this leads us to the following idea: we want to find the most recent OR on the left/right as well as the most recent FALSE on the left/right. Now whenever we want to convert an entire sequence to a single variable, we know where these things have last been found as well as when these false variables show.
Basically, all we have to do now is to find for each query where the most recent OR lays to the left of L / to the right of R and if any of the subexpressions is true, then the entire expression is true and we can't change anything with just one variable replacement.
Otherwise, we need to look at the variables in the current range which are bordered by ORs, and maybe a few other variables left over from the previous sectors. If at least one of them is false (thing we can check using lastfalseL/lastfalseR, then it's false no matter what). Else, we can make it true or false as we want.
Source codes#
The source codes in C++ and Python can be seen below.
#include <iostream>
using namespace std;
int n, q, tip[200002], lastorL[200002], lastorR[200002], lastfalseL[200002], lastfalseR[200002];
int evalL[200002], evalR[200002];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
for(int i = 1; i <= n; i++)
{
string s;
cin >> s;
if(s[0] == 'f')
tip[i] = 0;
if(s[0] == 't')
tip[i] = 1;
if(s[0] == 'a')
tip[i] = 2;
if(s[0] == 'o')
tip[i] = 3;
}
// precompute lastor arrays
for(int i = 1; i <= n; i++)
if(tip[i] == 3)
lastorL[i] = i;
else
lastorL[i] = lastorL[i-1];
lastorR[n+1] = n+1;
for(int i = n; i >= 1; i--)
if(tip[i] == 3)
lastorR[i] = i;
else
lastorR[i] = lastorR[i+1];
// precompute lastfalse arrays
lastfalseL[0] = -1;
for(int i = 1; i <= n; i++)
if(tip[i] == 0)
lastfalseL[i] = i;
else
lastfalseL[i] = lastfalseL[i-1];
lastfalseR[n+1] = n+2;
for(int i = n; i >= 1; i--)
if(tip[i] == 0)
lastfalseR[i] = i;
else
lastfalseR[i] = lastfalseR[i+1];
// precompute subexpressions for left/right
int overall = 0;
for(int i = 1; i <= n; )
{
int j = i+1;
int val = tip[i];
while(j <= n && tip[j] != 3)
{
val &= (tip[j+1]);
j += 2;
}
if(val == 1)
overall = 1;
evalL[j] = overall;
i = j+1;
}
int overall2 = 0;
for(int i = n; i >= 1; )
{
int j = i-1;
int val = tip[i];
while(j >= 1 && tip[j] != 3)
{
val &= (tip[j-1]);
j -= 2;
}
if(val == 1)
overall2 = 1;
evalR[j] = overall2;
i = j-1;
}
// dealing with the cases and the queries
for(int i = 1; i <= q; i++)
{
int L, R;
string x;
cin >> L >> R;
cin >> x;
int pL = lastorL[L];
int pR = lastorR[R];
if(evalL[pL] || evalR[pR])
{
if(x == "false")
cout << "N";
else
cout << "Y";
}
else
{
if(x == "false")
cout << "Y";
else
if(lastfalseL[L-1] >= pL || lastfalseR[R+1] <= pR)
cout << "N";
else
cout << "Y";
}
}
return 0;
}
import sys
input_data = sys.stdin.read().split()
pos = 0
n = int(input_data[pos])
pos += 1
q = int(input_data[pos])
pos += 1
tip = [None] * (n + 1)
for i in range(1, n + 1):
token = input_data[pos]
pos += 1
if token[0] == 'f':
tip[i] = 0
elif token[0] == 't':
tip[i] = 1
elif token[0] == 'a': # and
tip[i] = 2
elif token[0] == 'o': # or
tip[i] = 3
lastorL = [0] * (n + 1)
for i in range(1, n + 1):
if tip[i] == 3:
lastorL[i] = i
else:
lastorL[i] = lastorL[i - 1]
lastorR = [0] * (n + 2)
lastorR[n + 1] = n + 1
for i in range(n, 0, -1):
if tip[i] == 3:
lastorR[i] = i
else:
lastorR[i] = lastorR[i + 1]
lastfalseL = [0] * (n + 1)
lastfalseL[0] = -1
for i in range(1, n + 1):
if tip[i] == 0:
lastfalseL[i] = i
else:
lastfalseL[i] = lastfalseL[i - 1]
lastfalseR = [0] * (n + 2)
lastfalseR[n + 1] = n + 2
for i in range(n, 0, -1):
if tip[i] == 0:
lastfalseR[i] = i
else:
lastfalseR[i] = lastfalseR[i + 1]
evalL = [0] * (n + 2)
evalR = [0] * (n + 2)
overall = 0
i = 1
while i <= n:
j = i + 1
val = tip[i]
while j <= n and tip[j] != 3:
if j + 1 <= n:
val &= tip[j + 1]
j += 2
if val == 1:
overall = 1
evalL[j] = overall
i = j + 1
overall2 = 0
i = n
while i >= 1:
j = i - 1
val = tip[i]
while j >= 1 and tip[j] != 3:
if j - 1 >= 1:
val &= tip[j - 1]
j -= 2
if val == 1:
overall2 = 1
evalR[j] = overall2
i = j - 1
output = []
for _ in range(q):
L = int(input_data[pos])
pos += 1
R = int(input_data[pos])
pos += 1
x = input_data[pos]
pos += 1
pL = lastorL[L]
pR = lastorR[R]
if evalL[pL] or evalR[pR]:
if x == "false":
output.append("N")
else:
output.append("Y")
else:
if x == "false":
output.append("Y")
else:
if lastfalseL[L - 1] >= pL or lastfalseR[R + 1] <= pR:
output.append("N")
else:
output.append("Y")
sys.stdout.write("".join(output))