Count Strings
Problem Statement :
A regular expression is used to describe a set of strings. For this problem the alphabet is limited to 'a' and 'b'.
We define to be a valid regular expression if:
1) is "" or "".
2) is of the form "", where and are regular expressions.
3) is of the form "" where and are regular expressions.
4) is of the form "" where is a regular expression.
Regular expressions can be nested and will always have have two elements in the parentheses. ('' is an element, '' is not; basically, there will always be pairwise evaluation) Additionally, '' will always be the second element; '' is invalid.
The set of strings recognized by are as follows:
1) If is "", then the set of strings recognized .
2) If is "", then the set of strings recognized .
3) If is of the form "" then the set of strings recognized = all strings which can be obtained by a concatenation of strings and , where is recognized by and by .
4) If is of the form "" then the set of strings recognized = union of the set of strings recognized by and .
5) If is of the form "" then the the strings recognized are the empty string and the concatenation of an arbitrary number of copies of any string recognized by .
Task
Given a regular expression and an integer, , count how many strings of length are recognized by it.
Input Format
The first line contains the number of test cases . test cases follow.
Each test case contains a regular expression, , and an integer, .
Output Format
Print T lines, one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 10^9 + 7.
Solution :
Solution in C :
In C++ :
#include<stdio.h>
#include<vector>
#include<set>
#include<stdlib.h>
#include<map>
#include<string.h>
#include<iostream>
using namespace std ;
typedef pair<int,int> P ;
#define INF (int)1e9
#define MOD 1000000007
#define MAXN 102
int n,out[MAXN],g[MAXN][MAXN] ;
int ga[MAXN][MAXN],gb[MAXN][MAXN] ;
int g2[MAXN][MAXN] ;
set<int> aMask[MAXN],bMask[MAXN] ;
P construct(char regex[],int low,int high)
{
int start = n++ ;
int end = n++ ;
if(low == high)
{
out[start] = regex[low] - 'a' ;
return P(start,end) ;
}
int mid,ct = 0 ;
for(mid = low + 1;mid <= high;mid++)
{
if(regex[mid] == '(') ct++ ;
if(regex[mid] == ')') ct-- ;
if(ct == 0) break ;
}
P ret1 = construct(regex,low + 1,mid) ;
if(regex[mid + 1] == '|')
{
P ret2 = construct(regex,mid + 2,high - 1) ;
g[start][ret1.first] = g[start][ret2.first] = 1 ;
g[ret1.second][end] = g[ret2.second][end] = 1 ;
}
else if(regex[mid + 1] == '*')
{
g[start][ret1.first] = g[start][end] = 1 ;
g[ret1.second][end] = g[end][start] = 1 ;
}
else
{
P ret2 = construct(regex,mid + 1,high - 1) ;
g[start][ret1.first] = g[ret1.second][ret2.first] = 1 ;
g[ret2.second][end] = 1 ;
}
return P(start,end) ;
}
void mul(int a[MAXN][MAXN],int b[MAXN][MAXN],int c[MAXN][MAXN],int N)
{
int d[MAXN][MAXN] ;
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
d[i][j] = 0 ;
for(int k = 0;k < N;k++)
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
d[i][j] = (d[i][j] + 1LL * a[i][k] * b[k][j]) % MOD ;
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
c[i][j] = d[i][j] ;
}
void power(int a[MAXN][MAXN],int b[MAXN][MAXN],int k,int N)
{
if(k == 0)
{
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
b[i][j] = i == j ? 1 : 0 ;
return ;
}
int c[MAXN][MAXN] ;
power(a,c,k / 2,N) ;
mul(c,c,b,N) ;
if(k % 2 == 1)
{
mul(a,b,b,N) ;
}
}
int solve(char * regex,int L)
{
n = 0 ;
memset(g,0,sizeof g) ;
memset(out,255,sizeof out) ;
P nfa = construct(regex,0,strlen(regex) - 1) ;
for(int i = 0;i < n;i++) g[i][i] = 1 ;
for(int k = 0;k < n;k++)
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
if(g[i][k] && g[k][j])
g[i][j] = 1 ;
memset(ga,0,sizeof ga) ;
memset(gb,0,sizeof gb) ;
for(int i = 0;i < MAXN;i++) aMask[i].clear(),bMask[i].clear() ;
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
{
bool va = false,vb = false ;
for(int k = 0;k + 1 < n;k++)
{
if(g[i][k] && out[k] != -1 && g[k + 1][j])
{
if(out[k] == 0) va = true ;
else vb = true ;
}
}
if(va) ga[i][j] = true ;
if(vb) gb[i][j] = true ;
if(ga[i][j]) aMask[i].insert(j) ;
if(gb[i][j]) bMask[i].insert(j) ;
}
memset(g2,0,sizeof g2) ;
int id = 0 ;
set<int> orig[MAXN],q[MAXN] ;
int sz = 0 ;
map<set<int>,int> mp ;
set<int> start ;
start.insert(nfa.first) ;
q[sz++] = start ;
mp[start] = id++ ;
orig[id - 1] = start ;
for(int i = 0;i < sz;i++)
{
set<int> k = q[i] ;
int kk = mp[k] ;
set<int> a,b ;
for(int j = 0;j < n;j++)
if(k.find(j) != k.end())
{
for(set<int> :: iterator it = aMask[j].begin();it != aMask[j].end();++it) a.insert(*it) ;
for(set<int> :: iterator it = bMask[j].begin();it != bMask[j].end();++it) b.insert(*it) ;
}
if(!mp.count(a))
{
q[sz++] = a ;
mp[a] = id++ ;
orig[id - 1] = a ;
}
g2[kk][mp[a]]++ ;
if(!mp.count(b))
{
q[sz++] = b ;
mp[b] = id++ ;
orig[id - 1] = b ;
}
g2[kk][mp[b]]++ ;
}
// cout << "nodes: " << n << ", " << id << endl ;
int g3[MAXN][MAXN] ;
power(g2,g3,L,id) ;
int ret = 0 ;
for(int i = 0;i < id;i++)
if(orig[i].find(nfa.second) != orig[i].end())
ret = (ret + g3[mp[start]][i]) % MOD ;
return ret ;
}
bool vis[MAXN][MAXN] ;
int _L ;
int cur[MAXN] ;
void dfs(int k,int p)
{
if(vis[k][p]) return ;
vis[k][p] = true ;
for(int i = 0;i < n;i++)
if(g[k][i])
dfs(i,p) ;
if(out[k] != -1 && p < _L && cur[p] == out[k]) dfs(k + 1,p + 1) ;
}
int check()
{
memset(vis,false,sizeof vis) ;
dfs(0,0) ;
return vis[1][_L] ? 1 : 0 ;
}
int generate(int k)
{
if(k == _L) return check() ;
cur[k] = 0 ;
int ret = generate(k + 1) ;
cur[k] = 1 ;
ret += generate(k + 1) ;
return ret ;
}
int solve2(char * regex,int L)
{
_L = L ;
n = 0 ;
memset(g,0,sizeof g) ;
memset(out,255,sizeof out) ;
P nfa = construct(regex,0,strlen(regex) - 1) ;
return generate(0) ;
}
string genRegex(int k)
{
if(k == 1)
{
string s ;
if(rand() % 2 == 0) s.push_back('a') ;
else s.push_back('b') ;
return s ;
}
string s ;
int x = rand() % 3 ;
if(x == 0)
{
s = genRegex(k - 1) ;
s = "(" + s + "*)" ;
}
else
{
int f = 1 + rand() % (k - 1) ;
int se = k - f ;
string s1 = genRegex(f) ;
string s2 = genRegex(se) ;
if(x == 1) s = "(" + s1 + s2 + ")" ;
else s = "(" + s1 + "|" + s2 + ")" ;
}
return s ;
}
void generate2()
{
char in[10] = "in .txt" ;
for(int test = 1;test < 10;test++)
{
in[2] = test + '0' ;
FILE * fout = fopen(in,"w") ;
int runs = 50 ;
fprintf(fout,"%d\n",runs) ;
for(int t = 0;t < runs;t++)
{
int k = 28 - rand() % 10 ;
string s = genRegex(k) ;
if(s.size() > 100) while(1) ;
int L = rand() % 1000000000 + 1 ;
fprintf(fout,"%s %d\n",s.c_str(),L) ;
}
}
}
void test()
{
for(int t = 0;t < 100;t++)
{
string s = genRegex(15) ;
cout << s << endl ;
int L = rand() % 12 + 5 ;
char reg[MAXN] = {} ;
for(int i = 0;i < s.size();i++) reg[i] = s[i] ;
int ret1 = solve(reg,L) ;
int ret2 = solve2(reg,L) ;
cout << ret1 << " " << ret2 << endl ;
if(ret1 != ret2)
{
cout << "Failed on: " << s << endl ;
while(1) ;
}
}
}
int pow2(int k)
{
if(k == 0) return 1 ;
int ret = pow2(k / 2) ;
ret = 1LL * ret * ret % MOD ;
if(k & 1) ret = 1LL * ret * 2 % MOD ;
return ret ;
}
int main()
{
// generate2() ; return 0 ;
// test() ; return 0 ;
int runs ;
scanf("%d",&runs) ;
for(int t = 1;t <= runs;t++)
{
int L ;
char regex[MAXN] ;
scanf("%s%d",regex,&L) ;
int ret = solve(regex,L) ;
// cout << "test: " << t << endl ;
// cout << ret << " " << pow2(L) << endl ; continue ;
/*
int ret2 = solve2(regex,L) ;
cout << ret << " " << ret2 << endl ;
if(ret != ret2)
{
cout << "Failed" << endl ;
while(1) ;
}
*/
printf("%d\n",ret) ;
}
return 0 ;
}
In Java :
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
public class Solution {
static int parseIndex = 0;
static final int MOD = 1000000007;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int cases = scan.nextInt();
for(int cs=0; cs<cases; cs++){
String regex = scan.next();
int length = scan.nextInt();
NFA nfa = parse(regex);
DFA dfa = new DFA(nfa);
long[][] graph = dfa.toAdjacencyMatrix();
graph = power(graph, length);
long words = 0;
for(int end : dfa.ends){
words += graph[dfa.start][end];
}
words %= MOD;
System.out.println(words);
}
}
static long[][] power(long[][] matrix, long power){
if(power == 1)
return matrix;
else if(power % 2 == 0)
return power(multiply(matrix, matrix), power/2);
else
return multiply(matrix, power(multiply(matrix, matrix), power/2));
}
static long[][] multiply(long[][] m1, long[][] m2){
long[][] res = new long[m1.length][m1.length];
for(int i=0; i<m1.length; i++){
for(int j=0; j<m1.length; j++){
long dotProd = 0;
for(int k=0; k<m1.length; k++){
dotProd += m1[i][k] * m2[k][j];
dotProd %= MOD;
}
res[i][j] = dotProd;
}
}
return res;
}
static NFA parse(String regex){
parseIndex = 0;
return new NFA(regex);
}
static class DFA{
int start;
HashSet<Integer> ends = new HashSet<Integer>();
List<DFANode> nodes = new ArrayList<DFANode>();
HashMap<DFANode, Integer> nodeMap = new HashMap<DFANode, Integer>();
public DFA(NFA nfa){
HashSet<DFANode> allNodes = new HashSet<DFANode>();
Queue<DFANode> wipNodes = new LinkedList<DFANode>();
DFANode startNode = new DFANode(nfa.start.findClosure());
startNode.startState = true;
allNodes.add(startNode);
wipNodes.offer(startNode);
while(!wipNodes.isEmpty()){
DFANode node = wipNodes.poll();
HashSet<NFANode> nextState = NFA.nextState(node.state, 'a');
if(!nextState.isEmpty()){
DFANode next = new DFANode(nextState);
node.letterA = next;
if(allNodes.add(next))
wipNodes.offer(next);
}
nextState = NFA.nextState(node.state, 'b');
if(!nextState.isEmpty()){
DFANode next = new DFANode(nextState);
node.letterB = next;
if(allNodes.add(next))
wipNodes.offer(next);
}
if(node.state.contains(nfa.end))
node.endState = true;
}
for(DFANode node : allNodes){
int index = nodes.size();
nodes.add(node);
nodeMap.put(node, index);
if(node.startState)
start = index;
else if(node.endState)
ends.add(index);
}
}
long[][] toAdjacencyMatrix(){
long[][] matrix = new long[nodes.size()][nodes.size()];
for(int i=0; i<nodes.size(); i++){
DFANode node = nodes.get(i);
if(node.letterA != null)
matrix[i][nodeMap.get(node.letterA)] = 1;
if(node.letterB != null)
matrix[i][nodeMap.get(node.letterB)] = 1;
}
return matrix;
}
}
static class NFA{
NFANode start, end;
public NFA(String regex){
start = new NFANode();
end = new NFANode();
end.endState = true;
if(regex.charAt(parseIndex) == 'a'){//direct 'a' transition
parseIndex++;
start.letterA.add(end);
} else if(regex.charAt(parseIndex) == 'b'){//direction 'b' transition
parseIndex++;
start.letterB.add(end);
} else{//opening bracket
parseIndex++;
NFA child = new NFA(regex);
if(regex.charAt(parseIndex) == '*'){//repeat
parseIndex++;
start.epsilon.add(child.start);
start.epsilon.add(end);
child.end.epsilon.add(end);
child.end.endState = false;
end.epsilon.add(child.start);
} else if(regex.charAt(parseIndex) == '|'){//or
parseIndex++;
NFA child2 = new NFA(regex);
start.epsilon.add(child.start);
start.epsilon.add(child2.start);
child.end.epsilon.add(end);
child2.end.epsilon.add(end);
child.end.endState = false;
child2.end.endState = false;
} else{//concat
NFA child2 = new NFA(regex);
start = child.start;
end = child2.end;
child.end.epsilon.add(child2.start);
child.end.endState = false;
}
parseIndex++;//skip closing bracket
}
}
static HashSet<NFANode> nextState(HashSet<NFANode> states, char transition){
HashSet<NFANode> reachableClosure = new HashSet<NFANode>();
for(NFANode node : states){
HashSet<NFANode> reachable = new HashSet<NFANode>();
switch(transition){
case 'a':
reachable.addAll(node.letterA);
break;
case 'b':
reachable.addAll(node.letterB);
break;
}
for(NFANode n : reachable)
reachableClosure.addAll(n.findClosure());
}
return reachableClosure;
}
}
static class NFANode{
HashSet<NFANode> letterA = new HashSet<NFANode>();
HashSet<NFANode> letterB = new HashSet<NFANode>();
HashSet<NFANode> epsilon = new HashSet<NFANode>();
boolean endState = false;
HashSet<NFANode> findClosure(){
HashSet<NFANode> closure = new HashSet<NFANode>();
Stack<NFANode> DFS = new Stack<NFANode>();
DFS.push(this);
while(!DFS.isEmpty()){
NFANode node = DFS.pop();
closure.add(node);
for(NFANode n : node.epsilon)
if(!closure.contains(n))
DFS.push(n);
}
return closure;
}
}
static class DFANode{
DFANode letterA;
DFANode letterB;
HashSet<NFANode> state = new HashSet<NFANode>();
boolean startState = false;
boolean endState = false;
public DFANode(HashSet<NFANode> state){
this.state = state;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((state == null) ? 0 : state.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
DFANode other = (DFANode) obj;
if (state == null) {
if (other.state != null)
return false;
} else if (!state.equals(other.state))
return false;
return true;
}
}
}
In Python3 :
from enum import Enum
from collections import namedtuple
Edge = namedtuple('Edge', 'dest char')
class Alphabet(Enum):
a = 'a'
b = 'b'
e = None
def empty_edge(dest):
return Edge(dest, Alphabet.e)
class CountStrings:
def __init__(self, regex_string):
RegexGraphNFA.node_count = 0
self.regex_string = regex_string
nfa_graph = self.translate_regex()
translate_graph = TranslateGraph(nfa_graph)
self.dfa_graph = translate_graph.translate()
def calculate(self, string_length):
return self.dfa_graph.count_paths(string_length)
def translate_regex(self, index=0):
result_set = ResultSet()
while index < len(self.regex_string):
if self.regex_string[index] == '(':
out_list, index = self.translate_regex(index + 1)
result_set.insert(out_list)
elif self.regex_string[index] == ')':
result = result_set.calculate_result()
return result, index
elif self.regex_string[index] == '|':
result_set.set_or()
else:
result_set.insert(self.regex_string[index])
index += 1
return result_set.calculate_result()
class ResultSet:
def __init__(self):
self.r1 = None
self.r2 = None
self.has_or = False
def set_or(self):
self.has_or = True
def calculate_result(self):
repeat = True if self.r2 == '*' else False
if self.r2 is None:
pass
elif repeat:
self.calculate_repeat()
elif self.has_or:
self.calculate_or()
else:
self.calculate_and()
return self.r1
def calculate_repeat(self):
self.r1.graph_repeat()
def calculate_or(self):
self.r1.graph_or(self.r2)
def calculate_and(self):
self.r1.graph_add(self.r2)
def insert(self, value):
if value != '*' and isinstance(value, str):
value = RegexGraphNFA.get_char_graph(Alphabet[value])
if self.r1 is None:
self.r1 = value
else:
self.r2 = value
class RegexGraphNFA:
node_count = 0
def __init__(self):
self.edges = None
self.head = None
self.tail = None
@staticmethod
def get_char_graph(value):
my_graph = RegexGraphNFA()
my_graph.insert_char(value)
return my_graph
@classmethod
def get_next_node_id(cls):
node_id = cls.node_count
cls.node_count += 1
return node_id
def insert_char(self, value):
self.head = self.get_next_node_id()
self.tail = self.get_next_node_id()
self.edges = {self.head: [Edge(self.tail, value)],
self.tail: []}
def graph_add(self, other):
join_node = self.get_next_node_id()
self.join(other)
self.edges[self.tail].append(empty_edge(join_node))
self.edges[join_node] = [empty_edge(other.head)]
self.tail = other.tail
def graph_repeat(self):
new_head = self.get_next_node_id()
new_tail = self.get_next_node_id()
self.edges[self.tail].extend([empty_edge(self.head), empty_edge(new_tail)])
self.edges[new_head] = [empty_edge(self.head), empty_edge(new_tail)]
self.edges[new_tail] = []
self.head = new_head
self.tail = new_tail
def graph_or(self, other):
new_head = self.get_next_node_id()
new_tail = self.get_next_node_id()
self.join(other)
self.edges[new_head] = [empty_edge(self.head), empty_edge(other.head)]
self.edges[self.tail].append(empty_edge(new_tail))
self.edges[other.tail].append(empty_edge(new_tail))
self.edges[new_tail] = []
self.head = new_head
self.tail = new_tail
def join(self, other):
for node, edge in other.edges.items():
if node in self.edges:
self.edges[node].extend(edge)
else:
self.edges[node] = edge
def get_dfa_char_node_set(self, origin, use_char):
node_set = set()
for my_node in origin:
for edges in self.edges[my_node]:
if edges.char == use_char:
node_set.add(edges.dest)
return self.get_dfa_zero_node_set(node_set)
def get_dfa_zero_node_set(self, origin):
node_set = set(origin)
processed = set()
while len(node_set.difference(processed)) > 0:
my_node = node_set.difference(processed).pop()
for edges in self.edges[my_node]:
if edges.char == Alphabet.e:
node_set.add(edges.dest)
processed.add(my_node)
return frozenset(node_set)
class TranslateGraph:
language = (Alphabet.a, Alphabet.b)
def __init__(self, nfa_graph: RegexGraphNFA):
self.node_count = 0
self.nfa_graph = nfa_graph
self.trans_to = {}
self.trans_from = {}
self.table = {}
def get_next_node_id(self):
node_id = self.node_count
self.node_count += 1
return node_id
def add_translate(self, nfa_ids):
if len(nfa_ids) == 0:
return None
if nfa_ids not in self.trans_from:
dfa_id = self.get_next_node_id()
self.trans_to[dfa_id] = nfa_ids
self.trans_from[nfa_ids] = dfa_id
self.table[dfa_id] = dict(zip(self.language, [None] * len(self.language)))
return self.trans_from[nfa_ids]
def translate(self):
self.create_translate_table()
return self.build_dfa()
def build_dfa(self):
head = 0
valid_ends = set()
adjacency = {}
for node, edges in self.table.items():
adjacency[node] = []
if self.nfa_graph.tail in self.trans_to[node]:
valid_ends.add(node)
for my_char, node_dest in edges.items():
if node_dest is not None:
adjacency[node].append(Edge(node_dest, my_char))
return RegexGraphDFA(head, valid_ends, adjacency)
def create_translate_table(self):
nfa_ids = self.nfa_graph.get_dfa_zero_node_set({self.nfa_graph.head})
self.add_translate(nfa_ids)
processed = set()
while len(set(self.table).difference(processed)) > 0:
my_node = set(self.table).difference(processed).pop()
for char in self.language:
next_nodes = self.nfa_graph.get_dfa_char_node_set(self.trans_to[my_node], char)
dfa_id = self.add_translate(next_nodes)
self.table[my_node][char] = dfa_id
processed.add(my_node)
class RegexGraphDFA:
def __init__(self, head, valid_ends, edges):
self.edges = edges
self.head = head
self.valid_ends = valid_ends
self.edge_matrix = Matrix.get_from_edges(len(self.edges), self.edges)
def count_paths(self, length):
modulo = 1000000007
edge_walk = self.edge_matrix.pow(length, modulo)
count = 0
for end_node in self.valid_ends:
count += edge_walk.matrix[self.head][end_node]
return count % modulo
class Matrix:
@staticmethod
def get_from_edges(dimension, adj_list):
my_matrix = Matrix.get_zeros(dimension)
my_matrix.add_edges(adj_list)
return my_matrix
@staticmethod
def get_zeros(dimension):
my_matrix = Matrix(dimension)
my_matrix.pad_zeros()
return my_matrix
def copy(self):
my_matrix = Matrix(self.dimension)
my_matrix.matrix = []
for i in range(self.dimension):
my_matrix.matrix.append([])
for j in range(self.dimension):
my_matrix.matrix[i].append(self.matrix[i][j])
return my_matrix
def __init__(self, dimension):
self.matrix = None
self.dimension = dimension
def __str__(self):
my_str = ''
for row in self.matrix:
my_str += str(row) + "\n"
return my_str
def pad_zeros(self):
self.matrix = []
for i in range(self.dimension):
self.matrix.append([])
for j in range(self.dimension):
self.matrix[i].append(0)
def add_edges(self, adj_list):
if adj_list is not None:
for from_node, edge_list in adj_list.items():
for to_node, my_char in edge_list:
self.matrix[from_node][to_node] = 1
def pow(self, pow_val, mod_val=None):
started = False
target = pow_val
current_pow = 1
current_val = 0
while pow_val > 0:
if current_pow == 1:
current_pow_matrix = self.copy()
else:
current_pow_matrix = current_pow_matrix.mat_square_mult(current_pow_matrix, mod_val)
if pow_val % (2 * current_pow):
current_val += current_pow
if started:
result = result.mat_square_mult(current_pow_matrix, mod_val)
else:
result = current_pow_matrix.copy()
started = True
# print(current_pow, current_val, target)
pow_val -= current_pow
current_pow *= 2
return result
def mat_square_mult(self, other, mod_val=None):
result = Matrix.get_zeros(self.dimension)
for i in range(self.dimension):
for j in range(self.dimension):
val = 0
for k in range(self.dimension):
val += self.matrix[i][k] * other.matrix[k][j]
if mod_val is not None:
val %= mod_val
result.matrix[i][j] = val
return result
def main():
cases = int(input().strip())
for i in range(cases):
in_line = input().strip().split()
my_class = CountStrings(in_line[0])
print(my_class.calculate(int(in_line[1])))
if __name__ == "__main__":
main()
View More Similar Problems
Cube Summation
You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries. UPDATE x y z W updates the value of block (x,y,z) to W. QUERY x1 y1 z1 x2 y2 z2 calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coor
View Solution →Direct Connections
Enter-View ( EV ) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the x -axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points. Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) do
View Solution →Subsequence Weighting
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =
View Solution →Kindergarten Adventures
Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti
View Solution →Mr. X and His Shots
A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M
View Solution →Jim and the Skyscrapers
Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently. Let us describe the problem in one dimensional space
View Solution →