/** * H:\Dropbox\Code\Codeforces\340C.cpp * Created on: 2015-03-14-01.10.35, Saturday * Verdict: Solved * Author: Enamul Hassan * Concept: We would work on sorted data so that the problem becomes easy. So, we have to sort it first. However, Lets think about denominator first. Clearly, there exists n! ways to permute n elements. Now, think about numerator. We can divide it into two sub part. One calculates all distances from 0 and the one calculates the rest differences. Taking n elements, if we fixed the first element, then in how many ways we can permute the rest elements? Surely, (n-1)! So, every element would occur at first position in (n-1)! permutations. That means, the result of the first part would be: Sum1 = ((n-1)! * a1+(n-1)! * a2+...+(n-1)! * an), as |ai - 0| = ai Sum1 = (n-1)! * (a1+a2+...+an) Sum1 = (n-1)! * (sum of all elements) Lets think about the second part of the numerator. We have to calculate the sum of all |ai-aj| in all permutations where i and j ranges 1 to n and ai and aj are adjacent in the permutation. Now, lets fixed the position of aj at k. So, the position of aj is fixed at k+1. rest of the n-2 elements can be permuted in (n-2)! ways. At how many positions we can fixed aj? in other word, what are the possible values of k? definitely 1 to n - 1. That means, Sum2 = |ai-aj| * (n-1) * (n-2)! Sum2 = |ai-aj| * (n-1)! If we sum these two and write with denominator, then it would be: Answer = (Sum1+Sum2)/n! Answer = ((n-1)! * (sum of all elements) + |ai-aj| * (n-1)!)/n! Answer = (n-1)! * ((sum of all elements) + |ai-aj|)/(n * (n-1)!) Answer = ((sum of all elements) + |ai-aj|)/n The only remaining part is to calculate the sum of differences of all possible pairs which is not an easy task for 10^5 elements. A brute force approach would take 10^10 operations which would cause Time Limit. We can do it by counting how many times a value is added and how many time it is deducted. In term |ai - aj|, ai is added and aj is deducted. For the i-th value, it would be added in i-1 term and deducted in n-i. Say, a sequence a1 a2 a3 ... a(i-1) ai a(i+1)... an Paring with the values smaller than ai, it would remain as added value as |ai - ak| where k ranges 1 to i-1. Similarly, for the values greater than ai, it would remain as deducted value as |ak - ai| where k ranges i+1 to n. We have to multiply this result by two, because, a pair would occur twice. One time |ai - aj| and other time |aj - ai|. At last we have to divide both numerator and denominator by their GCD. * Special Thanks to: --Denis Distrugatorul De Pizde (http://codeforces.com/profile/Kira69) --Rumman Mahmud Mahdi Al Masud **/ #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define all(a) a.begin(),a.end() #define ll long long #define fread freopen("input.txt","r",stdin) #define fwrite freopen("output.txt","w",stdout) using namespace std; ll sum,n; int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM _ // clock_t begin, end; // double time_spent; // begin = clock(); cin>>n; vector<ll>v(n); for (int i = 0; i<n; i++) cin>>v[i]; sort(all(v)); for (int i = 0; i<n; i++) { /** * Lets i-th element = a * for the first sub part, a should be added in sum. * for the second sub part add portion, 2*a*i should be added. * for the second sub part deduct portion, 2*a*(n-i-1) should be deducted. * So, total added in sum = a + 2ai- 2a(n-i-1) * = a + 2ai- 2an + 2ai + 2a * = a(1 + 2i - 2n + 2i + 2) * = a(4i - 2n + 3) */ sum+=((i<<2)-(n<<1)+3LL)*v[i]; } ll gcd = __gcd(sum,n); sum/=gcd; n/=gcd; cout<<sum<<" "<<n; // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
Saturday, March 14, 2015
Codeforces: 340C - Tourist Problem
Thursday, March 12, 2015
UVa: 12461 - Airplane
/** * H:\Dropbox\Code\UVa\Accepted\12461 - Airplane.cpp * Created on: 2015-03-12-19.22.42, Thursday * Verdict: Solved * Author: Enamul Hassan **/ #include<stdio.h> int main(){ int n; while(~scanf("%d", &n)&&n){printf("1/2\n");} return 0; }
Friday, March 6, 2015
Codechef: IITK2P05 Factorization
/** * H:\Dropbox\Code\CodeChef\Practice\IITK2P05 Factorization.cpp * Created on: 2015-03-06-01.40.58, Friday * Verdict: Solved * Author: Enamul Hassan * Problem Link: http://www.codechef.com/problems/IITK2P05 * Concept: This is a very interesting number theory problem. Lets think the problem if n ranges to 10^12. What would we do? we would generate all the primes up to 10^6 and would apply them on n. at last if n>1 then that value would be added in answer. Before going to the original constraint, we have to know some basic number theory formulas. They are: ---phi( n * m) = phi(n) * phi(m) ---phi( n ) = n * ( 1 - (1/p1) )* ( 1 - (1/p2) ) * ... * ( 1 - (1/pk) ) ---phi( n ) = ( p1^(e1-1) )* ( p2^(e2-1) ) * ... * ( pk^(ek-1) ) *( p1 - 1) *(p2-1)* ... *(pk-1) where pi is i-th prime factor of n and ei is the corresponding power of that prime factor. Another thing is to know that, phi(x) = x - 1 satisfies only when x is prime. Now, lets face the main problem. At first, we have to find all prime factors of n less than 10^6. The corresponding phi calculation should be deducted from m. How the corresponding phi would be deducted from m? 3rd formula would help. For a prime factor pi, we know its corresponding power in n which is ei. So, the new m would be m/(( pi^(ei-1) ) * (pi - 1 )). Now, only primes greater than 10^6 are remaining in n. This part of the calculation would be needed if n remains greater than one after the above calculation. It is guaranteed that there could exists at most two primes. Because, if any number below or equal to 10^18 have more than two prime factor, one of them must remain in range 10^6. Because, 10^6 *10^6 * 10^6 = 10^18. There are 3 possibilities which would be described below: 1. n could be a prime if n = m + 1. So, n itself a prime, no calculation needed. 2. n could be square number of a prime. In this case phi would be (p-1) * (p-1). Because, prime number p has phi, m = p - 1 and phi(p * p) = (p-1) * (p - 1). 3. n could be the resultant of two different primes multiplication. suppose, these two primes are a and b. So, a * b = n ............................(1) and m = (a - 1) * (b - 1) m = a*b - a - b + 1 m = n - (a + b) + 1 a + b = n - m + 1 ....................(2) We know, (a - b)^2 = (a + b)^2 - 4 * a * b a - b = square_root( (n - m + 1)^2 - 4 * n ) .......(3) (2) - (3) => b = ( (n - m + 1) - square_root( (n - m + 1)^2 - 4 * n ) )/2 From (1), a = n/b * Special thanks to: Sudipta Chandra Dipu and Kazi Nayeem **/ #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define pb(a) push_back(a) #define all(a) a.begin(),a.end() #define ll long long #define fread freopen("input.txt","r",stdin) #define fwrite freopen("output.txt","w",stdout) using namespace std; ll n, m,t; vector<ll>ans; #define sz 1000010 ll col[sz/64+10]; int prime[78499+10], cnt; void seive()//1 indexed { long long i,j,k; for(i=3;i<sz;i+=2) if(!(col[i/64]&(1LL<<(i%64)))) for(j=i*i;j<sz;j+=2*i) col[j/64]|=(1LL<<(j%64)); prime[cnt++]=2; for (int i = 3; i<sz; i+=2) if(!(col[i/64]&(1LL<<(i%64)))) prime[cnt++] = i; } int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM _ // clock_t begin, end; // double time_spent; // begin = clock(); seive(); // cout<<cnt<<endl; cin>>t; while(t--) { cin>>n>>m; ans.clear(); for (int i = 0;i<cnt&& prime[i]*prime[i]<=n; i++) { if(n%prime[i]==0) { ll cn=1; n/=prime[i]; ans.pb(prime[i]); while(n%prime[i]==0) { n/=prime[i]; cn*=prime[i]; ans.pb(prime[i]); } m = m/(cn*(prime[i]-1)); } } if(n>1) { if(n==m+1) ans.pb(n); else if((n-m)*(n-m)==n) { ans.pb(n-m); ans.pb(n-m); } else { long double x = n-m+1; m= x-sqrtl((x*x)-(n<<2LL)); m>>=1; ans.pb(m); ans.pb(n/m); } } // sort(all(ans)); m = ans.size(); for (int i = 0; i<m; i++) cout<<ans[i]<<" \n"[i==m-1]; } // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
Thursday, March 5, 2015
Codechef: IITK2P10 Chef and Pattern
/** * H:\Dropbox\Code\CodeChef\Practice\IITK2P10 Chef and Pattern.cpp * Created on: 2015-03-04-21.38.54, Wednesday * Verdict: Solved * Author: Enamul Hassan * Problem Link: http://www.codechef.com/problems/IITK2P10 * Comment: The series would be: 1 K K K^2 K^4 K^8 K^16 K^32... 1 K K^2^0 K^2^1 K^2^2 K^2^3 K^2^4 K^2^5... For n=1, result is 1 and for n = 2, the result is K. For any other positive value of n, the result would be: K^2^(n-3) We know, if we have to modulo a number and its power is as huge as we have to modulo the power, then the power should modulo by the phi of the mod number. Here, the mod number is a prime and phi of any prime number is equal to one less than the prime number. So, (K^2^(n-3))%mod = K^((2^(n-3))%phi(mod))%mod **/ #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) #define mod 1000000007 ll bigmod(ll sonkha,ll ghat,ll vag_const) { ll vag_shesh=1; while(ghat>0) { if(ghat%2==1) { vag_shesh=(vag_shesh*sonkha)%vag_const; } ghat/=2; sonkha=(sonkha*sonkha)%vag_const; } return vag_shesh; } using namespace std; ll t, n, k, ans; int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM _ // clock_t begin, end; // double time_spent; // begin = clock(); cin>>t; while(t--) { cin>>k>>n; if(n<=2) { if(n==1) cout<<1<<"\n"; else cout<<k<<"\n"; continue; } ans=bigmod(k,bigmod(2,n-3,mod-1),mod); cout<<ans<<"\n"; } // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
Codechef: KGP14B Sequence Containment
/** * H:\Dropbox\Code\CodeChef\Practice\KGP14B Sequence Containment.cpp * Created on: 2015-03-05-03.55.48, Thursday * Verdict: Solved * Author: Enamul Hassan * Problem Link: http://www.codechef.com/problems/KGP14B * Concept: Lets the length of two strings are |X| and |Y|. If we merge the string X and Y, then we would get a string having length |X|+|Y|. To make this string ot Z, we could subtract the Longest Common Sequence from |X|+|Y|. Because, these letters are double counted in |X|+|Y|. So, |Z| = |X| + |Y| - LCS(X,Y). **/ #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define sz 1005 #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; int mag[sz][sz]; int LCS(string &X, string &Y) { int m = X.size(), n = Y.size(); for (int i = 1;i<=m ; i++) for (int j = 1; j<=n; j++) { if(X[i-1]==Y[j-1]) { mag[i][j] = mag[i-1][j-1]+1; } else if(mag[i-1][j]>=mag[i][j-1]) { mag[i][j] = mag[i-1][j]; } else { mag[i][j] = mag[i][j-1]; } } return mag[m][n]; } int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM int t, n, m, cas=1; _ // clock_t begin, end; // double time_spent; // begin = clock(); string a,b; cin>>t; while(t--) { clr(mag,0); cin>>m>>n>>a>>b; cout<<"Case "<<cas++<<": "<<(m+n-LCS(a,b))<<"\n"; } // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
Codechef: KGP14A Drawing Contest
/** * H:\Dropbox\Code\CodeChef\Practice\KGP14A Drawing Contest.cpp * Created on: 2015-03-05-03.35.16, Thursday * Verdict: Solved * Author: Enamul Hassan * Problem link: http://www.codechef.com/problems/KGP14A * Concept: Sorting both height of kids and length of pencils array, we would take the sum of all absolute differences between hi and li where i = 1,2,...,n. Because, every kids have to assign a pencil and the number of kids and the number pencils are same. This would be the optimal, because if we don't take the ith pencil for ith kids after sorting then absolute differences would be increase, because it would be taken by the jth kids having larger absolute difference. **/ #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define sz 200005 #define pb(a) push_back(a) #define all(a) a.begin(),a.end() #define ll long long #define fread freopen("input.txt","r",stdin) #define fwrite freopen("output.txt","w",stdout) using namespace std; vector<ll>v,vv; int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM _ // clock_t begin, end; // double time_spent; // begin = clock(); ll t, n, m, ans,cas=1; cin>>t; while(t--) { v.clear(); vv.clear(); ans = 0; cin>>n; for (int i = 0; i<n; i++) { cin>>m; v.pb(m); } for (int i = 0; i<n; i++) { cin>>m; vv.pb(m); } sort(all(v)); sort(all(vv)); for (int i = 0; i<n; i++) ans+=abs(v[i]-vv[i]); cout<<"Case "<<cas++<<": "<<ans<<"\n"; } // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
Codechef: IITK2P04 DOTS Player
/** * H:\Dropbox\Code\CodeChef\Practice\IITK2P04 DOTS Player.cpp * Created on: 2015-03-04-22.04.49, Wednesday * Verdict: Solved * Author: Enamul Hassan * Problem link: http://www.codechef.com/problems/IITK2P04 * Concept: At first, lets think the problem if n and m both ranges from 1 to 100 instead of 1 to 1000. For every cell (i,j), a dfs would find the farthest node of this color and another dfs from that farthest node would find the maximum point from the current node. A global maximum variable can be updated each time. If we get any cycle, then global maximum would be compared with the number of items of this color. But here, it would cross the stack limit if this approach is used on the original constraint. So, the same thing should be implement using bfs instead of dfs. **/ #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define sz 1005 #define fread freopen("input.txt","r",stdin) #define fwrite freopen("output.txt","w",stdout) using namespace std; int rr[] = {0,0,1,-1}; int cc[] = {1,-1,0,0}; int conv[] = {1,0,3,2}; int t, n, m, arr[sz][sz], coll,res,cas=1,visited[sz][sz]; map<int ,int>mpp; queue< pair<pair<int ,int>,pair<int,int> > >st; void bfs(int x, int y,int ex) { while(!st.empty()) st.pop(); st.push({{x,y},{1,-1}}); int now, level,u,v,fx,fy,mxlvl=-1; cas++; while(!st.empty()) { x = st.front().first.first; y = st.front().first.second; visited[x][y] = cas; level = st.front().second.first; now = st.front().second.second; st.pop(); if(level>mxlvl) { mxlvl = level; fx = x; fy = y; } for (int i = 0; i<4; i++) { if(now==i) continue; u = x+rr[i]; v = y+cc[i]; if(u<0||v<0||u>=n||v>=m||arr[u][v]!=coll) continue; if(visited[u][v]==cas) { res = max(res,mpp[coll]); return; } visited[u][v] = cas; st.push({{u,v},{level+1,conv[i]}}); } } if(ex) bfs(fx,fy,0); res = max(res,mxlvl); } int main() { #ifdef ENAM // fread; // fwrite; #endif // ENAM _ // clock_t begin, end; // double time_spent; // begin = clock(); cin>>n>>m; for (int i = 0; i<n; i++) for (int j = 0; j<m; j++) { cin>>arr[i][j]; mpp[ arr[i][j] ]++; } for (int i = 0; i<n; i++) for (int j = 0; j<m; j++) { coll = arr[i][j]; if(!visited[i][j]) bfs(i,j,1); } if(res==1) res = 0; cout<<res<<"\n"; // end = clock(); // time_spent = (double)(end - begin) / CLOCKS_PER_SEC; // cerr<<"Time spent = "<<time_spent<<endl; return 0; }
Subscribe to:
Posts (Atom)