WLDRPL - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Manan Grover
Tester: Samarth Gupta
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Binary Trees, String parsing.

PROBLEM

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.

You have a valid string S and Q queries on it. Each query is represented by two integers L and R (L\leq R).

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.

Your task is to find the power of the substring S_L, S_{L+1}, \dots, S_R. It is guaranteed that this substring is a valid string.

QUICK EXPLANATION

  • The given string expression can be represented by a binary tree, where each internal node stores the sign, and each ? corresponds to a leaf node in a binary tree
  • For each node, compute the minimum and maximum value attainable at the node, by evaluating the expression represented by subtree of that node, if each leaf in the subtree is replaced by 0 and 1.
  • To answer queries, determine which range corresponds to which node in the binary tree, and print the maximum value attainable at that node.

EXPLANATION

From string expression to binary tree

The string representation is not really a convenient way to evaluate mathematical expressions. Let us find a way to represent it better.

Referring to the definition of valid string, we can see that it is defined recursively. So most likely a recursive data structure would be an ideal choice for representation. One such data structure is a tree.

A Tree can be

  • A single leaf node
  • A node having one or more trees as its children.

Referring to this image from wikipedia on page binary expression tree
image

Above tree represents expresson (((a+b)*c)+7).

In our problem, we need to build this binary expression tree, in which ? represents the leaf node, and each internal node will store the arithmetic operators correspondings to the expression in the subtree.

Processing this binary tree for the maximum value of an expression

Now that we have a rooted binary tree, we want to compute the maximum attainable value of the expression in each node’s subtree. Since the attainable value of a node depends upon the attainable value of its children, it is only natural to process the leaf nodes first, then their parent, and so on. In this order, first, all children of the current node are processed. Based on values computed for children, the value for the current node is computed.

Here, let’s say we have computed the maximum attainable value for each child of the current node. Some of these nodes have a positive sign while some have a negative sign.

To obtain the maximum value for the current node, it’d be optimal to choose the maximum attainable value for nodes with a positive sign, and choose the minimum attainable value for nodes with negative sign.

Subtracting the minimum value would be optimal as it maximizes the final value.

For example, let’s assume we have expression (x-y) where x can take values in range [4,7] and y can take values in range [3, 9]. To maximize (x-y), it is best to choose x = 4 and y = 3.

Hence, in order to compute maximum attainable values, we also need to compute minimum attainable values for expression in the subtree of each node.

Answering queries

Let’s assume, for each node, we have calculated the maximum attainable value of expression of that node. But query specifies the range in terms of indices of string S. How do we identify which node covers the exact interval given?

An important fact here is that each node in the binary expression tree corresponds to a substring in expression. For example, in string S = (((a+b)*c)+7) substring from 2 to 9 corresponds to the node having * sign in the image.

An observation we can make is that we can compute the intervals corresponding to each node at the time of construction of the binary expression tree. Then we only need to identify the node, which can be done using a map or a binary search.

TIME COMPLEXITY

The preprocessing part takes O(N) time. The queries can be processed in O(Q) or O(Q*log(N)) depending upon implementation.

So the overall time complexity is O(N+Q*log(N)) per test case.

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t;
  cin>>t;
  while(t--){
    string s;
    cin>>s;
    int n = s.size();
    int dp[n];
    int temp = 1;
    vector<int> v;
    for(int i = 0; i < n; i++){
      if(s[i] == ')'){
        dp[i] = dp[v.back()];
        v.pop_back();
        temp = dp[i];
        continue;
      }
      dp[i] = temp;
      if(s[i] == '('){
        v.push_back(i);
      }
      if(s[i] == '-'){
        temp = 1 - temp;
      }
    }
    int a[n][2] = {};
    if(s[0] == '?'){
      a[0][dp[0]]++;
    }
    for(int i = 1; i < n; i++){
      a[i][0] += a[i - 1][0];
      a[i][1] += a[i - 1][1];
      if(s[i] == '?'){
        a[i][dp[i]]++;
      }
    }
    int q;
    cin>>q;
    while(q--){
      int l, r;
      cin>>l>>r;
      l--;
      r--;
      if(l == r){
        cout<<1<<" ";
      }else{
        cout<<a[r][dp[l]] - a[l][dp[l]]<<" ";
      }
    }
    cout<<"\n";
  }
  return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;

long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}
 
void readEOF(){
    assert(getchar()==EOF);
}
int main() {
    // your code goes here
    int t;
    t = readIntLn(1, 1000);
    int sum = 0;
    int sumq = 0;
    while(t--){
        string str;
        str = readStringLn(1, 1e6);
        vector<int> vec;
        int n = str.size();
        sum += n;
        assert(sum <= 1e6);
        int close[n];
        int dp_max[n], dp_min[n];
        
        for(int i = 0; i < n ; i++){
            if(str[i] == '(')
                vec.push_back(i);
            else if(str[i] == ')'){
                assert(vec.size() > 0);
                close[i] = vec.back();
                vec.pop_back();
                if(str[i-1] == ')'){
                    int l_prev = close[i-1];
                    assert(str[l_prev-1] == '+' || str[l_prev-1] == '-');
                    if(str[l_prev-2] == '?'){
                        assert(close[i] == l_prev-3);
                        if(str[l_prev-1] == '+')
                            dp_max[i] = 1 + dp_max[i-1], dp_min[i] = dp_min[i-1];
                        else
                            dp_max[i] = 1 - dp_min[i-1], dp_min[i] = -dp_max[i-1];
                    }
                    else{
                        assert(str[l_prev-2] == ')');
                        int l_prev_prev = close[l_prev-2];
                        assert(close[i] == l_prev_prev - 1);
                        if(str[l_prev-1] == '+')
                            dp_max[i] = dp_max[l_prev-2] + dp_max[i-1], dp_min[i] = dp_min[l_prev-2] + dp_min[i-1];
                        else
                            dp_max[i] = dp_max[l_prev-2] - dp_min[i-1], dp_min[i] = dp_min[l_prev - 2] - dp_max[i-1];
                    }
                }
                else{
                    assert(str[i-1] == '?');
                    assert(str[i-2] == '+' || str[i-2] == '-');
                    if(str[i-3] == '?'){
                        assert(close[i] == i - 4);
                        if(str[i-2] == '+')
                            dp_max[i] = 2, dp_min[i] = 0;
                        else
                            dp_max[i] = 1, dp_min[i] = -1;
                    }
                    else{
                        assert(str[i-3] == ')');
                        int l_prev = close[i - 3];
                        assert(close[i] == l_prev - 1);
                        if(str[i-2] == '+')
                            dp_max[i] = dp_max[i-3] + 1, dp_min[i] = dp_min[i-3];
                        else
                            dp_max[i] = dp_max[i-3], dp_min[i] = dp_min[i-3] - 1;
                    }
                }
            }
            else{
                assert(str[i] == '?' || str[i] == '+' || str[i] == '-');
                assert(vec.size() > 0);
            }
        }
        assert(vec.size() == 0);
        int q = readIntLn(1, 1e6);
        sumq += q;
        assert(sumq <= 1e6);
        while(q--){
            int l, r;
            l = readIntSp(1, n);
            r = readIntLn(l, n);
            l--, r--;
            if(l == r){
                assert(str[l] == '?');
                cout << 1 << " ";
            }
            else{
                assert(str[r] == ')');
                assert(str[l] == '(');
                assert(close[r] == l);
                cout << dp_max[r] << " ";
            }
        }
        cout << '\n';
    }
    readEOF();
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class WLDRPL{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        String S = n();
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int ID = 0;
        int N = S.length();
        int[] st = new int[N], en = new int[N], par = new int[N];
        //st[i] -> start position of range of ith node
        //en[i] -> end position of range of ith node
        //par[i] -> id of parent of ith node
        boolean[] negative = new boolean[N];
        boolean neg = false;
        //Expression parsing
        for(int i = 0; i< S.length(); i++){
            if(S.charAt(i) == '?'){
                st[ID] = i;
                en[ID] = i;
                par[ID] = stack.peek();
                negative[ID] = neg;
                neg = false;
                ID++;
            }else if(S.charAt(i) == '('){
                st[ID] = i;
                par[ID] = stack.peek();
                negative[ID] = neg;
                neg = false;
                stack.push(ID);
                ID++;
            }else if(S.charAt(i) == ')'){
                int id = stack.pop();
                en[id] = i;
            }else if(S.charAt(i) == '-')neg = true;
        }
        
        //Building binary tree
        List<Integer>[] adj = new ArrayList[ID];
        for(int i = 0; i< ID; i++)adj[i] = new ArrayList<>();
        for(int i = 1; i< ID; i++)adj[par[i]].add(i);
        int[] min = new int[ID], max = new int[ID];
        for(int i = ID-1; i >= 0; i--){
            if(st[i] == en[i]){
                min[i] = 0;
                max[i] = 1;
            }else{
                for(int v:adj[i]){
                    if(negative[v]){
                        min[i] -= max[v];
                        max[i] -= min[v];
                    }else{
                        min[i] += min[v];
                        max[i] += max[v];
                    }
                }
            }
        }
        
        for(int Q = ni(); Q > 0; Q--){
            int L = ni()-1, R = ni()-1;
            int lo = 0, hi = ID-1;
            while(lo < hi){
                int mid = lo + (hi-lo)/2;
                if(st[mid] >= L)hi = mid;
                else lo = mid+1;
            }
            hold(en[hi] == R);
            p(max[hi]+" ");
        }
        pn("");
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new WLDRPL().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

2 Likes

I solved this problem using a stack. First I wrote a solution that solved each test case in O(QN) time and then I memoized the results to avoid redundant computations to reduce the complexity to O(N+Q).

First subtask:
For each query, iterate from L to R. Whenever you see a “(”, “+” or “-”, push it on the stack. Whenever you see a “?”, push a pair [1,0] on the stack (denoting [max value, min value] that the “?” can be replaced with).
Whenever you see a “)”, the top of the stack is guaranteed to look like this:
[..., "(", pair[amax,amin], operator, pair[bmax,bmin] ]
This is because the queries are all well-formed. So you pop 4 times from the stack and you receive two pairs [amax,amin] and [bmax,bmin], an operator (+ or -) and a “(”.
Push onto the stack a pair [cmax,cmin] denoting the maximum value and minimum value that this part can have.

If the operator is plus:
cmax = amax + bmax
cmin = amin + bmin

If the operator is minus:
cmax = amax - bmin
cmin = amin - bmax

When you reach R, the stack will basically be storing one pair denoting the maximum value and the minimum value the part [L, R] can have. Output the maximum value.

Second subtask:
Just add memoization to the above. Whenever you see a “)” also store the resulting value in a dictionary keyed by the index of the corresponding “(”. And whenever you see a “(”, first check if the dictionary contains the answer for the query starting at this “(” or not. If it does, just get it from the dictionary and push it on the stack and then jump to the index of the corresponding “)”. This way, you won’t perform redundant computations.

Link to my solution: Solution: 53810203 | CodeChef

10 Likes

I solved this question using dynamic programming. The idea is similar to the one mentioned in the editorial, but I find working with arrays easier than working with trees.

Code: Solution: 53545861 | CodeChef

I also solved it using stack. Here’s the Cpp implementation of stack approach Solution: 53703624 | CodeChef

Hii , I try to solve it using recursion but i am getting RE(NZEC) in last subtask , can any one tell me What’s wrong in my code.
I think RE due to Memory Limit Exceed.
https://www.codechef.com/viewsolution/53791461

I used dynamic programming too. But I also stored the size of the substring in addition to its lowest and its highest possible value. This resulted in a somewhat shorter and cleaner code: Solution: 53803465 | CodeChef

i made this quition with simple array traversal and stack for storeing the +/_ but got wrong ans in the major tast case
please help me to find where im doing the mistack
solution:53831413

Thanks for sharing the code. I learned a lot from it.

2 Likes

@an2609 please take look at my code and help me to finding the mistack i did
you can copy the code and run in your compiler to check the custom tast cases of yours and suggest me

Thanks for the solution akamoha. Do you have any good links to explain why/how you use:

‘sys’, ‘stdin’,‘readline()’

These are the only things I am not familiar with (assuming this is a way to process input/output faster?- I could be wrong here!). Thanks

1 Like

can someone please tell me the error in my approach?

i just checked for each ‘?’ if it is supposed to be negative or positive after opening the brackets. if its negative then it should be zero else it should be 1

https://www.codechef.com/viewsolution/53807215

Yes you’re right, that is a way to process I/O faster in Python. I found it by “Googling fast I/O in Python geeksforgeeks”. The first couple of geeksforgeeks articles have some example code for fast I/O.
BTW, are you an Odablock fan?

I used prefix sum array to solve the problem. Helped me to understand how array type data structures works: Solution: 53821101 | CodeChef

Example:
(?-(?+?)-(?-?)+(?+?)-((?-?)-?)+?)
turns to:
010100000200000400000610000010070

https://www.codechef.com/viewsolution/53905814
I am getting TLE in two of the test cases I am using a stack to solve the problem as described in the comments and have also used dp to avoid redundant computing. Could someone tell me what I am doing wrong?
Thank you

You should use optimal data structures according to the language you are using. For java you should use Deque rather than Stack. Also use the class you have defined (MaxMin) rather than int array (int[]). This will make your solution fast enough to pass all the test cases. Here’s the updated solution Solution: 53914680 | CodeChef

1 Like

I have used your approch of storing min, max and size in the dp but my solution fails , it showing TLE and RE can you figure out where’s the mistake, my code and approch is same as yours Solution 53986787 | codechef

In C++ it’s necessary to pass the string to function isValid by reference, otherwise it will be copied with a huge overhead on every call (in D language strings are different and don’t need this). Everything else looks fine.

Thank you so much, sir !!

1 Like

Thanks, It’s giving AC now thank you once again bro, I have learned a lot from this discussion.

Thanks man, that’s exactly what I googled tbh.

And yea big Oda fan :joy: guessing you are too? hahaha

Gotta put some love on that baldy’s name :rofl: