Problem: Given a string consisting of opening and closing parenthesis, find length of the longest valid parenthesis sub string.[Courtesy: geeksforgeeks] Problem Link Solution: The problem can be solved with DP approach . And also as counting the left and right parenthesis from left to right.If the left parenthesis count is less than the right parenthesis
Continue Reading “Find Longest valid Parentheses Length [ Google ]”
Problem: Count the maximum number of ways we can parenthesize of a given boolean expression so that the value of expression evaluates to true or false as asked. Boolean expression will be given with following symbols. Symbols ‘T’ —> true ‘F’ —> false And the Operators & —> boolean AND | —>
Continue Reading “Maximum Boolean Parenthesization String [ Microsoft, Amazon]”
Problem: Find the length and/or string of the longest palindrome of a string. The problem appeared as an Interview question in Amazon, Microsoft. Solution: One important property of a palindrome is if we remove the first and last characters of it , it would be another palindrome. So A string S[a..b] will be a palindrome
Continue Reading “Find the longest palindrome of a String [Amazon,Microsoft]”
#include <iostream> #include <algorithm> #include <queue> #include <cstdio> #include <cstring> #include <string> #include <map> #include <vector> using namespace std; struct Schedule{ int to; int start,end; Schedule(int a,int b,int c) { to = a; start = b; end = c; } }; vector<Schedule> vb[101]; int kase=1; map<string,int> mp; char dest_city[1024], start_city[1024]; int earliest_start_time, cityNum; int dist[2400][101];//saves
#include <iostream> #include <algorithm> #include <queue> #include <cstdio> #include <cstring> #include <string> #include <map> #include <vector> using namespace std; struct Schedule{ int to; int start,end; Schedule(int a,int b,int c) { to = a; start = b; end = c; } }; vector<Schedule> vb[101]; int kase=1; map<string,int> mp; char dest_city[1024], start_city[1024]; int earliest_start_time, cityNum; int dist[2400][101];//saves
There is a problem with online judge results for this problem. It accepts for n=6 as AC result as : 2^-6 = 1.562e-2 and for n=7 AC result as : 2^-7 = 7.812e-3 But it should be 2^-6 = 1.563e-2 and 2^-7 = 7.813e-3 respectively using approximation method after 3rd decimal. So to get AC from UVA OJ I
This is a dp problem where kmp algorithm(specially prefix function) is used to solve the problem. If a string is multiple of a repeated string then the difference between the string length and last index of the prefix table indicates the minimal length of the repeated string. A brief and nice discussion is available here . #include
#include <iostream> #include <cstdio> #include <cmath> #include <climits> #include <inttypes.h> #include <cstring> #include <string> #include <algorithm> #define INF 1000000 #define _MOD 1000000007 #define ul unsigned long long using namespace std; int arr[105]; unsigned long long ncr[105][105]; /* void init() { ncr[1][1]=1; for(int i=2;i<105;i++) { ncr[i][1]=i; for(int j=2;j<=i;j++) { ncr[i][j] = ( (ncr[i-1][j-1]%_MOD) + (ncr[i-1][j]%_MOD) )%_MOD;
#include <iostream> #include <cstdio> #include <cmath> #include <climits> #include <cstring> #include <string> #define INF 1000000 using namespace std; int X[20],Y[20]; int totalpointsOfline[20][20]; int m,n,restTrees; int dp[66000]; void init() { memset(totalpointsOfline,0,sizeof(totalpointsOfline)); for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { for(int k=n-1;k>=0;k–) { totalpointsOfline[i][j]<<=1; if( (Y[j]-Y[i])*(X[k]-X[i])==(Y[k]-Y[i])*(X[j]-X[i])) totalpointsOfline[i][j]+=1; } } } memset(dp,-1,sizeof(dp)); } int _min(int a,int b) { return a<b?a:b;
#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std; int n; int dp[1002][3002]; int capacity[1002]; int weight[1002]; void init() { for(int i=0;i<1002;i++) for(int j=0;j<3002;j++) dp[i][j]=0; } int _max(int a,int b) { return a>b?a:b; } int _min(int a,int b) { return a<b?a:b; } int main() { int idx; while(scanf("%d",&n),n) { init(); for(int i=1;i<=n;i++) {