All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Boolean Expressions
Tag(s):

Combinatorics, Dynamic Programming, Mathematics, Medium, Two dimensional

Problem
Editorial
Analytics

Roy is intrigued by the fact that the evaluated value of boolean expressions can easily vary depending upon the order of evaluation !

For instance, consider the example:

Expression: 1 xor 1 and 0

We can have following two interpretations:

1.  ((1 xor 1) and 0) => (0 and 0) => 0
2.  (1 xor (1 and 0)) => (1 xor 0) => 1

Now, he is further interested into finding the number of possible different parenthesizations such that the result of computation is res.

Input:

The first line of input file contains two space-separated strings. The first string denotes the literals of our boolean expression S, the second string denotes the operators. The next line denotes an integer q, i.e. the number of queries to follow. Each of the next q lines contain two space separated integers l and r and a string res, which is either true or false.

Output:

For each query. output in a new line, the number of ways in which the boolean expression of substring [l,r] can be parenthesized so that it evaluates to res. As the output can be very large, please print the answer modulo 1000000009.

Constraints:

1 <= |S| <= 300
1 <= q <= 90000
1 <= l <= r <= |S|

Notes:

  • No order of precedence is to be considered. The expression should be fully parenthesized.
  • Two parenthesizations are considered different if the parenthesized string produced is different.
  • The string of operations shall contain only characters 'a', 'o' and 'x' representing and, or and xor operations respectively
SAMPLE INPUT
110 ax
3
1 1 true
1 2 false
2 3 false
SAMPLE OUTPUT
1
0
0
Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

Christmas Coding Marathon

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?