Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Chef and Bracket-Pairs CodeChef Solution
Problem -Chef and Bracket-Pairs CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Chef and Bracket-Pairs CodeChef Solution in C++14
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
Tran The Bao
CTL - Da Lat
Practising for VOI23 gold medal
*/
const int M = 1e9 + 7;
const int N = 1e2 + 1;
int n, a[N], d[N][N];
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> n;
FOR(i, 1, n) cin >> a[i];
FOR(i, 1, n) d[i][i] = 1;
FOR(i, 2, n)
FOR(l, 1, n - i + 1) {
int r = l + i - 1;
d[l][r] = (d[l][r] + d[l + 1][r]) % M;
if (a[l] > 0) continue;
FOR(z, l + 1, r) {
if (-a[z] != a[l]) continue;
int f = (l + 1 > z - 1? 1 : d[l + 1][z - 1]);
int s = (z + 1 > r? 1 : d[z + 1][r]);
d[l][r] = (d[l][r] + 1LL * f * s % M) % M;
}
}
cout << d[1][n];
return 0;
}Chef and Bracket-Pairs CodeChef Solution in PYTH 3
n=int(input())
a=input().split()
len_arr=len(a)
arr=[]
dp=[]
mod=1000000007
for i in range(len_arr):
arr.append(int(a[i]))
for i in range(len_arr):
dp.append([0]*(len_arr))
for i in range(len_arr):
for j in range(len_arr):
if i==j:
continue;
if i==0 or j>i:
continue
dp[j][i]=dp[j][i-1]
if arr[i]>0:
for k in range(j,i,1):
if arr[k]<0 and arr[i]==-arr[k] and k!=j:
dp[j][i]=(((dp[j][i]+1+dp[k+1][i-1])%mod)+(((1+dp[k+1][i-1])%mod)*dp[j][k-1])%mod)%mod
elif arr[k]<0 and arr[i]==-arr[k] and k==j:
dp[j][i]=(((dp[j][i]+1%mod)+dp[k+1][i-1])%mod)
print(dp[0][n-1]+1) Chef and Bracket-Pairs CodeChef Solution in C
#include <stdio.h>
int main(void) {
int n,mod=1000000007;
scanf("%d",&n);
long long a[100],i,j,k,size;
for(i=0;i<n;i++)scanf("%lld",&a[i]);
long long dp[101][101]={{0}};
for(size=1;size<n;size++)//typical matrix chain/obst loops
{
for(i=0;i<(n-size);i++)
{
j=i+size;
//lets find valid sequences between [i,j] with range size=size
//lets not pairup the jth bracket (+x) with any brackets in the range [i,j-1]
//so all sequences between [i,j-1] will be included as it is
dp[i][j]=dp[i][j-1];
for(k=i;k<=j-1;k++)
{
if(a[k]<0 && a[k]+a[j]==0 && a[j]>0)//if (-x) type found
{
//pair this (-x,x)ie(k,j) bracket with all sequences inside them ie [k+1,j-1]
//1 is added to account for the null set
//pair this (-x,x)ie(k,j) bracket with all sequences outside them ie [i,k-1]
//1 is added to account for the null set
if(k-1<0)
dp[i][j] = (dp[i][j]%mod + (dp[k+1][j-1] + 1)%mod)%mod;
else
dp[i][j]=((dp[i][j]%mod)+((dp[k+1][j-1]+1)*1LL*(dp[i][k-1]+1))%mod)%mod;
}
}
}
}
printf("%lld\n",(dp[0][n-1]+1)%mod);
return 0;
} Chef and Bracket-Pairs CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
class Main
{
static class Patient implements Comparable<Patient> {
int pos;
int illness;
Patient(int pos,int illness) {
this.pos=pos;
this.illness=illness;
}
@Override
public int compareTo(Patient p) {
return p.illness-this.illness;
}
}
/*
class Pair
{
int f,s;
Pair( int f, int s)
{
this.f=f;
this.s=s;
}
}*/
static class Pair {
char prefix;
int suffixId;
Pair(char prefix, int suffixId) {
this.prefix = prefix;
this.suffixId = suffixId;
}
@Override
public int hashCode() {
final int prime = 199;
int hash = 0;
hash = prime * prefix + hash;
hash = prime * suffixId + hash;
return hash;
}
@Override
public boolean equals(Object obj) {
if(obj instanceof Pair) {
Pair p2 = (Pair) obj;
return this.prefix == p2.prefix && this.suffixId == p2.suffixId;
}
return false;
}
}
/*static class pair implements Comparable<pair>
{
long x;
int y;
pair(long x,int y)
{
this.x=x;
this.y=y;
}
public int compareTo(pair o)
{
return (int)(x-o.x);
}
}
static class Pair
{
long x,y;
Pair(long x, long y)
{
this.x = x;
this.y = y;
}
}
static class PairComparator implements Comparator<Pair>
{
public long compare(Pair a, Pair b)
{
//if(a.x==b.x)
return a.y-b.y;
// return a.x-b.x;
}
}
static class Point {
public double x, y;
private static final int MAX = (int) 1e6 + 1;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
public int hashCode() {
return (int)x * MAX + (int)y;
}
public boolean equals(Object ob) {
if(ob instanceof Point) {
Point other = (Point) ob;
return other.x == x && other.y == y;
}
return false;
}
public String toString() {
return "(" + x + ", " + y + ")";
}
}
/* static int days4=0;
static int all;
static long phi[]=new long[1000001];
static long ans[]=new long[1000001];
//static int tree[],sum[];
//public static long mod = 1000000007; public static long [][] tempMatrix;
public static long max = (long) Math.pow(10, 9) + 7;
static StringBuilder res = new StringBuilder();
//static Node tree[];
//static int a[];
static long mod = 998244353;
public static int rootColor=0;
static int MX = (1<<18);
static boolean primes[]=new boolean[10000001];
static double pi = 3.1415926535;
private static final int MAXN = 5000;
private static final int MOD = 1000_000_007;
// private static Modular modular_nCr = new Modular(MOD);
// private static Modular modular = new Modular(MOD);
private static final long[][] nCr = new long[MAXN+5][MAXN+5];
// static int[] maxval = new int[1000000];
// static int[] minval = new int[1000000];
// private static long bruteAns = 1;
// static double eps = 1e-7;
static {
nCr[0][0]=1;
for(int i=0;i<=MAXN;i++)
nCr[i][0]=1;
for(int i=1;i<=MAXN;i++){
for(int j=1;j<=i;j++){
nCr[i][j]=(nCr[i-1][j-1]+nCr[i-1][j])%MOD;
}
}
}
/*
static { nCr[0][0] = 1;
for (int i = 1; i < MAXN; i++) {
nCr[i][0] = 1;
for (int j = 1; j <= i; j++) {
nCr[i][j] = modular_nCr.add(nCr[i - 1][j - 1], nCr[i - 1][j]);
} }
}
*/
static int final_sum=0;
static long mod=1000000007;
static ArrayList<Integer> graph[];
static boolean vis[];
static int seive[]=new int[1000001];
static int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
static int[] calcPower() {
int[] arr = new int[26];
for (int i = 0; i < 26; i++) {
arr[i] = (int) Math.pow(2, i);
}
return arr;
}
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
// FastReader in = new FastReader(System.in);
StringBuilder sb = new StringBuilder();
FastScanner in=new FastScanner();
// Scanner sc = new Scanner(System.in);
PrintWriter out=new PrintWriter(System.out);
// HashMap<Integer, Integer> h = new HashMap<Integer, Integer>();
// TreeMap<Integer, Integer> h1 = new TreeMap<Integer, Integer>();
// HashMap<Integer, Integer> h2 = new HashMap<Integer, Integer>();
// HashSet<Point> s = new HashSet<Point>();
// HashSet<Double> s2 = new HashSet<Double>();
// HashSet<Double> s3 = new HashSet<Double>();
// HashSet<Character> h2 = new HashSet<Character>();
//long t= in.nextLong();
// long t = in.nextLong();
//DecimalFormat df = new DecimalFormat("#,###,##0.000000");
/* boolean prime[]=new boolean[10000000];
int p[]=new int[10000000];
int k=1;
Arrays.fill(prime, true);
prime[0]=false;
prime[1]=false;for(int i=2;i<10000000;i++)
{
if(!prime[i])
{
p[i]=p[i-1];
continue;
}
p[i]=k; k++;
for(long j=(long)i*i;j<10000000;j+=i)
prime[(int)j]=false;
}
// BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
/* int pri[]=new int[1000005];
int p=2;
List<Integer> list=new ArrayList<>();
while(p*p <=1000005)
{
if(pri[p]==0)
{
for(int i=p*2;i<=1000004;i=i+p)
{
pri[i]=1;
}
list.add(p);
}
p++;
}*/
//System.out.println(list);
int[] power = calcPower();
int n = in.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++)
{
arr[i] = in.nextInt();
}
long ans=0;
long dp[][]=new long[n][n];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(j==(i+j))
{
dp[j][j]=0;
}
else
{
if(i+j < n)
{
int x=i+j;
dp[j][x]=dp[j][x-1];
for(int k=j;k<x;k++)
{
if(arr[x]>0 && arr[k]==-arr[x])
{
if(k==j)
dp[j][x]=(dp[j][x]+1+dp[j+1][x-1])%1000000007;
else
{
dp[j][x]=(dp[j][x]+((1+dp[k+1][x-1])*(1+dp[j][k-1])))%1000000007;
}
}
}
}
}
}
}
System.out.println(dp[0][n-1]+1);
}
/*
long mod = 1000000007;
//StringBuilder sb = new StringBuilder();
// DecimalFormat df = new DecimalFormat("######0.00000000000");
// int[] dp = new int[101];
String[] S1;
double[][] Comb=new double[1000+1][1000+1];
for(int i=0;i<1001;i++)
{
Comb[i][0]=Comb[i][i]=1.0;
for(int j=1;j<i;j++)
Comb[i][j]=Comb[i-1][j]+Comb[i-1][j-1];
}
*/
public static long gcd(long a,long b,long n){
if(a==b){
return (power(a,n,mod)+power(b,n,mod))%mod;
}
long res=1l;
long num=a-b;
for(long i=1;i*i<=num;i++){
if(num%i==0){
long temp= (power(a,n,i)+ power(b,n,i))%i;
if(temp==0){
res=Math.max(res,i);
}
temp= (power(a,n,num/i) + power(b,n,num/i))%(num/i);
if(temp==0){
res=Math.max(res,num/i);
}
}
}
return res%mod;
}
public static long power(long a,long n,long d){
long res=1l;
while(n>0){
if(n%2==1){
res =((res%d)*(a%d))%d;
n--;
}else{
a=((a%d)*(a%d))%d;
n=n/2;
}
}
return res%mod;
}
/* static long power(long x,long y) {
long res=1;
x%=m;
while(y>0) {
if(y%2!=0)
res=(res*x)%m;
y=y>>1;
x=(x*x)%m;
}
return res;
}
*/
static long gcd(long a, long b)
{
if(b==0)
return a;
else
return gcd(b, a%b);
}
static long nextPower_2 ( long x, long y )
{
long count = 0 ;
while ( y < x )
{count ++ ;
y = y << 1 ;
}
return count ;
}
/*
static long power(long a, long b, long p)
{ long x = 1, y = a;
while (b > 0) {
if (b % 2 == 1) {
x = (x * y);
if (x >= p) x %= p;
}
y = (y * y); if (y >= p) y %= p;
b /= 2;}
return x;
}*/
public static class Modular {
private int MOD;
Modular(int MOD) {
this.MOD = MOD;
}
public long add(long a, long b) {
return (a + b) % MOD;
}
public long sub(long a, long b) {
return (a - b + MOD) % MOD;
}
public long mul(long a, long b) {
return (a * b) % MOD;
}
public long div(long a, long b) {
return mul(a, inverseEuler(b));
} public long power(long a, long b) {
long x = 1, y = a;
while (b > 0) {
if (b % 2 == 1) {
x = (x * y);if (x >= MOD) x %= MOD;
}
y = (y * y);
if (y >= MOD) y %= MOD;
b /= 2;}
return x;
}
public long inverseEuler(long n) {
return power(n, MOD - 2);
}
}
static class FastReader {
byte[] buf = new byte[2048];
int index, total;
InputStream in;FastReader(InputStream is) {
in = is;
} int scan() throws IOException {
if (index >= total) {
index = 0;
total = in.read(buf);
if (total <= 0) { return -1;
}
}
return buf[index++];
}
String next() throws IOException {
int c;
for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder(); for (; c > 32; c = scan()) {
sb.append((char) c);}
return sb.toString();
}String nextLine() throws IOException {
int c;for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder();
for (; c != 10 && c != 13; c = scan()) {
sb.append((char) c);
} return sb.toString();
}char nextChar() throws IOException {
int c;
for (c = scan(); c <= 32; c = scan()) ;
return (char) c;
} int nextInt() throws IOException {
int c, val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan(); }
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}long nextLong() throws IOException {
int c;long val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan();
}
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}
}
static class FastScanner{
BufferedReader br;
StringTokenizer st;
public FastScanner(){br=new BufferedReader(new InputStreamReader(System.in));}
String nextToken(){
while(st==null||!st.hasMoreElements())
try{st=new StringTokenizer(br.readLine());}catch(Exception e){}
return st.nextToken();
}
int nextInt(){return Integer.parseInt(nextToken());}
long nextLong(){return Long.parseLong(nextToken());}
double nextDouble(){return Double.parseDouble(nextToken());}
}
}Chef and Bracket-Pairs CodeChef Solution in PYPY 3
from functools import lru_cache
mod = 10 ** 9 + 7
@lru_cache(None)
def dp(l, r):
if l >= r:
return 0
ans = 0
for i in range(l, r+1):
if s[i] > 0:
for j in range(l, i):
if s[j] == -s[i]:
ans += (1 + dp(j+1, i-1)) * (1 + dp(l,j-1))
ans %= mod
return ans
n = int(input())
s = [int(x) for x in input().split()]
print ((dp(0, n-1)+1) % mod)
#voi moi dau ngoac dong tim xem co bao nhieu brack co end la cai do
#goi vi tri cai ngoac mo la i
#x = dp[l, i-1]
#y = dp[i+1, j-1]
#ans += (x+1) * (y+1)
#tai sao cong 1, vi chung ta dc quyen chon 0 brack from x va yChef and Bracket-Pairs CodeChef Solution in PYTH
# pylint: disable=missing-docstring, invalid-name, line-too-long
import sys, copy
inp, outp = sys.stdin, sys.stdout
def calcInner(x, y, brackets, DP):
inner, total = [], 1
for b in brackets:
if b[0] > x and b[1] < y:
inner.append((b[0], b[1]))
inner.sort(key=lambda x: x[1])
for i in range(len(inner)):
b = inner[i]
temp = DP[b]
for j in range(i):
if inner[j][1] < b[0]:
keyOther = (inner[j][0], inner[j][1])
temp = (temp + DP[b] * DP[keyOther]) % MOD
# print 'inner', b, temp
DP[b] = temp % MOD
total += temp
return total % MOD
def solve(A, N):
brackets, DP = [], {}
for i in range(N - 1):
if A[i] < 0:
for j in range(i + 1, N):
if A[j] == -A[i]:
brackets.append((i, j))
brackets.sort(key=lambda x: x[1] - x[0])
for bracket in brackets:
DP[bracket] = calcInner(bracket[0], bracket[1], brackets, copy.copy(DP))
# print bracket, DP[bracket]
return calcInner(-1, N + 1, brackets, copy.copy(DP))
N, MOD = int(inp.readline().strip()), int(1e+9 + 7)
A = [int(s) for s in inp.readline().split()]
print solve(A, N)Chef and Bracket-Pairs CodeChef Solution in C#
using System;
using System.Linq;
public class Test
{
public static void Main()
{
// your code goes here
int n = int.Parse(Console.ReadLine());
num = Console.ReadLine().Trim().Split().Select(x => int.Parse(x)).ToArray();
dp = new long[n+1,n+1];
for(int i = 0 ; i <= n ; i++)
for(int j = 0 ; j <= n ; j++){
dp[i,j] = -1;
}
Console.WriteLine(recur(0,n-1));
}
static int[] num;
static long recur(int l , int r){
if(dp[l,r] != -1)
return dp[l,r];
long ret = 1;
for(int i = l ; i <= r ; i++){
if(num[i] < 0){
for(int j = i + 1 ; j <= r ; j++){
if(num[j] == -num[i]){
long val = 1;
if(i + 1 <= r && j - 1 >= l)
val = val * recur(i+1,j-1);
if(j+1 <= r)
val = val * recur(j+1,r);
ret = (ret + val ) % 1000000007;
}
}
}
}
dp[l,r] = ret;
return ret;
}
static long[,] dp;
}Chef and Bracket-Pairs CodeChef Solution Review:
In our experience, we suggest you solve this Chef and Bracket-Pairs CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Chef and Bracket-Pairs CodeChef Solution.
Conclusion:
I hope this Chef and Bracket-Pairs CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
