Posts

Showing posts from September, 2016

CF 396/C :On Changing Tree ( BIT, Data Structure )

CF 396 /C :On Changing Tree ( BIT, Data Structure ) // /==================================================/// // / HELLO WORLD !! /// // / IT'S ME /// // / BISHAL GAUTAM /// // / [ bsal.gautam16@gmail.com ] /// // /==================================================/// #include<bits/stdc++.h> # define X first # define Y second # define mpp make_pair # define nl printf("\n") # define SZ ( x ) (int)(x.size()) # define pb ( x ) push_back(x) # define pii pair<int,int> # define pll pair<ll,ll> // /--------------------- # define S ( a ) scanf("%d",&a) # define P ( a ) printf("%d",a) # define SL ( a ) scanf("%lld",&a) # define S2 ( a , b ) scanf("%d%d",&a,&b) # define SL2 ( a , b ) scanf("%lld%lld",&a,&b) // /------------------------

UVA : 11486 - Finding Paths in Grid (Matrix expo, math)

UVA : 11486 - Finding Paths in Grid (Matrix expo, math) // /==================================================/// // / !! HELLO WORLD !! /// // / IT'S ME - BISHAL GAUTAM /// // / [ bsal.gautam16@gmail.com ] /// // /==================================================/// #include<bits/stdc++.h> # define X first # define Y second # define mpp make_pair # define pll pair<ll,ll> # define pii pair<int,int> # define pb ( x ) push_back(x) # define nl printf("\n") # define Max ( a , b ) ((a>b)?a:b) # define Min ( a , b ) ((a<b)?a:b) # define SZ ( x ) (int)(x.size()) // /--------------------- # define S ( a ) scanf("%d",&a) # define P ( a ) printf("%d",a) # define SL ( a ) scanf("%lld",&a) # define S2 ( a , b ) scanf("%d%d",&a,&b) # define SL2 ( a , b ) scanf("%lld%lld",&a,&b) /

UVA: 11551 - Experienced Endeavour (Matrix expoentiation)

UVA: 11551 - Experienced Endeavour (Matrix expoentiation) // /==================================================/// // / !! HELLO WORLD !! /// // / IT'S ME - BISHAL GAUTAM /// // / [ bsal.gautam16@gmail.com ] /// // /==================================================/// #include<bits/stdc++.h> # define X first # define Y second # define mpp make_pair # define pll pair<ll,ll> # define pii pair<int,int> # define pb ( x ) push_back(x) # define nl printf("\n") # define Max ( a , b ) ((a>b)?a:b) # define Min ( a , b ) ((a<b)?a:b) # define SZ ( x ) (int)(x.size()) // /--------------------- # define S ( a ) scanf("%d",&a) # define P ( a ) printf("%d",a) # define SL ( a ) scanf("%lld",&a) # define S2 ( a , b ) scanf("%d%d",&a,&b) # define SL2 ( a , b ) scanf("%lld%lld",&a,&b)

UVA: 10459 - The Tree Root ( Diameter of Tree, DP )

UVA : 10459 - The Tree Root ( Diameter of Tree , DP ) Problem : The problem asked to find longest level of tree assuming all node ( 1 to N ) as root . Then to find best and worst levels we got from different nodes . Idea : find starting and ending nodes of diameter of tree , then answer for each node will be maximum of distance from these endpoints . //==================================================/// /// HELLO WORLD !! /// /// IT ' S ME /// /// BISHAL GAUTAM /// /// [ bsal . gautam16@gmail . com ] /// ///==================================================/// # include < bits / stdc ++. h > # define X first # define Y second # define mpp make_pair # define nl printf( " \n " ) # define SZ (x) (int)(x . size () ) # define pb(x) push_back(x) # define pii pair < int , int > # define pll p

UVA 10003 -Cutting Sticks ( dp, Knuth Optimization )

UVA 10003 -Cutting Sticks ( dp, Knuth Optimization ) // /==================================================/// // / HELLO WORLD !! /// // / IT'S ME /// // / BISHAL GAUTAM /// // / [ bsal.gautam16@gmail.com ] /// // /==================================================/// #include<bits/stdc++.h> # define X first # define Y second # define mpp make_pair # define nl printf("\n") # define SZ ( x ) (int)(x.size()) # define pb ( x ) push_back(x) # define pii pair<int,int> # define pll pair<ll,ll> // /--------------------- # define S ( a ) scanf("%d",&a) # define P ( a ) printf("%d",a) # define SL ( a ) scanf("%lld",&a) # define S2 ( a , b ) scanf("%d%d",&a,&b) # define SL2 ( a , b ) scanf("%lld%lld",&a,&b) // /----------------------

UVA 11951- Area ( dp, Two Pointers )

UVA 11951 -Area ( dp, Two Pointers ) // /==================================================/// // / HELLO WORLD !! /// // / IT'S ME /// // / BISHAL GAUTAM /// // / [ bsal.gautam16@gmail.com ] /// // /==================================================/// #include<bits/stdc++.h> # define X first # define Y second # define mpp make_pair # define nl printf("\n") # define SZ ( x ) (int)(x.size()) # define pb ( x ) push_back(x) # define pii pair<int,int> # define pll pair<ll,ll> // /--------------------- # define S ( a ) scanf("%d",&a) # define P ( a ) printf("%d",a) # define SL ( a ) scanf("%lld",&a) # define S2 ( a , b ) scanf("%d%d",&a,&b) # define SL2 ( a , b ) scanf("%lld%lld",&a,&b) // /------------------------------------ # de

UVA 836 - Largest Submatrix ( DP, Largest 1s Submatrix )

UVA 836 - Largest Submatrix ( DP, Largest 1s Submatrix ) // /==================================================/// // / HELLO WORLD !! /// // / IT'S ME /// // / BISHAL GAUTAM /// // / [ bsal.gautam16@gmail.com ] /// // /==================================================/// #include<bits/stdc++.h> # define X first # define Y second # define mpp make_pair # define nl printf("\n") # define SZ ( x ) (int)(x.size()) # define pb ( x ) push_back(x) # define pii pair<int,int> # define pll pair<ll,ll> // /--------------------- # define S ( a ) scanf("%d",&a) # define P ( a ) printf("%d",a) # define SL ( a ) scanf("%lld",&a) # define S2 ( a , b ) scanf("%d%d",&a,&b) # define SL2 ( a , b ) scanf("%lld%lld",&a,&b) // /------------------

UVA 108 - Maximum Sum (2D MAX SUM)

UVA 108 - Maximum Sum ( 2 D MAX SUM )     Problem : Given 2 D (N*N) array with some + ve & - ve integers .  You have to compute the sum of submatrix with maximum sum. IDEA : 1. ) Fix one column lft . 2. ) Fix one column rgt from lft to rgtmost corner. 3. ) For every fixed lft & rgt column, traverse below rowwise &   calculate cumulative sum. Note : We have to precalculate rowise sum earlier. 4. ) If sum becomes negative then , make it 0 & update maximum sum on every step. So, overall complexity is O ( N ^ 3 ) . / / / = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = / / / / / / HELLO WORLD !! / / / / / / IT 'S ME / / / / / / BISHAL GAUTAM / / / / / / [ bsal.gautam16@gmail.com ] / / / / / / = = = = = = = = = = = = = = = = = = =

UVA 153 -Permalex ( Permutation, Math, Overflow handling )

UVA 153 -Permalex ( Permutation, Math, Overflow handling ) // /==================================================/// // / HELLO WORLD !! /// // / IT'S ME /// // / BISHAL GAUTAM /// // / [ bsal.gautam16@gmail.com ] /// // /==================================================/// #include<bits/stdc++.h> # define X first # define Y second # define mpp make_pair # define nl printf("\n") # define SZ ( x ) (int)(x.size()) # define pb ( x ) push_back(x) # define pii pair<int,int> # define pll pair<ll,ll> // /--------------------- # define S ( a ) scanf("%d",&a) # define P ( a ) printf("%d",a) # define SL ( a ) scanf("%lld",&a) # define S2 ( a , b ) scanf("%d%d",&a,&b) # define SL2 ( a , b ) scanf("%lld%lld",&a,&b) // /------------------

UVA 11019 - Matrix Matcher( 2D String matching, Rolling Hash )

UVA 11019 - Matrix Matcher ( 2D String matching, Rolling Hash ) Problem: Given 2D Text string and 2D pattern string, you have to count how many times 2D pattern occurs in 2D Text. Idea: Rolling Hash, Firstly compute hashes of segement of fixed window on row , then stored it. Then, Taking these Stored hash value as alphabets calculate hash on column on fixed window using rolling hash mechanism. // /==================================================/// // / HELLO WORLD !! /// // / IT'S ME /// // / BISHAL GAUTAM /// // / [ bsal.gautam16@gmail.com ] /// // /==================================================/// #include<bits/stdc++.h> # define X first # define Y second # define mpp make_pair # define nl printf("\n") # define SZ ( x ) (int)(x.size()) # define pb ( x ) push_back(x) # define pii pair<int,int> # define pll