Wildcard Replacement WLDRPL Solution

Wildcard Replacement WLDRPL Solution Codechef

by

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

Leave a Comment

6 + 8 =