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]”
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#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 maximum departure time from start void solve() { int st_city = mp[start_city]; int end_city = mp[dest_city]; int reach_time,reach_city; memset(dist,-1,sizeof(dist)); for(int i=0;i<vb[st_city].size();i++) { if(vb[st_city][i].start>=earliest_start_time) { reach_time = vb[st_city][i].end; reach_city = vb[st_city][i].to; dist[reach_time][reach_city]= max( dist[reach_time][reach_city] , vb[st_city][i].start ); } } for(int i=earliest_start_time;i<2400;i++) { for(int j=0;j<cityNum;j++) { if(dist[i][j]==-1) continue; for(int k=0;k<vb[j].size();k++) { if(vb[j][k].start>=i) { dist[vb[j][k].end][vb[j][k].to] = max(dist[vb[j][k].end][vb[j][k].to],dist[i][j]); } } } if(dist[i][end_city]!=-1) { printf("%04d %04d\n",dist[i][end_city],i); return; } } printf("No connection\n"); } int main() { int prev_time, prev_city, cur_time, cur_city; int trainNum, noOfCities, t, arrival_time; char str[1024]; while(scanf("%d",&cityNum)&&cityNum!=0) { mp.clear(); for(int i=0;i<cityNum;i++) { scanf("%s",str); mp[str]=i; vb[i].clear(); } scanf("%d",&trainNum); for(int i=1;i<=trainNum;i++) { scanf("%d",&noOfCities); for(int j=0;j<noOfCities;j++) { scanf("%d %s",&arrival_time,str); if(j>0 && arrival_time>prev_time) { cur_time = arrival_time; cur_city = mp[str]; vb[prev_city].push_back(Schedule(cur_city,prev_time,cur_time)); } prev_time = arrival_time; prev_city = mp[str]; } } scanf("%d %s %s",&earliest_start_time,start_city,dest_city); solve(); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#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 maximum departure time from start void solve() { int st_city = mp[start_city]; int end_city = mp[dest_city]; int reach_time,reach_city; memset(dist,-1,sizeof(dist)); printf("Scenario %d\n",kase++); for(int i=0;i<vb[st_city].size();i++) { if(vb[st_city][i].start>=earliest_start_time) { reach_time = vb[st_city][i].end; reach_city = vb[st_city][i].to; dist[reach_time][reach_city]= max( dist[reach_time][reach_city] , vb[st_city][i].start ); } } for(int i=earliest_start_time;i<2400;i++) { for(int j=0;j<cityNum;j++) { if(dist[i][j]==-1) continue; for(int k=0;k<vb[j].size();k++) { if(vb[j][k].start>=i) { dist[vb[j][k].end][vb[j][k].to] = max(dist[vb[j][k].end][vb[j][k].to],dist[i][j]); } } } if(dist[i][end_city]!=-1) { printf("Departure %04d %s\n",dist[i][end_city],start_city); printf("Arrival %04d %s\n",i,dest_city); return; } } printf("No connection\n"); } int main() { int prev_time, prev_city, cur_time, cur_city; int trainNum, noOfCities, t, arrival_time; char str[1024]; scanf("%d",&t); while(t--) { scanf("%d",&cityNum); mp.clear(); for(int i=0;i<cityNum;i++) { scanf("%s",str); mp[str]=i; vb[i].clear(); } scanf("%d",&trainNum); for(int i=1;i<=trainNum;i++) { scanf("%d",&noOfCities); for(int j=0;j<noOfCities;j++) { scanf("%d %s",&arrival_time,str); if(j>0 && arrival_time>prev_time) { cur_time = arrival_time; cur_city = mp[str]; vb[prev_city].push_back(Schedule(cur_city,prev_time,cur_time)); } prev_time = arrival_time; prev_city = mp[str]; } } scanf("%d %s %s",&earliest_start_time,start_city,dest_city); solve(); printf("\n"); } return 0; } |
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 .
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <iostream> #include <cstdio> #include <cstring> #include <string> #define INF 100000000 using namespace std; int dp[85][85]; int lps[85]; string s; int prefix_function(string str) { memset(lps,0,sizeof(lps)); int len = 0; int i=1; lps[0]=0; int length = str.size(); while(i<length) { if(str[i]==str[len]) { len+=1; lps[i]=len; i+=1; } else { if(len!=0) { len = lps[len-1]; } else { len = 0; i+=1; } } } int minimal_lengthOf_repeated_str = str.size()-lps[str.size()-1]; int times = str.size()/minimal_lengthOf_repeated_str; if(str.size()==times*minimal_lengthOf_repeated_str) return minimal_lengthOf_repeated_str; else return str.size(); } int DP(int left,int right) { if(left==right) return 1; if(dp[left][right]!=-1) return dp[left][right]; string str1 = s.substr(left,right-left+1); int val = prefix_function(str1); int ans1,ans2; if(val==right-left+1) { int mn = INF; for(int i=left;i<right;i++) { ans1 = DP(left,i); ans2 = DP(i+1,right); mn = (mn<(ans1+ans2)?mn:(ans1+ans2)); } dp[left][right]=mn; } else { dp[left][right] = DP(left,left+val-1); } return dp[left][right]; } int main() { while(cin>>s) { if(s=="*") break; memset(dp,-1,sizeof(dp)); printf("%d\n",DP(0,s.size()-1)); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#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; } } } */ int main() { int t,kase=1,n; ul ans; scanf("%d",&t); //init(); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&arr[i]); } sort(arr+1,arr+n+1); ans = 1; for(int i=1;i<=n;i++) { if(arr[i]<i) { ans = 0; break; } ans = (ans*(arr[i]-i+1))%_MOD; } printf("Case %d: %llu\n",kase++,ans); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#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; } int DP(int totalTrees) { if(dp[totalTrees]!=-1) return dp[totalTrees]; int cnt=0; for(int i=0;i<n;i++) { if(totalTrees&(1<<i)) cnt+=1; } if(cnt<=restTrees) return dp[totalTrees]=0; if(cnt==1) return dp[totalTrees]=1; int MX = INF; for(int i=0;i<n;i++) { if(totalTrees&(1<<i)) { for(int j=i+1;j<n;j++) { if(totalTrees&(1<<j)) { MX = _min(MX,DP( totalTrees&(~totalpointsOfline[i][j]) )+1); } } } } return dp[totalTrees]=MX; } int main() { int t,kase=1; int idx,a,b; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(); for(int i=0;i<n;i++) { scanf("%d%d",&X[i],&Y[i]); } init(); restTrees = n-m; printf("Case #%d:\n",kase++); printf("%d\n",DP((1<<n)-1)); if(t) printf("\n"); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#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++) { scanf("%d%d",&weight[i],&capacity[i]); dp[i][capacity[i]]=1; } for(int i=2;i<=n;i++) { for(int j=0;j<3002;j++) { if(j>=weight[i]) { idx = _min(j-weight[i],capacity[i]); dp[i][idx]=_max(dp[i][idx],dp[i-1][j]+1); } dp[i][j]=_max(dp[i][j],dp[i-1][j]); } } int height=0;; for(int i=0;i<3002;i++) { height=_max(height,dp[n][i]); } cout<<height<<"\n"; } return 0; } |