/** * H:\Dropbox\Code\CodeChef\Practice\NOKIA Connecting Soldiers.cpp * Created on: 2015-03-18-23.17.22, Wednesday * Verdict: Solved * Author: Enamul Hassan * Concept: This problem has a dp solution, but I did it with greedy observation. Now, lets discuss the main theme. With some paper work for small cases, I observed that, all the permutations' outputs remains in a continuous range. That means, if we could find the highest and lowest value of this range, then its easy to calculate the rest. By observing a little bit deeply, we can see that it is related to partitioning. That means, we can divide the problem into same sub-problems with smaller range. If we take n spots, and choose the spot from either end, then the rest of the problem is for n-1 spots. Similarly, we can choose either end and call for n-2 and so on. This partitioning is very slow, because we are making the problem only one less than the problem was in the last step. This permutation could be 1 2 3 ... n So, by doing this, we are getting the highest value of the range. On the other hand, if we want to get the lowest value of the range, we have to divide the sub-problem into smallest possible part. In one step having n spots,we can divide it into two sub-problems of ceil(n/2) spots. Example: for n = 3, 2 1 3 or 3 1 2 is a possible permutation for getting the lowest value. The highest value can be found by a formula, but I did it generating the permutation and calculating from it. The formula is (n+1)*(n+2)/2-1. I calculated the lowest value by dividing into sub problems approach where base case is: if n = 2, then one of it is tower and another is spot. So, two miles wire needed. if n = 1, then it is a tower, so no need to use wire. If the purchased wire is smaller then the lowest value, then -1 would be printed. If it is larger than largest value, then the difference between the largest value and the purchased wire would be the output, otherwise output would be zero! **/ #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define pb(a) push_back(a) #define ll long long #define fread freopen("input.txt","r",stdin) #define fwrite freopen("output.txt","w",stdout) using namespace std; ll t, n, ans, m, high, low; vector<int>v; ll calc() { ll now = 0, up, down; for(int co = 1; co<=n; co++) for (int i = 0; i<n; i++) { if(v[i]==co) { for (up = i+1; up<n; up++) if(v[up]<co) break; now+=up-i; for (down = i-1; down>=0; down--) if(v[down]<co) break; now+=i-down; } } return now; } ll calcs(int k) { if(k<=1) return 0; if(k==2) return 2; int mid = k/2; return calcs(mid)+calcs(k-mid)+k; } int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM _ // clock_t begin, end; // double time_spent; // begin = clock(); cin>>t; while(t--) { cin>>n>>m; low = calcs(n+1); v.clear(); for (int i = 1; i<=n; i++) v.pb(i); high = calc(); if(m<low) cout<<-1<<"\n"; else if(m>=low && m<=high) cout<<0<<"\n"; else cout<<m-high<<"\n"; } // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
Thursday, March 19, 2015
CodeChef: NOKIA Connecting Soldiers
CodeChef: LUCKY8 Little Elephant and Product
/** * H:\Dropbox\Code\CodeChef\Practice\LUCKY8 Little Elephant and Product.cpp * Created on: 2015-03-19-03.10.31, Thursday * Verdict: Solved * Author: Enamul Hassan * Concept: This problem can be solved easily by using Digit DP. The parameter would be: 1. Current digit number which is now processing, 2. number of four I could take, 3. number of five. 4. start flag 5. end flag where flags determine the current digit range. The combination of this five parameter would give the same result and they would be used repeatedly. So, we can use them as DP parameter. The base case would be: when the last digit processing is finished, then I can calculate the result by multiplying the number of four and the number of seven. The start flag on means I already put a digit which is greater than the corresponding digit in smaller number, here L, so now I can put any of 10 digits in this position, otherwise I could put only those digits which are greater than or equal to the corresponding digit in L. Similarly, the end flag on means I already put a digit which is less than the corresponding digit in larger number, here R, so now I can put any of 10 digits in this position, otherwise I could put only those digits which are less than or equal to the corresponding digit in R. If the current digit equal to 4 or 7 , the parameter number of four or seven would be increased by 1. Why we add one thing in dp parameter? because, without this parameter the overlapping calls would give the same value, but actually it should differ. In these problem, these five parameter could uniquely say that, if any call comes with the same parameter here, then it should walk the same way which I already walked and stored the result. So, no need to walk the same way my friend! take the result from me! One important thing is that, length of both number should be same. So, if it is not same, we would make it same. **/ #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define fread freopen("input.txt","r",stdin) #define fwrite freopen("output.txt","w",stdout) #define clr(abc,z) memset(abc,z,sizeof(abc)) using namespace std; string a,b; int n,dp[20][20][20][2][2]; int rec(int pos, int four, int seven, bool low, bool high) { if(pos == n) return four*seven; int &ret = dp[pos][four][seven][low][high]; if(ret != -1) return ret; ret = 0; for (int i = (low?'0':a[pos]); i<= (high?'9':b[pos]); i++) ret = max(ret, rec(pos+1,four+(i=='4'),seven+(i=='7'), low | (i > a[pos]), high | (i < b[pos]))); return ret; } int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM int t; _ // clock_t begin, end; // double time_spent; // begin = clock(); cin>>t; while(t--) { cin>>a>>b; clr(dp,-1); n = b.size(); while(n>a.size()) a='0'+a; cout<< rec(0,0,0,0,0) <<"\n"; } // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
Wednesday, March 18, 2015
CodeChef: CAKEDOOM Doom Bakes Cakes
/** * H:\Dropbox\Code\CodeChef\Practice\CAKEDOOM Doom Bakes Cakes.cpp * Created on: 2015-03-18-21.48.03, Wednesday * Verdict: Solved * Author: Enamul Hassan * Concept: This problem can be solved by path dp, but I solved it using greedy concept. In the problem, they already said that what to do if n = 1. After this condition, now, we want to filter those cases for which the answer would be "NO". They are: 1. Already invalid, that means there exists same values any of the adjacent places. 2. k = 1 when n>1 where n = |S|. Example: ?? --> 00 (invalid) 3. k = 2: a. when n is odd. Example: 1???0 --> 10100 (invalid) b. when odd numbers of question marks occur with unequal end values. Example: 1???0 --> 10100 (invalid) c. when even numbers of question marks occur with equal end values.Example: 1??1 --> 1011 (invalid) For all other cases a valid solution exists. So, in every places where question mark would come, we would try to put lower values for getting lexicographically smaller string. I did it recursively, but we have to ensure that, no recursion call would occur after getting one solution. For checking purpose, we would concatenate the replicating string of the original string as the positions are cyclic. **/ #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define fread freopen("input.txt","r",stdin) #define fwrite freopen("output.txt","w",stdout) using namespace std; bool got; string ans,s, tew; int k,n; void rec(int pos) { if(got) return; if(pos == n) { if(!got)tew = ans; got = true; return; } if(s[pos]!='?') { rec(pos+1); return; } for (int i = 0; i<k; i++) { if( (!pos&&s[n-1]!=(i+'0')&&s[pos+1]!=(i+'0')) ||/// pos = 0 (pos==n-1&&(ans[pos-1]!=(i+'0')&&ans[0]!=(i+'0'))) || /// pos = n-1 (pos&&pos!=n-1&&ans[pos-1]!=(i+'0')&&s[pos+1]!=(i+'0')) ) { ans[pos]=i+'0'; if(got)return; rec(pos+1); } } } int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM _ // clock_t begin, end; // double time_spent; // begin = clock(); int t; bool flag; string now; cin>>t; while(t--) { flag = true; got = false; cin>>k>>s; n = s.size(); if(n==1) { if(s=="?") cout<<"0\n"; else cout<<s<<"\n"; continue; } if(k==1) { cout<<"NO\n"; continue; } ///replication now = s+s; if(k==2) { if(n%2) flag = false; int pum = now.size(), koyta=0, agerta=-1; for (int i =1; i<pum; i++) { if(!got) { if(now[i]!='?') got=true; continue; } if(now[i]=='?') if(!koyta++) agerta = now[i-1]; else if(koyta) { if((koyta%2==1&&agerta!=now[i] ) ///odd # of '?' ||(koyta%2==0&&agerta==now[i])) { flag = false; break; } koyta=0; } } } ///checking the existence of already invalid case for (int i = 0; i<n; i++) if(now[i]==now[i+1]&&now[i]!='?') { flag = false; break; } if(!flag) { cout<<"NO\n"; continue; } ans = s; got = false; rec(0); cout<<tew<<"\n"; assert(got); } // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
Tuesday, March 17, 2015
Timus: 1084. Goat in the Garden
/** * H:\Dropbox\Code\Timus\1084. Goat in the Garden.cpp * Created on: 2015-03-15-05.15.37, Sunday * Verdict: Not Solved * Author: Enamul Hassan * Concept: Centering the stake, the goat could explore within a limited area in the field and the area is nothing but a circle having the radius equals to the length of the rope and the kitchen-garden is a square. So, What are the possible scenarios of the problem? The scenarios could be classified into 3 type. 1. The square is totally inside the circle. 2. The circle is totally inside the square. 3. Both overlap some area. For the first two, the answer is clear. In the first case, the area of the square is the answer of the problem and in the second case, the area of the circle is the answer. However, the main thing is to decide when the first scenario would come and when the second. The first scenario would come when the diameter of the circle would be greater than the diagonal of the square. The second scenario would come when the side of the square is less than or equal to the diameter of the circle. Lets talk about the overlapping scenario. We can take the area of the circle but to get the answer, we have to subtract the area of the portion which gone outside the square. We can calculate the area of this portion from one side and subtract them multiplying by 4 as it is same in all four sides. A_____________ E|\ | /|\ \ | / | \ \ | | D|_____C | \ | | \| | F|_____________| B The above picture may give an idea. We know that, to get the idea, no need to have a clear and exact picture. However, AC is the half of the diagonal of the square and CE is the radius of the circle. We can draw a perpendicular line from the center to side BE. Say this line is CD. Here, we don't know the length of DE but know the length of AD, because it is the half of the side of the square. In the right Triangle ACD, CD is the base and AD is the height and AC is the hypotenuse. Using Pythagorean theorem, we get, AC^2 = AD^2 + CD^2 Lets the half of the side, s = AD and the diagonal, diag = AC, so, we can get the base, b = CD = square_root( diag^2 - s^2 ). From the right triangle CDE, CD is the base and DE is the height and CE is the hypotenuse. Using Pythagorean theorem, we get, CE^2 = DE^2 + CD^2 Radius of the circle, r = CE, and lets DE = x. So, x = square_root( r^2 - b^2 ). Now, we know, cos(ECD) = CD/CE = b/r. ECD = cos(b/r)^-1. Here, the angle ECF, theta = 2 * angle ECD = 2 * cos(b/r)^-1. Lets talk about the area of a circle. 2PI angle makes a circle having the area = PI*r*r 1 angle makes a circle having the area = PI*r*r/(2*PI) T angle makes a circle having the area = r*r*T/2 theta angle would make area = r*r*2 * (cos(b/r)^-1)/2 = r*r*(cos(b/r)^-1). To calculate the extended area we have to subtract the area of the ACB triangle. In ACB triangle, height, CD = b, base, AB = 2*s. So, the area of the triangle ACB = b*2*s/2 = b*s. So, the final answer equals to PI*r*r - ( r*r*(cos(b/r)^-1) - b*s ). * Special Thanks to: Rumman Mahmud Mahdi Al Masud. **/ #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define fread freopen("input.txt","r",stdin) #define fwrite freopen("output.txt","w",stdout) #define PI acos(-1) using namespace std; int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM int t, n, m, cas=1; _ // clock_t begin, end; // double time_spent; // begin = clock(); double diag,r,area,d, side; cin>>n>>m; r = m; d = 2*r; diag =side= n; diag*= sqrt(2); if(diag<=d) area = side*side; else { area = PI*r*r; if(d>side) { double h = side/2.0; double theta = acos(h/r); double l = sqrt(r*r - h*h ); area -=(4*( theta * r * r - side * l * .5)); } } cout<<fixed<<setprecision(3)<<area; // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
Monday, March 16, 2015
Timus: 1352. Mersenne Primes
/** * H:\Dropbox\Code\Timus\1352. Mersenne Primes.cpp * Created on: 2015-03-16-23.25.19, Monday * Verdict: Solved * Author: Enamul Hassan * Concept: All the answers are given in the problem statement. Just seek and gather them. Only 3 to 8 number powers are not given. Any brute force algorithm would work. You can find them off-line and put them. The brute force algorithm are given in the comment. How to check n is prime or not? A very naive approach can be like: having a loop through 2 to n - 1 where any of the value can divide n without any remainder, that means mod value equals to zero. If any value can divide, then it is not prime, otherwise it is a prime. **/ #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define fread freopen("input.txt","r",stdin) #define fwrite freopen("output.txt","w",stdout) using namespace std; map<int,int>ans; int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM _ // clock_t begin, end; // double time_spent; // begin = clock(); int t, n; ans[1]=2; ans[2]=3; ans[3]=5; ans[4]=7; ans[5]=13; ans[6]=17; ans[7]=19; ans[8]=31; ans[9]=61; ans[10]=89; ans[11]=107; ans[12]=127; ans[13]=521; ans[14]=607; ans[15]=1279; ans[16]=2203; ans[17]=2281; ans[18]=3217; ans[19]=4253; ans[20]=4423; ans[21]=9689; ans[22]=9941; ans[23]=11213; ans[24]=19937; ans[25]=21701; ans[26]=23209; ans[27]=44497; ans[28]=86243; ans[29]=110503; ans[30]=132049; ans[31]=216091; ans[32]=756839; ans[33]=859433; ans[34]=1257787; ans[35]=1398269; ans[36]=2976221; ans[37]=3021377; ans[38]=6972593; // for (int i = 3; i<=31; i++) // { // ll k = (1LL<<i)-1; // cout<<i<<": "<<k<<endl; // int j; // for (j = 2; j<k; j++) // if(k%j==0) break; // if(j==k) cout<<"prime"<<endl; // } cin>>t; while(t--) { cin>>n; cout<<ans[n]<<"\n"; } // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
Timus: 1024. Permutations
/** * H:\Dropbox\Code\Timus\1024. Permutations.cpp * Created on: 2015-03-16-01.56.52, Monday * Verdict: Solved * Author: Enamul Hassan * Concept: At first we have to know some prerequisites like how it is forming a chain or cycle. Lets take the given example in the problem set. |1 2 3 4 5| |4 1 5 2 3| we have: P(1) = 4;P(P(1)) = P(4) = 2 and P(P(P(1))) =P(2) = 1. So, in this cycle the elements are 1 4 2. This cycle has no relation with any other existing cycle in the permutation. Say, P(3) = 5. P(P(3)) = P(5) = 3. Here, another cycle is found which has no relation with the previous cycle. The elements of this cycle are 3 5. In this problem, we have to understand what is EN(n). EN(n) is a function which takes a permutation and gives the same permutation again. If k could be 0, then the answer would always be zero as I am getting the same permutation without any iteration. Here, iteration means every element would walk one step through it cyclic path. If we apply one step on our example, what it would be? It would be: |1 2 3 4 5| |2 4 3 1 5| Here, we have: P(1) = 2;P(P(1)) = P(2) = 4 and P(P(P(1))) =P(4) = 1. So now, cycle elements became 2 4 1 from 1 4 2. Similarly for another cycle it became 5 3 from 3 5. However, in the problem, k should be a positive integer, that means it could not be 0. we have to find the k. k would be an integer which indicates after how many iteration, all the cycles would meet at their own initial states. A cycle having n elements meets its initial state after every n iterations. So, all the cycles would meet at an iteration number where all of them are at their initial states. Definitely, it is nothing but the LCM of the all cycle lengths. The cycle would never overlap, so we could do it having complexity O(n). * Special Thanks to: Rumman Mahmud Mahdi Al Masud. **/ #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define sz 2005 #define pb(a) push_back(a) #define ll long long #define fread freopen("input.txt","r",stdin) #define fwrite freopen("output.txt","w",stdout) using namespace std; int arr[sz]; bool col[sz]; int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM int t, n, m, cas=1,res; _ // clock_t begin, end; // double time_spent; // begin = clock(); cin>>n; for (int i = 1; i<=n; i++) cin>>arr[i]; vector<int>ans; for (int i = 1; i<=n; i++) { if(col[i]) continue; t = 0; m = i; do { col[i] = true; m = arr[m]; t++; }while(m!=i); ans.pb(t); } res = 1; for (int i = 0; i<ans.size(); i++) res = (res/__gcd(res, ans[i])*ans[i]); cout<<res; // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
UVaLive: 5807 - Maximum in the Cycle of 1
/** * H:\Dropbox\Code\UVaLive\5807 - Maximum in the Cycle of 1.cpp * Created on: 2015-03-15-11.29.31, Sunday * Verdict: Solved * Author: Enamul Hassan * Concept: At first we have to know some prerequisites like how it is forming a chain or cycle. Lets take the given example in the problem set. |1 2 3 4 5 6 7 8| |3 2 5 4 1 7 8 6| we have: P(1) = 3;P(P(1)) = P(3) = 5 and P(P(P(1))) =P(5) = 1. So, in this cycle the elements are 1 3 5. This cycle has no relation with any other existing cycle in the permutation. Say, P(6) = 7; P(P(6)) = P(7) = 8 and P(P(P(6))) =P(8) = 6. Here, another cycle is found which has no relation with the previous cycle. The elements of this cycle are 6 7 8. 2 and 4 are in its original position. So, it would loop on itself infinitely! But the other two cycles' elements would be repeated once in every three iterations. Now, lets work with the problem and make it easier and simpler. The main problem is to find a cycle where 1 and k must exist and no element greater than k exists. This problem may solve using derangement mathematics, but I would try to solve using the other way. Now, k=1 is an exceptional case, lets think about k>1. We can make cycles of length 2, 3, 4, ... , k. we could not make length 1, because if we want to bring k in our cycle having 1 already, we have to take at least two elements. if we fix the cycle length, then all other elements can be rearranged among them independently. Say, we fixed the length L, so, rest n - L elements can be rearranged among them independently and it is (n-L)! Another thing would be calculated simultaneously, that is in length L, we can fill the first position with any elements except 1. That means, there are (L-1) possibilities. For the second position, we have (L-2) options. In this way the options would go like (L-3),(L-4),...,3,2,1 which clearly making (L-1)! But there could arise a confusion. How could we calculate the possibilities of second position? From where L-2 came, right? Well, take an example of 3 elements: 1 2 3. If we fix 2 at the first position, then there are 2 options: 2 1 3 and 2 3 1, where the first one is invalid, because 3 is in its own position. If we fix 3 at the first position, then there are 2 options: 3 1 2 and 3 2 1, where the second one is invalid, because 2 is in its own position. So, there are three options for the first position, two and one for the second and third position respectively. You can observe more longer cycles if you are not clear at this point. Now, how many L length cycle is possible? we have to fixed two positions, one is position 1 and another one is position k. we can take other elements in C( (k-2) , (L-2) ) ways. So, for each L where 2<=L<=k, we have to multiply these three things and add it with our solution. That is: Answer+= (n-L)! * (L-1)! * C( (k-2), (L-2) ). The one and only case is k = 1. If we fix 1 at its own position, then in how many ways the rest of the elements can permute independently among them? Yes, it is (n-1)! * Special Thanks to: Rumman Mahmud Mahdi Al Masud. **/ #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define ll long long #define fread freopen("input.txt","r",stdin) #define fwrite freopen("output.txt","w",stdout) using namespace std; unsigned ll ncr[25][25], factorials[25]; bool t_ncr[25][25], t_factorials[25]; unsigned ll nCr(unsigned ll int n,unsigned ll int r) { if(r==1) return n; if(n==r||r==0) return 1; unsigned ll &ret = ncr[n][r]; if(t_ncr[n][r]) return ret; t_ncr[n][r] = true; ret = nCr(n-1,r)+nCr(n-1,r-1); return ret; } unsigned ll fact(unsigned ll n) { if(n==0) return 1LL; unsigned ll &ret = factorials[n]; if(t_factorials[n]) return ret; t_factorials[n]=true; ret=fact(n-1)*n; return ret; } int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM int t, n, m, cas; _ // clock_t begin, end; // double time_spent; // begin = clock(); cin>>t; unsigned ll ans; while(t--) { cin>>cas>>n>>m; ans=0; for (int i = 2; i<=m; i++) { ans+=(fact(n-i)*nCr(m-2,i-2)*fact(i-1)); } if(m==1) ans = fact(n-1); cout<<cas<<" "<<ans<<"\n"; } // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
Subscribe to:
Posts (Atom)