Wildcard Replacement WLDRPL Solution Codechef

Wildcard Replacement WLDRPL Solution

A string SS 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= ?
  • S=(x+y)S=(x+y), where xx and yy are valid strings.
  • S=(x−y)S=(x−y), where xx and yy are valid strings.

For example, strings ??, (?−?)(?−?), (?+(?−?))(?+(?−?)) are valid strings, while strings (?−+)(?−+), ????, (?)(?), ?−??−?, (?+?))(?+?)) are not.

The power of a valid string SS is defined to be the maximum value attainable by replacing each ?? in it by either 00 or 11 and evaluating the resulting expression.

For example, the power of (?−?)(?−?) is 11 because we can obtain (1−0)(1−0) which evaluates to 11.

You are given a valid string SS, and QQ queries on it. Each query is represented by two integers LL and RR (L≤RL≤R). Your task is to find the power of the substring SL,SL+1,…,SRSL,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 TT, denoting the number of test cases. The description of TT test cases follows:
  • The first line of each test case contains the string SS.
  • The next line contains an integer QQ, representing the number of queries to answer.
  • Each of the following QQ lines contains two space-separated integers, LL and RR, representing the query.

Output Format

For each test case, print one line containing QQ space-separated integers, the ii-th of which represents the answer to the ii-th query.

Constraints

  • 1≤T≤10001≤T≤1000
  • 1≤|S|≤1061≤|S|≤106
  • 1≤Q≤1061≤Q≤106
  • 1≤L≤R≤|S|1≤L≤R≤|S|
  • ∑|S|∑|S| and ∑Q∑Q over all test cases does not exceed 106106.

Subtasks

Subtask #1 (20 points):

  • 1≤|S|≤10001≤|S|≤1000
  • 1≤Q≤10001≤Q≤1000
  • ∑|S|∑|S| and ∑Q∑Q over all test case does not exceed 104104.

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 11, as it can be converted to 11.
  • Query 2: Power of the string (?+?)(?+?) is 22, as it can be converted to (1+1)(1+1).

Test case 2:

  • Query 1: Power of the string (?−(?−?))(?−(?−?)) is 22, as it can be converted to (1−(0−1))(1−(0−1)).
  • Query 2: Power of the string (?−?)(?−?) is 11, as it can be converted to (1−0)(1−0).

Test case 3:

  • Query 1: Power of the string (?−(?+?))(?−(?+?)) is 11, as it can be converted to (1−(0+0))(1−(0+0)).

Wildcard Replacement WLDRPL Solution is updated. Click Below

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

Codechef Long Challenges Solution

October Long Challenge 2021 Solution

September Long Challenge 2021 Solution

Leave a Comment