Lightoj 1159 - Batman

http://lightoj.com/volume_showproblem.php?problem=1159

problem analysis:

First i thought of this as if s1, s2 and s3 are those three strings than if i find the lcs of s1 and s2 and again i call the same function for the lcs of (lcs of s1 and s2) and s3 than that is my answer after coding the commented down below part i found that it is not entirely true as we all know any two strings can have not single but many lcs  so if i find a lcs for the first two strings and than run it with the third one that only means that specific lcs doesn't match with the third one but there may  another lcs that matches entirely. so i had to change the whole structure  . new one is similar to the lcs of two strings just it's 3D.

Here Goes the Code:

1. #include <bits/stdc++.h>
2. using namespace std;
3. string s1, s2, s3;
4. int l1, l2, l3;
5. int dp[50+1][50+1][50+1];
6. int lcs(){
7.     memset(dp, 0, sizeof(dp));
8.     for(int i = 1; i <= l1; i++){
9.         for(int j = 1; j <=l2; j++){
10.             for(int k= 1; k <= l3; k++){
11.                 if(s1[i-1] == s2[j-1] && s2[j-1] == s3[k-1])dp[i][j][k] = 1+ dp[i-1][j-1][k-1];
12.                 else dp[i][j][k] = max(max(dp[i][j][k-1], dp[i-1][j][k]), dp[i][j-1][k]);
13.             }
14.         }
15.     }
16.     return dp[l1][l2][l3];
17. }
18. int main(){
19.     int ts;
20.     scanf("%d", &ts);
21.     for(int p = 1; p <=ts; p++){
22.     cin>>s1>>s2>>s3;
23.     l1 = s1.length();
24.     l2 = s2.length();
25.     l3 = s3.length();
26.     printf("Case %d: %d\n", p, lcs());
27.     }
28.     return 0;
29. }
30.  
31. /*
32. int lcsa(){
33.     memset(dp, 0, sizeof(dp));
34.     for(int i = 1; i <= l1; i++){
35.         for(int j = 1; j <=l2; j++){
36.             if(s1[i-1] == s2[j-1])dp[i][j] = 1+ dp[i-1][j-1];
37.             else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
38.         }
39.     }
40.    
41.     for(int i = 0; i <= l1; i++){
42.         for(int j = 0; j <= l2; j++){
43.             printf("%d ", dp[i][j]);
44.         }
45.         printf("\n");
46.     }
47.    
48.     return dp[l1][l2];
49. }
50. string ans(){
51.     int index = lcsa();
52.     char lcs[index+1];
53.    lcs[index] = '\0';
54.    int i = l1, j = l2;
55.    while (i > 0 && j > 0)
56.    {
57.       if (s1[i-1] == s2[j-1])
58.       {
59.           lcs[index-1] = s1[i-1]; // Put current character in result
60.           i--; j--; index--;     // reduce values of i, j and index
61.       }
62.     else if (dp[i-1][j] > dp[i][j-1]) i--;
63.     else j--;
64.    }
65.   string ans(lcs);
66.   return ans;
67.    
68. }
69.  
70. int main(){
71.     int ts;
72.     scanf("%d", &ts);
73.     for(int p = 1; p <=ts; p++){
74.     cin>>s1>>s2>>s3;
75.     l1 = s1.length();
76.     l2 = s2.length();
77.     s1 = ans();
78.     s2 = s3;
79.     l1 = s1.length();
80.     l2 = s2.length();
81.     printf("Case %d: %d\n", p, lcsa());
82.     }
83.     return 0;
84. }
85. */

Lightoj 1382 - The Queue

http://lightoj.com/volume_showproblem.php?problem=1382

Problem analysis:

This is a rare problem i wrote about so far.  After much struggling we can actually see that this is nothing but a tree combination that means we can represent each permutation of queue as a tree where the root is the supervisor and each of the  employee under that supervisor is the the child of that root. that means in the queue no child can be before it's root. after building the tree the only question is how many ways are there to represent the queue using the tree where no child is before and root or root of root?

After much struggling and using different combinatorics rules we can see that there is no way without making the problem smaller (yeah i am talking about DP) and building the ultimate answer using those smaller results. So first these questions are important to answer??
1. What this root actually means of the tree??
2. How the childs are connected to the root?? By this I mean how to combine the results of the childs results to construct the roots result??
and finally
3. how to find the result of the childs??

Answers:
1. root means whatever i do later that is not my concern but right now this root must be in the position (the child or child of child is for later)  and  than go for the childs.

2. here for each root we can calculate how many positions available after fixing the position of the root and than we can also calculate how many positions are needed for a certain child(total number of that child including that child) so if our function is dp(int root) for each child we can just use

ncr(total_positions_available,positions_needed_for_child_i)*dp(i)

we can pre calculate the values of ncr and after constructing the tree we can easily calculate number of childs of each root. that we can use the DP function to find the answer.

Here goes the code.

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define MOD 1000000007
4. #define llu long long unsigned
5. vector<int>v[1005];
6. bool vis[1005];
7. llu chi[1005];
8. llu ncr[1005][1005];
9. llu dp[1005];
11. llu child(llu root){
12.     if(v[root].size() == 0) return chi[root] = 1;
13.     llu sum = 0;
14.     for(int i = 0; i <(int)v[root].size(); i++){
15.         sum += child(v[root][i]);
16.     }
17.     return chi[root] = 1+sum;
18. }
19. void NCR(){
20.     ncr[0][0] = 1;
21.     for(int i = 1; i <1005; i++){
22.         for(int j = 0; j <=i; j++){
23.             if(j == 0 || j == i) ncr[i][j] = 1;
24.             else ncr[i][j]= (ncr[i-1][j]+ncr[i-1][j-1])%MOD;
25.         }
26.     }
27.     /*
28.     for(int i = 0; i <10; i++){
29.         for(int j = 0; j <10; j++){
30.             printf("%d ", ncr[i][j]);
31.         }
32.         printf("\n");
33.     }
34.     */
35. }
36. llu DP(llu root){
37.     llu totalsize = chi[root]-1; // except himself
38.     llu ans = 1;
39.     for(int i = 0; i <(int)v[root].size(); i++){
40.         llu chld = v[root][i];
41.         llu chldsize = chi[chld];
42.         ans*=(ncr[totalsize][chldsize]*DP(chld))%MOD;
43.         ans%=MOD;
44.         totalsize-=chldsize;
45.     }
46.     return dp[root] = ans;
47. }
48. int main(){
49.     NCR();
50.     int ts;
51.     scanf("%d", &ts);
52.     for(int p = 1; p <=ts; p++){
53.     int n;
54.     scanf("%d", &n);
55.     memset(vis, false, sizeof(vis));
56.     for(int i = 1; i <=n; i++) v[i].clear();
57.     for(int i = 1; i <n; i++){
58.         int a, b;
59.         scanf("%d%d", &a, &b);
60.         v[a].push_back(b);
61.         vis[b] = true;
62.     }
63.     int mark;
64.     for(int i = 1; i <=n; i++){
65.         if(!vis[i]){mark = i;break;}
66.     }
67.     child(mark);
68.     printf("Case %d: %lld\n",p,  DP(mark));
69.     }
70.     return 0;
71. }

Lightoj 1326 - Race

http://lightoj.com/volume_showproblem.php?problem=1326

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define ll long long int
4. #define M 10056
5. int DP[1005][1005];
6. int dp[1005];
7. int bc(int n, int k){
8.     int i, j;
9.     for (i = 0; i <= n; i++){
10.         for (j = 0; j <=  k; j++){
11.             if (j == 0 || j == i)
12.                 DP[i][j] = 1;
13.  
14.             else
15.                 DP[i][j] = (DP[i-1][j-1]%M + DP[i-1][j]%M)%M;
16.         }
17.     }
18. }
19. int main(){
20.     bc(1000, 1000);
21.     dp[0] = dp[1] = 1;
22.     dp[2] = 3;
23.     for(int i = 3; i <= 1000; i++){
24.         for(int j = i-1; j>=0; j--){
25.             dp[i]+= (dp[j]%M)*(DP[i][i-j]%M)%M;
26.             dp[i]%=M;
27.         }
28.     }
29.     /*
30.     for(int  i = 0; i <=1000; i++){
31.         for(int j = 0; j <=1000; j++){
32.             cout<<DP[i][j]<<" ";
33.         }
34.         cout<<endl;
35.     }
36.     */
37.     //int n;
38.     //scanf("%d", &n);
39.     //for(int i = 1; i<10; i++) cout<<dp[i]<<" ";
40.     int ts;
41.     scanf("%d", &ts);
42.     for(int i = 1; i <= ts; i++){
43.         int n;
44.         scanf("%d",&n);
45.         printf("Case %d: %d\n", i, dp[n]);
46.     }  
47.     return 0;
48. }

Lightoj 1110 - An Easy LCS

http://lightoj.com/volume_showproblem.php?problem=1110

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define For(i,a) for(int i=0;i<a;++i)
4. #define foreach(x,v) for(typeof (v).begin() x = (v).begin(); x!= (v).end(); x++)
5. #define all(x) x.begin(),x.end()
6. #define rall(x) x.rbegin(),x.rend()
7. #define D(x) cout<< #x " = "<<(x)<<endl
8. #define Dbg if(1)
9. #define MAXNODES 1000
10.  
11. int dp[101][101];
12. string lex[101][101];
13.  
14. int lcs(const string &a,const string &b, string &ans){
15.   int n=a.size(),m=b.size();
16.   if(n==0 || m==0) return 0;
17.   for(int i=0;i<=n;++i){
18.     dp[i][0] = 0;
19.     lex[i][0].clear();
20.   }
21.   for(int j=0;j<=m;++j){
22.     dp[0][j] = 0;
23.     lex[0][j].clear();
24.   }
25.   for(int i=1;i<=n;i++){
26.     for(int j=1;j<=m;++j){
27.       if(a[i-1]==b[j-1]){
28.         dp[i][j] = dp[i-1][j-1]+1;
29.         lex[i][j] = lex[i-1][j-1] + a[i-1];
30.       }
31.       else if(dp[i][j-1] > dp[i-1][j]){
32.         dp[i][j] = dp[i][j-1];
33.         lex[i][j] = lex[i][j-1];
34.       }else if(dp[i][j-1] < dp[i-1][j]){
35.         dp[i][j] = dp[i-1][j];
36.         lex[i][j] = lex[i-1][j];
37.       }else{
38.         dp[i][j] = dp[i-1][j];
39.         lex[i][j] = min(lex[i-1][j],lex[i][j-1]);
40.       }
41.     }
42.   }
43.  
44.   ans=lex[n][m];
45.  
46.   return dp[n][m];
47. }
48.  
49. int main(){
50.   int numcas;cin>>numcas;
51.   for(int cid=1;cid<=numcas;++cid){
52.     string a,b;cin>>a>>b;
53.     string ans;
54.     cout<<"Case "<<cid<<": "<<((lcs(a,b,ans)==0)?":(":ans)<<endl;
55.   }
56.   return 0;
57. }

1. /*
2. // another implementation
3. #include <bits/stdc++.h>
4. using namespace std;
5. #define N 100
6. int L[N][N];
7.  set<string> findLCS(string X, string Y, int m, int n){
8.     set<string> s;
9.     if (m == 0 || n == 0){
10.         s.insert("");
11.         return s;
12.     }
13.  
14.     if (X[m - 1] == Y[n - 1]){
15.         set<string> tmp = findLCS(X, Y, m - 1, n - 1);
16.     for (string str : tmp)
17.             s.insert(str + X[m - 1]);
18.     }
19.     else{
20.         if (L[m - 1][n] >= L[m][n - 1])
21.             s = findLCS(X, Y, m - 1, n);
22.     if (L[m][n - 1] >= L[m - 1][n]){
23.             set<string> tmp = findLCS(X, Y, m, n - 1);
24.         s.insert(tmp.begin(), tmp.end());
25.         }
26.     }
27.     return s;
28. }
29.  
30. int LCS(string X, string Y, int m, int n){
31.     for (int i = 0; i <= m; i++){
32.         for (int j = 0; j <= n; j++){
33.             if (i == 0 || j == 0)
34.                 L[i][j] = 0;
35.             else if (X[i - 1] == Y[j - 1])
36.                 L[i][j] = L[i - 1][j - 1] + 1;
37.             else
38.                 L[i][j] = max(L[i - 1][j], L[i][j - 1]);
39.         }
40.     }
41.     return L[m][n];
42. }
43.  
44. int main(){
45.     int ts;
46.     cin>>ts;
47.     for(int k = 1; k <= ts; k++){
48.     string X;
49.     string Y;
50.     cin>>X>>Y;
51.     int m = X.length();
52.     int n = Y.length();
53.     //cout << "LCS length is " << LCS(X, Y, m, n) << endl;
54.     set<string> s = findLCS(X, Y, m, n);
55.     set<string> :: iterator p;
56.     p = s.begin();
57.     if((*p) == "") printf("Case %d: :(\n", k);
58.     else printf("Case %d: %s\n", k, (*p).c_str());
59.     s.clear();
60.     }
61.     return 0;
62. }
63.  
64. */

1.