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 1048 - Conquering Keokradong

Problem link:

Problem Analysis:

It is actually a basic Bisection problem , as we can see here we can not actually find a formula for the camp distance but what we can do is for a certain camp distance we can check how many nights or how many nights we must stay in a camp. and if that's less than k than we are good but else we need to check for smaller distances.

 here isp() function just validates for any certain distance is it possible to do it less than or equal k nights or not. and in the main function that bisection just puts the data from the function to Isp() to search for a better result.

If for certain "l" Isp(l) returns true than we check if there is another l' which is l'<l and still isp(l')  returns true or not.

else we increse I and check for the isp(I) for which it is true result again. The printing part is a little tricky But can be done. 

Here goes the code:  

1. #include <bits/stdc++.h>
2. using namespace std;
3. vector<int>v;
4. int k;
5. bool isp(int l){
6.     int co = 0;
7.     int sum =v[0];
8.     for(int i = 1; i <v.size(); i++){
9.         if(v[i]>l) return false;
10.         else if(sum+v[i]<=l){
11.             sum+= v[i];
12.         }
13.         else{
14.             sum = v[i];
15.             co++;
16.         }
17.     }
18.     if(co<=k) return true;
19.     return false;
20. }
21. void prt(int l){
22.     int sum= 0;
23.     int co = 0;
24.     for(int i = 0; i <v.size(); i++){
25.         sum+= v[i];
26.         if(sum>l){
27.             printf("%d\n", sum-v[i]);
28.             sum = v[i];
29.             co++;
30.         }
31.         if(k-co+1>=v.size()-i){
32.             printf("%d\n", sum);
33.             for(int j = i+1; j <v.size(); j++) printf("%d\n", v[j]);
34.             break;
35.         }
36.     }
37. }
38. int main(){
39.     int ts;
40.     scanf("%d", &ts);
41.     for(int p = 1; p <= ts; p++){
42.     v.clear();
43.     int n,low = INT_MIN, high = 0, mid = 0, ans;
44.     scanf("%d%d", &n, &k);
45.     for(int i = 0; i <=n; i++){
46.         int a;
47.         scanf("%d", &a);
48.         high+= a;
49.         v.push_back(a);
50.         low = max(low, a);
51.     }
52.     while(high-low>2){
53.         mid = (low+high)/2;
54.         if(isp(mid)) high = mid;
55.         else low = mid;
56.     }
57.     for(int i  = high; i >= low; i--) if(isp(i)) ans = i;
58.     printf("Case %d: %d\n",p,  ans);
59.     prt(ans);
60.     }
61.     return 0;
62. }

Lightoj 1307 - Counting Triangles

Problem link:

Problem Analysis: 

for any triangle with edges a, b, c we know that 

(1)   a + b > c

(2)   b + c > a

(3)   c + a > c

for being a valid triangle it must follow all these . we can use a brute force algorithm O(n^3) with 3 nested loops and checking the validity of those selected edges of those but it's too big so we will try to make this better.  So first we sort the array of lengths for simplicity.

 Than for each 'e1' we select another edge after that and thats 'e2' and we know we sorted the aray so e1<=e2. After that we search the maximum element 'e3' that follows all three of those triangle validity formula we wrote above.

 we already know that e1+e3 > e2 and e2 + e3 > e1 as they are sorted and e1<= e2 < e3 so we just need to find the maximum edge length for which e1+e2>e3. and than we also know that all the edges between e2 and e3 also makes valid triangles.  because they also follow all the three rules.

So we just search index  of (e1+e2-1)  using binary search.

here we searched for (e1+e2-1) we used -1 because e1+e2 , e1, e2 these three can not actually make a valid triangle. After finding the upper bound of e3 (e1+e2-1) we just add the difference of the index of e2 and e3 and repeat it for the next e1, e2' .  so our algorithm now becomes
O(N^2 + Nlog(N)) = O(N^2) that easily passes. 

for better visualization go here  

Here goes the code: 

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main(){
4.     int ts;
5.     scanf("%d", &ts);
6.     for(int p = 1; p <= ts; p++){
7.     int n;
8.     scanf("%d", &n);
9.     vector<int>v;
10.     for(int i = 0; i <n; i++){
11.         int a;
12.         scanf("%d", &a);
13.         v.push_back(a);
14.     }
15.     sort(v.begin(), v.end());
16.     long long unsigned sum = 0;
17.     for(int i = 0; i <n-2; i++){
18.         for(int j = i+1; j<n-1; j++){
19.             sum+= upper_bound(v.begin(), v.end(),v[i]+v[j]-1)-v.begin()-j-1;
20.         }
21.     }
22.     printf("Case %d: %llu\n",p,  sum);
23.     }
24.     return 0;
25. }