1111.md (9390B)
1 Source: https://codeforces.com/blog/entry/64989 2 3 Tutorial is loading... 4 5 **Author's code** 6 7 ``` 8 #include "bits/stdc++.h" 9 using namespace std; 10 11 // Checking if a character is vowel 12 bool isVowel(char a) 13 { 14 if(a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u') 15 return true; 16 return false; 17 } 18 19 int main() 20 { 21 string S, T; 22 cin >> S; 23 cin >> T; 24 // Answer is no if size of strings is differents 25 if(S.size() != T.size()) 26 { 27 cout << "No\n"; 28 return 0; 29 } 30 int flag = 1; 31 // Checking the condition on all characters one by one 32 for(int i = 0; i < S.size(); ++i) 33 { 34 if((isVowel(S[i]) && isVowel(T[i])) || (isVowel(S[i]) == false && isVowel(T[i]) == false)) 35 { 36 continue; 37 } 38 flag = 0; 39 break; 40 } 41 if(flag) 42 cout << "Yes\n"; 43 else 44 cout << "No\n"; 45 return 0; 46 } 47 ``` 48 49 Tutorial is loading... 50 51 **Author's code** 52 53 ``` 54 #include <bits/stdc++.h> 55 using namespace std; 56 const long long N = 100010; 57 58 long long a[N]; 59 60 int main() 61 { 62 long long n, k, m, i, sum=0, tp; 63 long double mx; 64 cin>>n>>k>>m; 65 for(int i=1;i<=n;i++) 66 { 67 cin>>a[i]; 68 sum += a[i]; 69 } 70 // Sorting the array 71 sort(a+1, a+n+1); 72 // Checking for the case where none of the avengers is removed 73 mx = (long double)(sum+min(m, n*k))/(long double)(n); 74 75 for(int i=1;i<=min(n-1, m);i++) 76 { 77 sum -= a[i]; 78 tp = sum + min(m-i, (n-i)*k); 79 mx = max(mx, (long double)(tp)/(long double)(n-i)); 80 } 81 cout<<fixed<<setprecision(20)<<mx<<endl; 82 return 0; 83 } 84 ``` 85 86 Tutorial is loading... 87 88 **Author's code** 89 90 ``` 91 #include <bits/stdc++.h> 92 using namespace std; 93 94 vector<long long> avengers; 95 long long n,k,A,B; 96 97 // rec(l,r) returns minimum power needed to destroy l to r (inclusive) 98 long long rec(long long l, long long r) 99 { 100 long long i=lower_bound(avengers.begin(),avengers.end(),l)-avengers.begin(); 101 long long j=upper_bound(avengers.begin(),avengers.end(),r)-avengers.begin(); 102 j--; 103 // calculating positions of l and r in avengers array to calculate x 104 long long x=j-i+1; 105 long long power_consumed; 106 // if there is no avenger in that subarray 107 if(x==0) 108 power_consumed=A; 109 else 110 { 111 power_consumed=B*x*(r-l+1); 112 // power consumed for operation 2. (r-l+1 is length of subarray) 113 } 114 // if l is equal to r or if there is no avenger in the subarray, then do not go into recursion further 115 if(l==r || x==0) 116 return power_consumed; 117 long long mid=(l+r)/2; 118 // taking minimum of two operations. 119 long long minPower=min(power_consumed, rec(l,mid)+rec(mid+1,r)); 120 return minPower; 121 } 122 123 int main() 124 { 125 ios_base::sync_with_stdio(false); 126 cin.tie(NULL); 127 cout.tie(NULL); 128 cin>>n>>k>>A>>B; 129 int i; 130 for(i=0;i<k;i++) 131 { 132 int val; 133 cin>>val; 134 avengers.push_back(val); 135 } 136 sort(avengers.begin(),avengers.end()); 137 long long x = (long long)1<<n; 138 cout<<rec(1,x)<<endl; 139 return 0; 140 } 141 ``` 142 143 Tutorial is loading... 144 145 **Author's code** 146 147 ``` 148 #include<bits/stdc++.h> 149 using namespace std; 150 #define pb push_back 151 #define fr(i,n) for(i=0;i<n;i++) 152 #define rep(i,st,en) for(i=st;i<=en;i++) 153 154 typedef long long ll; 155 typedef pair<int,int> pii; 156 const int N = 100010; 157 ll mod = 1e9+7; 158 ll fmod(ll b,ll exp){ 159 ll res =1; 160 while(exp){if(exp&1ll)res=(res*b)%mod; 161 b =(b*b)%mod;exp/=2ll; 162 } 163 return res; 164 } 165 166 ll buc[101]; 167 ll fac[N],inv[N]; 168 ll dp[N],temp_dp[N]; 169 ll ans[55][55]; 170 string s,s1,s2; 171 172 int find(char c) 173 { 174 if(c>='A' && c<='Z')return (int)(c-'A'+26); 175 else return (c-'a'); 176 } 177 178 inline void add(ll &a,ll b) 179 { 180 a+=b; 181 if(a>=mod)a-=mod; 182 } 183 inline void sub(ll &a,ll b) 184 { 185 a-=b; 186 if(a<0)a+=mod; 187 } 188 int main() 189 { 190 //freopen("input.txt", "r", stdin); 191 //freopen("output.txt", "w", stdout); 192 ios_base::sync_with_stdio(false);cin.tie(NULL); 193 int t=1,n,i,j,m,q; 194 cin>>s; 195 n = s.length(); 196 //Store the frequencies in buc 197 for(int i=0;i<n;i++)buc[find(s[i])]++; 198 199 //Compte factorial and inverse factorials modulo mod 200 fac[0]=1; 201 rep(i,1,n)fac[i]=(fac[i-1]*1ll*i)%mod; 202 inv[n] = fmod(fac[n],mod-2); 203 for(int i=n-1;i>=0;i--)inv[i]=(inv[i+1]*1ll*(i+1))%mod; 204 205 //Compute n/2! * n/2! divided by factorials of frequencies of all 206 ll num = (fac[n/2]*fac[n/2])%mod; 207 for(int i=0;i<52;i++)num = (num*inv[buc[i]])%mod; 208 209 //DP for subset sum 210 dp[0]=1; 211 for(int i=0;i<52;i++) 212 { 213 if(!buc[i])continue; 214 for(int j=n;j>=buc[i];j--) 215 add(dp[j],dp[j-buc[i]]); 216 } 217 fr(i,52)ans[i][i]=dp[n/2]; 218 219 fr(i,52) 220 { 221 if(!buc[i])continue; 222 //Temporrily store dp using all characters in an array 223 for(int k=0;k<=n;k++) 224 temp_dp[k]= dp[k]; 225 226 //Remove all ways consisting of the ith character from temp array 227 for(int k=buc[i];k<=n;k++) 228 sub(temp_dp[k],temp_dp[k-buc[i]]); 229 230 231 for(int j=i+1;j<52;j++) 232 { 233 if(!buc[j])continue; 234 //Now remove the jth character from the temp 235 for(int k=buc[j];k<=n;k++) 236 sub(temp_dp[k],temp_dp[k-buc[j]]); 237 238 // Answer will be twice since ith and jth can be in 1st or 2nd half 239 ans[i][j]= (2ll*temp_dp[n/2])%mod; 240 ans[j][i]= ans[i][j]; //Symmetric 241 242 //Restore condition by adding ways using jth to reset temp to without i 243 for(int k=n;k>=buc[j];k--) 244 add(temp_dp[k],temp_dp[k-buc[j]]); 245 } 246 } 247 cin>>q; 248 int x,y; 249 while(q--) 250 { 251 cin>>x>>y; 252 int l = find(s[x-1]); 253 int r = find(s[y-1]); 254 //Use precomputed num and ans, for all queries 255 cout<<(num*ans[l][r])%mod<<"\n"; 256 } 257 258 return 0; 259 } 260 ``` 261 262 Tutorial is loading... 263 264 **Author's code** 265 266 ``` 267 #include<bits/stdc++.h> 268 using namespace std; 269 #define pb push_back 270 #define rep(i,st,en) for(i=st;i<=en;i++) 271 272 typedef long long ll; 273 typedef pair<int,int> pii; 274 const int N = 200010; 275 const int LN = 20; 276 ll mod = 1e9+7; 277 ll fmod(ll b,ll exp){ 278 ll res =1; 279 while(exp){if(exp&1ll)res=(res*b)%mod; 280 b =(b*b)%mod;exp/=2ll; 281 } 282 return res; 283 } 284 285 int ver[2*N]; // gives the id of the vertex in the euler array 286 ll bit[2*N]; 287 int st[N],en[N],A[N]; // st and en are the start and end time of node i 288 int f[N]; 289 ll dp[N]; 290 int par[N][LN]; 291 int mark[N],lev[N]; 292 293 vector<int> adj[N]; 294 295 int tim = 0,n; 296 297 /* Normal DFS and LCA functions */ 298 void dfs(int i,int p=-1) 299 { 300 301 if (p+1) 302 { 303 lev[i]=lev[p]+1; 304 par[i][0]=p; 305 for(int j=1;j<LN;j++) 306 if (par[i][j-1]+1) 307 par[i][j]=par[par[i][j-1]][j-1]; 308 } 309 st[i]=(++tim); 310 ver[tim]= i; 311 for(auto ve:adj[i]) 312 if(p-ve) 313 dfs(ve,i); 314 en[i]=(++tim); 315 ver[tim]= i; 316 } 317 318 int lca(int u,int v) 319 { 320 if (lev[u]<lev[v]) 321 swap(u,v); 322 for(int j=LN-1;j>=0;j--) 323 if (par[u][j]+1 && lev[par[u][j]]>=lev[v]) 324 u=par[u][j]; 325 if (u==v) 326 return u; 327 for(int j=LN-1;j>=0;j--) 328 { 329 if (par[u][j]+1 && par[u][j]!=par[v][j]) 330 { 331 u=par[u][j]; 332 v=par[v][j]; 333 } 334 } 335 return par[u][0]; 336 } 337 338 /* Helper functions */ 339 inline ll add(ll a,ll b) 340 { 341 a+=b; 342 if(a>=mod)a-=mod; 343 return a; 344 } 345 void upd(int ind,int val) 346 { 347 for(int i=ind;i<=2*n;i+=(i&-i)) 348 bit[i]+=val; 349 } 350 351 ll query(int ind) 352 { 353 ll res = 0; 354 for(int i=ind;i>0;i-=(i&-i)) 355 res+=bit[i]; 356 return res; // returns the number of marked nodes from 1 to ind inclusive. 357 } 358 359 int main() 360 { 361 //freopen("input.txt", "r", stdin); 362 //freopen("output.txt", "w", stdout); 363 ios_base::sync_with_stdio(false);cin.tie(NULL); 364 int t=1,i,j,m,q,u,v,w,typ,e,k,x; 365 memset(par,-1,sizeof(par)); 366 cin>>n>>q; 367 rep(i,1,n-1) 368 { 369 cin>>u>>v; 370 adj[u].pb(v); 371 adj[v].pb(u); 372 } 373 dfs(1,-1); 374 int root; 375 while(q--) 376 { 377 cin>>k>>x>>root; 378 379 rep(i,1,k){ 380 cin>>A[i]; 381 mark[A[i]]=1; //mark nodes given in the set 382 upd(st[A[i]],1); // range update by updating at start and end time in bit 383 upd(en[A[i]]+1,-1); 384 } 385 int ans_root = query(st[root]); 386 rep(i,1,k){ 387 int lp = lca(A[i],root); 388 //query function is inclusive, hence subtract 1 to remove current node from answer 389 f[i]= query(st[A[i]])+ans_root-2*query(st[lp])+(mark[lp]==1)-1; 390 } 391 //Sorting level-wise using f[i] values 392 sort(f+1,f+k+1); 393 rep(i,1,k){ 394 upd(st[A[i]],-1); // reverse the updates to nullify effect 395 upd(en[A[i]]+1,1); 396 mark[A[i]]=0; // unmark nodes in the set 397 } 398 rep(i,0,x)dp[i]=0; 399 dp[0]=1; 400 //If number of groups less than maximum height no way possible 401 int fl = 0; 402 rep(i,1,k)if(f[i]>=x)fl=1; 403 if(fl)cout<<"0\n"; 404 else{ 405 dp[0]=1; 406 //For every value of f[i], update dp. Note loop for j will be reverse. 407 rep(i,1,k){ 408 for(int j=min(i,x);j>=0;j--) 409 { 410 if(j<=f[i])dp[j]=0; //no way possible since less than height 411 else dp[j]= add(((dp[j]*1ll*(j-f[i]))%mod),dp[j-1]); 412 } 413 } 414 ll ans = 0; 415 // AT MOST x in the question 416 rep(i,1,x){ 417 ans = add(ans,dp[i]); 418 } 419 cout<<ans<<"\n"; 420 } 421 } 422 return 0; 423 } 424 ```