Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Remove Balance CodeChef Solution
Problem -Remove Balance 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.
<<Previous CodeChef Problem Next Codechef Problem>>
Remove Balance CodeChef Solution in C++17
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mod 998244353
#define inf 1e18
#define fo(i,n) for(i=0;i<n;i++)
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli t,n,i,m,k,j,p;
cin>>t;
while(t--)
{
string s;
stack<lli> st1,st2;
vector<lli> a;
lli ans=0;
cin>>s;
fo(i,s.size())
{
if(s[i]=='(')
st1.push(i);
else if(!st1.empty())
st1.pop();
else
st2.push(i);
}
while(!st1.empty())
{
a.push_back(st1.top());
st1.pop();
}
while(!st2.empty())
{
a.push_back(st2.top());
st2.pop();
}
a.push_back(-1);
a.push_back(s.size());
sort(a.begin(),a.end());
fo(i,a.size()-1)
{
if(a[i]+1!=a[i+1])
ans++;
}
cout<<a.size()-2<<" "<<ans;
cout<<"\n";
}
return 0;
}Remove Balance CodeChef Solution in C++14
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define count_1(n) __builtin_popcountll(n)
#define pb push_back
#define fr(a,b) for(int i =a ;i <b ;i++)
#define fr1(a,b) for(int j =a ;j <b ;j++)
#define all(x) (x).begin(), (x).end()
#define vint vector<int>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 1e9 + 7 ;
#define inf (1LL<<62)
template <typename T>istream &operator>>(istream &istream, vector<T> &vec){for (auto &a : vec)cin >> a;return istream;}
template <typename T>ostream &operator<<(ostream &ostream, const vector<T> &vec){for (auto &a : vec)cout << a << " ";return ostream;}
long long binpow(long long a, long long b, long long m) {
a %= m;long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % m; a = a * a % m; b >>= 1;
} return res;
}
//==========================================-_-=============================================//
int main() {
FAST
ll t,n,m,x,j,k,q ;
t=1;
cin >>t ;
while(t--){
string s;
cin >>s ;
n = s.size() ;
stack<int> open , close ;
fr(0,n){
if(s[i]=='(')open.push(i) ;
else{
if(!open.empty())open.pop() ;
else close.push(i) ;
}
}
vint v ;
while(!open.empty()){
v.pb(open.top()) ;
open.pop() ;
}
while(!close.empty()){
v.pb(close.top()) ;
close.pop() ;
}
sort(all(v)) ;
//cout << v << endl;
cout << v.size() <<" " ;
if(v.size()==0)cout<<"1" <<endl;
else if(v.size()==n)cout<<"0" <<endl;
else if(v.size()==1){
if(v[0]==0|| v[0]==n-1)cout<<"1" <<endl;
else cout << "2" <<endl;
}else{
int ans(0) ;
if(v[0] != 0)ans++ ;
if(v[v.size()-1] != n-1)ans++ ;
fr(1,v.size())if(v[i] != v[i-1]+1)ans++ ;
cout << ans <<endl;
}
}
return 0;
}Remove Balance CodeChef Solution in PYTH 3
t = int(input())
for i in range(t):
s = input()
par = {"(":")"}
stack = []
i = 0
res = []
while i < len(s):
flag = 0
if stack and stack[-1][0] != ")" and par[stack[-1][0]] == s[i]:
val , index = stack.pop()
res += [index,i]
flag = 1
if not flag:
stack.append((s[i],i))
i += 1
res.sort()
diff = []
for i in range(len(res)-1):
diff.append(abs(res[i]-res[i+1]))
#print(diff)
if diff:
count = 1
else:
count = 0
for i in range(len(diff)-1):
if diff[i] == diff[i+1] == 1:
pass
elif diff[i] != 1 and diff[i+1] == 1:
count += 1
print(len(stack),count)
Remove Balance CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static class FastScanner {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer("");
String next() {
while (!st.hasMoreTokens())
try {
st=new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
return st.nextToken();
}
int ni() {
return Integer.parseInt(next());
}
int[] iArray0(int n) {
int[] a=new int[n];
for (int i=0; i<n; i++) a[i]=ni();
return a;
}
int[] iArr1(int n){
int[] ar = new int[n + 1];
for(int i = 1; i <= n; i++) ar[i] = ni();
return ar;
}
long[] lArray0(int n){
long[] ar = new long[n];
for(int i = 0; i < n; i++) ar[i] = nl();
return ar;
}
long[] lArr1(int n){
long[] ar = new long[n + 1];
for(int i = 1; i <= n; i++) ar[i] = nl();
return ar;
}
long nl() {
return Long.parseLong(next());
}
}
static long mod=1000000007;
public static void main (String[] args) throws java.lang.Exception
{
FastScanner sc = new FastScanner();
PrintWriter out=new PrintWriter(System.out);
int tc = sc.ni();
for(int t=0; t<tc; t++){
// write code
String s= sc.next();
Stack<Integer>st= new Stack<>();
Stack<Character>st2= new Stack<>();
for(int i=0; i<s.length(); i++){
if(s.charAt(i)=='('){
st2.push('(');
st.push(i);
}
else{
if(st.isEmpty()){
st2.push(')');
st.push(i);
}
else{
if(st2.peek()=='('){
st2.pop();
st.pop();
}
else{
st2.push(')');
st.push(i);
}
}
}
}
int cnt=0;
int l=st2.size();
int prev= s.length();
while(!st.isEmpty()){
if(st.peek()!=prev-1){
cnt++;
}
prev= st.pop();
}
if(prev!=0){
cnt++;
}
out.println(l+" "+cnt);
}
out.close();
}
// helper functions
//DisjointSet
static class DisjointSet{
int[] parent, rank;
DisjointSet(int n){
this.parent = new int[n];
this.rank = new int[n];
for(int i = 0; i < n; i++) this.parent[i] = i;
}
int find(int x){
if(x != parent[x]) parent[x] = find(parent[x]);
return parent[x];
}
boolean equiv(int x, int y){
return find(x) == find(y);
}
void union(int x, int y){
int xRoot = find(x), yRoot = find(y);
if(xRoot == yRoot) return;
if(rank[xRoot] < rank[yRoot]){
parent[xRoot] = yRoot;
}else if(rank[yRoot] < rank[xRoot]){
parent[yRoot] = xRoot;
}else{
parent[xRoot] = yRoot;
rank[yRoot]++;
}
}
}
public static int lower_bound(ArrayList<Integer> ar,int lo , int hi , int k)
{
int s=lo;
int e=hi;
while (s !=e)
{
int mid = s+e>>1;
if (ar.get(mid) <k)
{
s=mid+1;
}
else
{
e=mid;
}
}
if(s==ar.size())
{
return -1;
}
return s;
}
public static int upper_bound(ArrayList<Integer> ar,int lo , int hi, int k)
{
int s=lo;
int e=hi;
while (s !=e)
{
int mid = s+e>>1;
if (ar.get(mid) <=k)
{
s=mid+1;
}
else
{
e=mid;
}
}
if(s==ar.size())
{
return -1;
}
return s;
}
static String decimalToFraction(double number)
{
double intVal = Math.floor(number);
double fVal = number - intVal;
final long pVal = 1000000000;
long gcdVal = gcd(Math.round(
fVal * pVal), pVal);
long num = Math.round(fVal * pVal) / gcdVal;
long deno = pVal / gcdVal;
String ans= num+"/"+deno;
return ans;
}
static boolean isPrime(long N)
{
if (N<=1) return false;
if (N<=3) return true;
if (N%2 == 0 || N%3 == 0) return false;
for (int i=5; i*i<=N; i=i+6)
if (N%i == 0 || N%(i+2) == 0)
return false;
return true;
}
static long pow(long a,long b)
{
long mod=1000000007;
long pow=1;
long x=a;
while(b!=0)
{
if((b&1)!=0)pow=(pow*x)%mod;
x=(x*x)%mod;
b/=2;
}
return pow;
}
static long toggleBits(long x)//one's complement || Toggle bits
{
int n=(int)(Math.floor(Math.log(x)/Math.log(2)))+1;
return ((1<<n)-1)^x;
}
static int countBits(long a)
{
return (int)(Math.log(a)/Math.log(2)+1);
}
static long fact(long N)
{
long n=2;
if(N<=1)return 1;
else
{
for(int i=3; i<=N; i++)n=(n*i)%mod;
}
return n;
}
private static boolean isInteger(String s) {
try {
Integer.parseInt(s);
} catch (NumberFormatException e) {
return false;
} catch (NullPointerException e) {
return false;
}
return true;
}
private static long gcd(long a, long b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
private static long lcm(long a, long b) {
return (a / gcd(a, b)) * b;
}
private static boolean isPalindrome(String str) {
int i = 0, j = str.length() - 1;
while (i < j)
if (str.charAt(i++) != str.charAt(j--))
return false;
return true;
}
private static String reverseString(String str) {
StringBuilder sb = new StringBuilder(str);
return sb.reverse().toString();
}
}Remove Balance CodeChef Solution in PYPY 3
for _ in range(int(input())):
S = input()
N = len(S)
T = [False] * N
L = N
stack = []
for i in range(N):
if S[i] == "(":
stack.append(i)
else:
if stack:
j = stack.pop()
T[i] = True
T[j] = True
L -= 2
V = 0
for i in range(N):
d = T[i - 1] if i != 0 else False
if not d and T[i]:
V += 1
print(L, V)Remove Balance CodeChef Solution in C#
using System;
using System.Collections.Generic;
class Test
{
public class Pair
{
public char c;
public int index;
public Pair(char c, int i)
{
this.c = c;
this.index = i;
}
}
// dfs
public static void dfs(int[] a, int n, int k, int index, int[] b)
{
if (index == k)
{
// Add(b);
return;
}
for (int i = 0; i < n; i++)
{
b[index] = a[i];
dfs(a, n, k, index + 1, b);
}
}
public static void Main(string[] args)
{
int t = Convert.ToInt32(Console.ReadLine());
char open = '(';
char close = ')';
while (t-- > 0)
{
String str = Console.ReadLine();
Stack<Pair> stack = new Stack<Pair>();
for (int i = 0; i < str.Length; i++)
{
if (stack.Count == 0 || stack.Peek().c == close)
stack.Push(new Pair(str[i], i));
else if (str[i] == close)
stack.Pop();
else
stack.Push(new Pair(open, i));
}
int result = 0;
int size = stack.Count;
if (size == 0)
{
Console.WriteLine("0" + " 1");
continue;
}
int[] arr = new int[size];
for (int i = size - 1; i >= 0; i--)
arr[i] = stack.Pop().index;
for (int i = 0; i < size; i++)
{
if (i == 0 || i == size - 1)
{
if (i == 0 && arr[i] != 0)
result++;
if (i == size - 1 && arr[i] != str.Length - 1)
result++;
}
if (i > 0 && (arr[i] - arr[i - 1] > 1))
result++;
}
Console.WriteLine(size + " " + result);
}
}
// permutation
public static void permutation(int[] a, int n, int k, int index, int[] b)
{
if (index == k)
{
// Add(b);
return;
}
for (int i = 0; i < n; i++)
{
b[index] = a[i];
permutation(a, n, k, index + 1, b);
}
}
public int CountUnguarded(int m, int n, int[][] guards, int[][] walls)
{
int[,] grid = new int[m, n];
foreach (int[] w in walls)
{
grid[w[0], w[1]] = -1;
}
foreach (int[] g in guards)
{
grid[g[0], g[1]] = -1;
}
HashSet<string> vals = new HashSet<string>();
int k1 = 0;
foreach (int[] g in guards)
{
grid[g[0], g[1]] = 2;
int m1 = g[0] - 1;
while (m1 >= 0)
{
if (grid[m1, g[1]] == -1 || grid[m1, g[1]] == 2)
break;
String s1 = m1 + " " + g[1];
if (!vals.Contains(s1))
{
k1++;
vals.Add(s1);
}
grid[m1, g[1]] = 1;
m1--;
}
m1 = g[0] + 1;
while (m1 < m)
{
if (grid[m1, g[1]] == -1 || grid[m1, g[1]] == 2)
break;
string s1 = m1 + " " + g[1];
if (!vals.Contains(s1))
{
k1++;
vals.Add(s1);
}
grid[m1, g[1]] = 1;
m1++;
}
m1 = g[1] - 1;
while (m1 >= 0)
{
if (grid[g[0], m1] == -1 || grid[g[0], m1] == 2)
break;
string s1 = g[0] + " " + m1;
if (!vals.Contains(s1))
{
k1++;
vals.Add(s1);
}
grid[g[0], m1] = 1;
m1--;
}
m1 = g[1] + 1;
while (m1 < n)
{
if (grid[g[0], m1] == -1 || grid[g[0], m1] == 2)
break;
string s1 = g[0] + " " + m1;
if (!vals.Contains(s1))
{
k1++;
vals.Add(s1);
}
grid[g[0], m1] = 1;
m1++;
}
}
int ans = m * n - guards.Length - walls.Length - k1;
if (ans < 0)
ans = 0;
return ans;
}
// solve
public static void solve(int[] a, int n, int k, int index, int[] b)
{
if (index == k)
{
// Add(b);
return;
}
for (int i = 0; i < n; i++)
{
b[index] = a[i];
solve(a, n, k, index + 1, b);
}
}
//
}Remove Balance CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
tc := readNum(reader)
var buf bytes.Buffer
for tc > 0 {
tc--
S := readString(reader)
a, b := solve(len(S), S)
buf.WriteString(fmt.Sprintf("%d %d\n", a, b))
}
fmt.Print(buf.String())
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readString(reader *bufio.Reader) string {
s, _ := reader.ReadString('\n')
for i := 0; i < len(s); i++ {
if s[i] == '\n' {
return s[:i]
}
}
return s
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
func solve(n int, S string) (int, int) {
stack := make([]int, n)
var p int
for i := 0; i < n; i++ {
if S[i] == ')' && p > 0 && S[stack[p-1]] == '(' {
p--
} else {
stack[p] = i
p++
}
}
rem := p
var ans int
if p == 0 {
ans++
}
if p > 0 && stack[0] != 0 {
ans++
}
if p > 0 && stack[p-1] != n-1 {
ans++
}
for i := 0; i+1 < p; i++ {
if stack[i]+1 != stack[i+1] {
ans++
}
}
return rem, ans
}Remove Balance CodeChef Solution Review:
In our experience, we suggest you solve this Remove Balance 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 Remove Balance CodeChef Solution.
Conclusion:
I hope this Remove Balance 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!
