codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```