Wildcard Replacement WLDRPL Solution
A string S whose characters are one of the following 5: (, ), +, − and ?, is said to be a valid string if one of the following conditions holds:
- S= ?
- S=(x+y), where x and y are valid strings.
- S=(x−y), where x and y are valid strings.
For example, strings ?, (?−?), (?+(?−?)) are valid strings, while strings (?−+), ??, (?), ?−?, (?+?)) are not.
The power of a valid string S is defined to be the maximum value attainable by replacing each ? in it by either 0 or 1 and evaluating the resulting expression.
For example, the power of (?−?) is 1 because we can obtain (1−0) which evaluates to 1.
You are given a valid string S, and Q queries on it. Each query is represented by two integers L and R (L≤R). Your task is to find the power of the substring SL,SL+1,…,SR. It is guaranteed that this substring is a valid string.
Note: The input of this problem is large, so use fast input/output methods.
Input Format
- The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows:
- The first line of each test case contains the string S.
- The next line contains an integer Q, representing the number of queries to answer.
- Each of the following Q lines contains two space-separated integers, L and R, representing the query.
Output Format
For each test case, print one line containing Q space-separated integers, the i-th of which represents the answer to the i-th query.
Constraints
- 1≤T≤1000
- 1≤|S|≤106
- 1≤Q≤106
- 1≤L≤R≤|S|
- ∑|S| and ∑Q over all test cases does not exceed 106.
Subtasks
Subtask #1 (20 points):
- 1≤|S|≤1000
- 1≤Q≤1000
- ∑|S| and ∑Q over all test case does not exceed 104.
Subtask #2 (80 points):
- Original constraints
Sample Input 1
3
(?+?)
2
2 2
1 5
(?-(?-?))
2
1 9
4 8
(?-(?+?))
1
1 9
Sample Output 1
1 2
2 1
1
Explanation
Test case 1:
- Query 1: Power of the string ? is 1, as it can be converted to 1.
- Query 2: Power of the string (?+?) is 2, as it can be converted to (1+1).
Test case 2:
- Query 1: Power of the string (?−(?−?)) is 2, as it can be converted to (1−(0−1)).
- Query 2: Power of the string (?−?) is 1, as it can be converted to (1−0).
Test case 3:
- Query 1: Power of the string (?−(?+?)) is 1, as it can be converted to (1−(0+0)).
SOLUTION
Program Python: Wildcard Replacement WLDRPL Solution in Python
# cook your dish here
import sys
sys.setrecursionlimit(10**8)
t=int(input())
for _ in range(t):
s=input()
dic={}
def do(ini,s):
x,maxx,minn,sign=ini+1,0,0,True
while s[x]!=')':
char=s[x]
if char=='?':
if sign:maxx+=1
else:minn+=1
elif char=='+':sign=True
elif char=='-':sign=False
elif char=='(':
arr=do(x,s)
if sign:
maxx+=arr[0]
minn+=arr[1]
else:
maxx+=arr[1]
minn+=arr[0]
x=arr[2]
x+=1
dic[ini]=maxx
return[maxx,minn,x]
do(0,s)
q=int(input())
ans=[]
for _ in range(q):
ini,f=map(int,input().split())
if ini==f:
ans.append(1)
else:
ans.append(dic[ini-1])
print(*ans)
Program C++: Wildcard Replacement WLDRPL Solution in C++
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
map<pair<int, int>, int> minn, maxx;
map<int, int> ind;
void pre(string s, int n)
{
stack<int> st;
for (int i = 0; i < n; i++)
{
if (s[i] == '(')
st.push(i);
else if (s[i] == ')')
{
int f = st.top();
st.pop();
maxx[{f, i}] = 0;
minn[{f, i}] = 0;
for (int j = f; j < i; j++)
{
if (s[j] == '?')
maxx[{f, i}]++;
else if (s[j] == '+' and s[j + 1] == '?')
maxx[{f, i}]++, j++;
else if (s[j] == '-' and s[j + 1] == '?')
minn[{f, i}]--, j++;
else if(s[j]=='+' and s[j+1]=='(')
{
int ff = j + 1, ss = ind[ff];
maxx[{f, i}] += maxx[{ff, ss}], minn[{f, i}] += minn[{ff, ss}],j=ss;
}
else if(s[j]=='-' and s[j+1]=='(')
{
int ff = j + 1, ss = ind[ff];
maxx[{f, i}] -= minn[{ff, ss}], minn[{f, i}] -= maxx[{ff, ss}], j = ss;
}
}
}
}
}
void storeind(string s, int n)
{
stack<int> st;
for (int i = 0; i < n; i++)
{
if (s[i] == '(')
{
st.push(i);
}
else if (s[i] == ')')
{
ind[st.top()] = i;
st.pop();
}
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while (tt--)
{
string s;
cin >> s;
int q;
cin >> q;
storeind(s, s.length());
pre(s, s.length()); // store all ranges in O(n*n)
while (q--)
{
int l, r;
cin >> l >> r;
l--, r--;
if (s[l] == '(' and s[r] == ')')
cout << maxx[{l, r}] << ' ';
else
{
int p = l, ans = 0;
while (p <= r)
{
if (s[p] == '?')
ans++;
else if (s[p] == '+' and s[p + 1] == '?' and p + 1 <= r)
ans++, p++;
else if (s[p] == '+' and s[p + 1] == '(')
ans += maxx[{p, ind[p]}], p = ind[p];
else if (s[p] == '-' and s[p + 1] == '(')
ans -= minn[{p, ind[p]}], p = ind[p];
else if (s[p] == '-' and s[p + 1] == '?')
p++;
p++;
}
cout << ans << ' ';
}
}
cout << endl;
}
}
Program Java: Wildcard Replacement WLDRPL Solution in Java
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main(String args[]) throws Exception {
FastReader fr = new FastReader();
int t = fr.nextInt();
PrintWriter out = new PrintWriter(System.out);
while (t-- > 0) {
String s = fr.next();
int n = fr.nextInt();
int l = s.length();
if(l == 1) {
for (int i = 0; i < n; i++) {
fr.nextInt();
fr.nextInt();
out.print(1+ " ");
}
out.println();
continue;
}
int max[] = new int[l];
int min[] = new int[l];
int parent[] = new int[l];
int p = 0;
String stack[] = new String[l];
int stPointer = 0;
stack[stPointer++] = "0";
for (int i = 1; i < l; i++) {
if(s.charAt(i) == '(') {
stack[stPointer++] = i + "";
parent[i] = p;
p = i;
} else if(s.charAt(i) == ')') {
int right = Integer.parseInt(stack[--stPointer]);
String op = stack[--stPointer];
int left = Integer.parseInt(stack[--stPointer]);
if(op.equals("+")) {
max[p] = max[left] + max[right];
min[p] = min[left] + min[right];
} else {
max[p] = max[left] - min[right];
min[p] = min[left] - max[right];
}
p = parent[p];
} else if(s.charAt(i) == '?'){
max[i] = 1;
min[i] = 0;
stack[stPointer++] = i + "";
} else {
stack[stPointer++] = s.charAt(i) + "";
}
}
for (int i = 0; i < n; i++) {
out.print(max[fr.nextInt()-1] + " ");
fr.nextInt();
}
out.println();
}
out.close();
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}
November Long Challenge 2021 Solution
- Which Fuel is Cheaper CHEAPFUEL Solution
- Convex Hulk CONHULK Solution
- Functional Array FUNARR Solution
- Flip or Compress FLIPCOMP Solution
- Maximise the bridges MAXBRIDGE Solution
- Wildcard Replacement WLDRPL Solution
- Xor Equation XOREQN Solution
- Hill Sequence HILLSEQ Solution
- Weird Palindrome Making MAKEPAL Solution
- Equal Coins EQUALCOIN Solution Codechef