Skip to main content

Kicstart 2017 Practice Problem C. Sherlock and Parentheses

Abridged problem statement

Given the number of left and right parenthesis, output the maximum number of balanced substrings in all possible subsets of the string.

Constraints

1 ≤ T ≤ 100.

Small dataset
0 ≤ L ≤ 20.
0 ≤ R ≤ 20.
1 ≤ L + R ≤ 20.

Large dataset
0 ≤ L ≤ 105.
0 ≤ R ≤ 105.
1 ≤ L + R ≤ 105.

Approach  

Let us try to obtain the answer manually for certain cases.
Case 1:
L = 1, R = 1
We can form only ( ) string which conatains 1 balanced substring.
Case 2:
L = 2, R = 2
We can form ( ) ( ) which contains 3 balanced substrings, i.e. index 1 to 2, index 3 to 4, index 1 to 4.
Case 3:
L = 3, R = 3
We can form ( ) ( ) ( ) which contains 6 balanced substrings, i.e. with indices 1 to 2,  3 to 4,  5 to 6, 1 to 4, 3 to 6, 1 to 6.
Case 4:
L = 4, R = 4
We can obtain 10 balanced substrings from ( ) ( ) ( ) ( ).
Hence we obtain the series 1, 3, 6, 10, ...
This forms the set of triangular numbers: where
a(n) = binomial(n+1,2) = n(n+1)/2

Code

#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
int main(){
freopen("inputlarge.in", "r", stdin);
freopen("outputlarge.txt", "w", stdout);
  long t, l, r, n;
  cin>>t;
  for(int cases = 1; cases <= t; cases++){
    cin>>l>>r;
    n = min(l,r);
    cout<<"Case #"<<cases<<": "<<fixed<< setprecision(0)<<1.0 * n * (n+1) / 2<<endl;
  }
  return 0;
}

Comments

Post a Comment

Popular posts from this blog

Kickstart 2017 Round A Problem A: Square Counting

Abridged problem statement Count Number of ways to select four points in RxC grid such that these four points make  a square. These squares need not be aligned with the axes. Constraints 1 ≤ T ≤ 100. Small dataset R, C < 10 3 Large dataset R,C < 10 9 Print answer modulo 10 9 + 7 Approach   Let us assume  C >= R. First count all the squares that are aligned with the axes:             number of 1x1 squares is (R-1)*(C-1)             number of 2x2 squares is (R-2)*(C-2)             ...             number of RxR squares is (R-R)*(C-R) Now count all the squares not aligned with the axes:           We can see from the above image that a N x N square has N enclosing squares( including the green squares we counted in the...
Post a Comment
Read more

Kickstart 2017 Round G: Problem A

Abridged problem statement Compute  A N! % P Constraints 1 ≤ T ≤ 100. Small dataset 1 ≤ A ≤ 10. 1 ≤ N ≤ 10. 1 ≤ P ≤ 10. Large dataset 1 ≤ A ≤ 10 5 . 1 ≤ N ≤ 10 5 . 1 ≤ P ≤ 10 5 . Approach   Just use the fact that  A m*n = (A m ) n A m*n % P = ( (A m % P) n % P ) Code # include < iostream > using namespace std ; int power ( long long x , int n , int M ) { long long result = 1 ; while ( n > 0 ) { if ( n % 2 = = 1 ) result = ( result * x ) % M ; x = ( x * x ) % M ; n = n / 2 ; } return result ; } int main ( ) { freopen ( " A-large-practice.in " , " r " , stdin ) ; freopen ( " output-large.txt " , " w " , stdout ) ; int t , a , n , p ; long long ans ; cin > > t ; for ( int i = 1 ; i < = t ; i + + ) { cin > > a > > n > > p ; ans = a ; fo...
Post a Comment
Read more