Tutorial is loading...
Author's code
#include "bits/stdc++.h"
using namespace std;
// Checking if a character is vowel
bool isVowel(char a)
{
if(a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
return true;
return false;
}
int main()
{
string S, T;
cin >> S;
cin >> T;
// Answer is no if size of strings is differents
if(S.size() != T.size())
{
cout << "No\n";
return 0;
}
int flag = 1;
// Checking the condition on all characters one by one
for(int i = 0; i < S.size(); ++i)
{
if((isVowel(S[i]) && isVowel(T[i])) || (isVowel(S[i]) == false && isVowel(T[i]) == false))
{
continue;
}
flag = 0;
break;
}
if(flag)
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
Tutorial is loading...
Author's code
#include <bits/stdc++.h>
using namespace std;
const long long N = 100010;
long long a[N];
int main()
{
long long n, k, m, i, sum=0, tp;
long double mx;
cin>>n>>k>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum += a[i];
}
// Sorting the array
sort(a+1, a+n+1);
// Checking for the case where none of the avengers is removed
mx = (long double)(sum+min(m, n*k))/(long double)(n);
for(int i=1;i<=min(n-1, m);i++)
{
sum -= a[i];
tp = sum + min(m-i, (n-i)*k);
mx = max(mx, (long double)(tp)/(long double)(n-i));
}
cout<<fixed<<setprecision(20)<<mx<<endl;
return 0;
}
Tutorial is loading...
Author's code
#include <bits/stdc++.h>
using namespace std;
vector<long long> avengers;
long long n,k,A,B;
// rec(l,r) returns minimum power needed to destroy l to r (inclusive)
long long rec(long long l, long long r)
{
long long i=lower_bound(avengers.begin(),avengers.end(),l)-avengers.begin();
long long j=upper_bound(avengers.begin(),avengers.end(),r)-avengers.begin();
j--;
// calculating positions of l and r in avengers array to calculate x
long long x=j-i+1;
long long power_consumed;
// if there is no avenger in that subarray
if(x==0)
power_consumed=A;
else
{
power_consumed=B*x*(r-l+1);
// power consumed for operation 2. (r-l+1 is length of subarray)
}
// if l is equal to r or if there is no avenger in the subarray, then do not go into recursion further
if(l==r || x==0)
return power_consumed;
long long mid=(l+r)/2;
// taking minimum of two operations.
long long minPower=min(power_consumed, rec(l,mid)+rec(mid+1,r));
return minPower;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>k>>A>>B;
int i;
for(i=0;i<k;i++)
{
int val;
cin>>val;
avengers.push_back(val);
}
sort(avengers.begin(),avengers.end());
long long x = (long long)1<<n;
cout<<rec(1,x)<<endl;
return 0;
}
Tutorial is loading...
Author's code
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr(i,n) for(i=0;i<n;i++)
#define rep(i,st,en) for(i=st;i<=en;i++)
typedef long long ll;
typedef pair<int,int> pii;
const int N = 100010;
ll mod = 1e9+7;
ll fmod(ll b,ll exp){
ll res =1;
while(exp){if(exp&1ll)res=(res*b)%mod;
b =(b*b)%mod;exp/=2ll;
}
return res;
}
ll buc[101];
ll fac[N],inv[N];
ll dp[N],temp_dp[N];
ll ans[55][55];
string s,s1,s2;
int find(char c)
{
if(c>='A' && c<='Z')return (int)(c-'A'+26);
else return (c-'a');
}
inline void add(ll &a,ll b)
{
a+=b;
if(a>=mod)a-=mod;
}
inline void sub(ll &a,ll b)
{
a-=b;
if(a<0)a+=mod;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(false);cin.tie(NULL);
int t=1,n,i,j,m,q;
cin>>s;
n = s.length();
//Store the frequencies in buc
for(int i=0;i<n;i++)buc[find(s[i])]++;
//Compte factorial and inverse factorials modulo mod
fac[0]=1;
rep(i,1,n)fac[i]=(fac[i-1]*1ll*i)%mod;
inv[n] = fmod(fac[n],mod-2);
for(int i=n-1;i>=0;i--)inv[i]=(inv[i+1]*1ll*(i+1))%mod;
//Compute n/2! * n/2! divided by factorials of frequencies of all
ll num = (fac[n/2]*fac[n/2])%mod;
for(int i=0;i<52;i++)num = (num*inv[buc[i]])%mod;
//DP for subset sum
dp[0]=1;
for(int i=0;i<52;i++)
{
if(!buc[i])continue;
for(int j=n;j>=buc[i];j--)
add(dp[j],dp[j-buc[i]]);
}
fr(i,52)ans[i][i]=dp[n/2];
fr(i,52)
{
if(!buc[i])continue;
//Temporrily store dp using all characters in an array
for(int k=0;k<=n;k++)
temp_dp[k]= dp[k];
//Remove all ways consisting of the ith character from temp array
for(int k=buc[i];k<=n;k++)
sub(temp_dp[k],temp_dp[k-buc[i]]);
for(int j=i+1;j<52;j++)
{
if(!buc[j])continue;
//Now remove the jth character from the temp
for(int k=buc[j];k<=n;k++)
sub(temp_dp[k],temp_dp[k-buc[j]]);
// Answer will be twice since ith and jth can be in 1st or 2nd half
ans[i][j]= (2ll*temp_dp[n/2])%mod;
ans[j][i]= ans[i][j]; //Symmetric
//Restore condition by adding ways using jth to reset temp to without i
for(int k=n;k>=buc[j];k--)
add(temp_dp[k],temp_dp[k-buc[j]]);
}
}
cin>>q;
int x,y;
while(q--)
{
cin>>x>>y;
int l = find(s[x-1]);
int r = find(s[y-1]);
//Use precomputed num and ans, for all queries
cout<<(num*ans[l][r])%mod<<"\n";
}
return 0;
}
Tutorial is loading...
Author's code
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,st,en) for(i=st;i<=en;i++)
typedef long long ll;
typedef pair<int,int> pii;
const int N = 200010;
const int LN = 20;
ll mod = 1e9+7;
ll fmod(ll b,ll exp){
ll res =1;
while(exp){if(exp&1ll)res=(res*b)%mod;
b =(b*b)%mod;exp/=2ll;
}
return res;
}
int ver[2*N]; // gives the id of the vertex in the euler array
ll bit[2*N];
int st[N],en[N],A[N]; // st and en are the start and end time of node i
int f[N];
ll dp[N];
int par[N][LN];
int mark[N],lev[N];
vector<int> adj[N];
int tim = 0,n;
/* Normal DFS and LCA functions */
void dfs(int i,int p=-1)
{
if (p+1)
{
lev[i]=lev[p]+1;
par[i][0]=p;
for(int j=1;j<LN;j++)
if (par[i][j-1]+1)
par[i][j]=par[par[i][j-1]][j-1];
}
st[i]=(++tim);
ver[tim]= i;
for(auto ve:adj[i])
if(p-ve)
dfs(ve,i);
en[i]=(++tim);
ver[tim]= i;
}
int lca(int u,int v)
{
if (lev[u]<lev[v])
swap(u,v);
for(int j=LN-1;j>=0;j--)
if (par[u][j]+1 && lev[par[u][j]]>=lev[v])
u=par[u][j];
if (u==v)
return u;
for(int j=LN-1;j>=0;j--)
{
if (par[u][j]+1 && par[u][j]!=par[v][j])
{
u=par[u][j];
v=par[v][j];
}
}
return par[u][0];
}
/* Helper functions */
inline ll add(ll a,ll b)
{
a+=b;
if(a>=mod)a-=mod;
return a;
}
void upd(int ind,int val)
{
for(int i=ind;i<=2*n;i+=(i&-i))
bit[i]+=val;
}
ll query(int ind)
{
ll res = 0;
for(int i=ind;i>0;i-=(i&-i))
res+=bit[i];
return res; // returns the number of marked nodes from 1 to ind inclusive.
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(false);cin.tie(NULL);
int t=1,i,j,m,q,u,v,w,typ,e,k,x;
memset(par,-1,sizeof(par));
cin>>n>>q;
rep(i,1,n-1)
{
cin>>u>>v;
adj[u].pb(v);
adj[v].pb(u);
}
dfs(1,-1);
int root;
while(q--)
{
cin>>k>>x>>root;
rep(i,1,k){
cin>>A[i];
mark[A[i]]=1; //mark nodes given in the set
upd(st[A[i]],1); // range update by updating at start and end time in bit
upd(en[A[i]]+1,-1);
}
int ans_root = query(st[root]);
rep(i,1,k){
int lp = lca(A[i],root);
//query function is inclusive, hence subtract 1 to remove current node from answer
f[i]= query(st[A[i]])+ans_root-2*query(st[lp])+(mark[lp]==1)-1;
}
//Sorting level-wise using f[i] values
sort(f+1,f+k+1);
rep(i,1,k){
upd(st[A[i]],-1); // reverse the updates to nullify effect
upd(en[A[i]]+1,1);
mark[A[i]]=0; // unmark nodes in the set
}
rep(i,0,x)dp[i]=0;
dp[0]=1;
//If number of groups less than maximum height no way possible
int fl = 0;
rep(i,1,k)if(f[i]>=x)fl=1;
if(fl)cout<<"0\n";
else{
dp[0]=1;
//For every value of f[i], update dp. Note loop for j will be reverse.
rep(i,1,k){
for(int j=min(i,x);j>=0;j--)
{
if(j<=f[i])dp[j]=0; //no way possible since less than height
else dp[j]= add(((dp[j]*1ll*(j-f[i]))%mod),dp[j-1]);
}
}
ll ans = 0;
// AT MOST x in the question
rep(i,1,x){
ans = add(ans,dp[i]);
}
cout<<ans<<"\n";
}
}
return 0;
}
Can you use Latex or whatever it is called for D and E also
You should have made a div1+div2 round with these div2 D/E as div1 D/E
Hi can someone explain why this dp soln for C is wrong. Link 49433152 I have taken the dp state as the length of the segment and the no. of avengers in the segment. The code is obviously redundant but I am still confused that why is it not working.
Hi, some avengers are possiblely in the same position so this code
upper_bound(pos.begin(), pos.end(), b)
will return a wrong result. I think this is the preblem of your solution.Oh, I am very sorry but what I have just said is WRONG and there are no problem with that code, please forget it >_<
Please excuse my poor English.
I think the real problem is that your state don't have all information in a segment. Just think a situation, A = 1 and B = 1000. There are two segments [1, 2] and [3, 4], and for each one there are two avengers inside. These 4 avengers are in postions 1 1 3 4.
It's obviously that the answer of first segment is 2001 and the answer of the second one is 2000. But your state will think they are same. So you have a wrong state.
Thank you. In the actual solution the code will be run for exactly 2k+1 times right because of k position of avengers and k+1 empty segments. So in a way k puts a limit over 2^n . Also in my dp solution I am not considering the distribution in a state which obviously matters.(same thing I did with problem A and got hacked )
After the testing i got wa on test 109 on B wtf =((
Lol, same.
I just love fast editorials <3. Thanks a lots <3
Video editorial: https://youtu.be/082mInmBC8Q?t=327
for Problem A Superhero Transformations using C++17's transform_reduce:
1111A - Superhero Transformation
For c you can just inplement a lazy created rangetree
The time complexity is more sensitively O(kn)
What made so many people lose B?
Weak pretests + previous expectations.
You usually don't have to make observations to solve div2B, but for many people the problem was unintuitive without making an observation: you will never increase a superhero that you delete. Seems obvious, but many people quickly went off on incorrect greedies because they did not stop to think. Even worse, these incorrect greedies passed pretests, which deceived people into thinking they got it.
The easy way to solve it is just realize that since you don't increase and delete the same superhero, you can separate them into "deleted" superheroes and "upgraded" superheros. After this the bruteforce is quite obvious.
Because there will be a problem if you use printf("%Lf") and choose G++11
I don't think it's proper of a Div.2 Test to have so hard a problem D and such weak pretests of problem B. In my room only two participants passed the final tests of problem B, but over ten participants passed the pretest. Some solutions are wrong obviously, but they can pass the pretest, too.
In D's editorial removal of character, shouldn't the loop has to go from x to n.
Yes, you are right.Updated now.
In problem D ,can jarvis make any arrangement?
Yes, any permutation is a product of transpositions
" all villains of a certain type either live in the first half of the colony or in the second half of the colony"-by certain type does it mean the type(s) at position x and y?
Why this solution get WA 4? I don't know why is not correct
In problem DIV2/C. Can someone please explain me how are we calculating number of avengers between l to r,I mean how exactly the upper_bound(v.begin(),v.end(),r)-lower_bound(v.begin(),v.end(),l) tells the exact number of avengers from l to r? Thanks in advance..!
In a sorted vector v, upper_bound(v.begin(),v.end(),y) gives the number of elements less than or equal to y in v. lower_bound(v.begin(),v.end(),x) gives the number of elements less than x in v. So, number of elements in v that are less than or equal to y and greater than or equal to x, i.e. in range [x,y] = upper_bound(v.begin(),v.end(),y)-lower_bound(v.begin(),v.end(),x)
say we're looking for number of elements within range [r,l] and vector v is sorted. upper_bound(v.begin(),v.end(),r)-v.begin() would return the position j of the least element not within the range lower_bound(v.begin(),v.end(),l)-v.begin() would return the position i of the least element within the range if it does exist (or the least element not withing range if there's no element withing the range which means i=j in this case) now in v[i],v[i+1],...,v[j-1],v[j] all elements v[i],..,v[j-1] would be within range no the total of elements within [a,b] would be (j-1)-i+1=j-i if there's no element within [a,b] as I stated before i=j so j-i=0 which is what we want I hope this helps :)
Can Prob.B be solved with a greedy algorithm?
It is already solved with greedy algorithm: we are trying to remove only minimal elements.
How to prove that the algorithm is correct
Suppose that we got answer, where we removed
x
insteady
, wherex
>y
. If we removey
insteadx
we will increase sum of element onx - y
and increase average value, and increase result. So, we need to removey
insteadx
.Tks !
https://codeforces.me/contest/1111/submission/49695185
my solution is getting WA on 15 , anybody help please.
https://codeforces.me/blog/entry/64989?#comment-491898
Thank you for your answering
Deceived badly in B!
i was trying to upsolve C problem using editorial approach https://codeforces.me/contest/1111/submission/49458002 (code is simple/easy to read) , I am getting TLE if anyone who solved C can suggest probable erroneous lines or any guess of eror , will be thankful
In your code you are making calls to your f() fn even if there are no avengers in [l,r].This is making your time complexity O(2^30) since you are visiting each node.You should instead return A if there are no avengers in [l,r] since breaking it down to 2 or more intervals will only increase answer (A+A..>A).
But in the worst case(one avenger in each node) time complexity is still O(2^30).
Maximum number of avengers given are 10^5 .So in the worst case only 10^5 nodes will be visited not 2^30
For Div2 B, I have approximately the same code as given in the tutorial, but in Java. The code fails for test case 37. Here it is. So, can anyone tell what exactly I did wrong?
test case 37 was submitted by me (for hacking)
u need long long when u do multiplication of k*n
otherwise it will exceed int
UNLUCKY
Not unlucky, fair and square an error on my side. Thanks for pointing that out!
May I know the reason why this round is unrated? It never stops to happen on codeforces, I experience this for the fourth time.
My WA solution for D: 1. I calculated the number of permutations of the selected letter types in one half. 2.Then I multiplied it by the permutation of the remaining letters. 3.I multiplied the whole result by 2 as the permutation of the selected types could happen in either of the halves. Can anyone point out where I am wrong?
"2.Then I multiplied it by the permutation of the remaining letters." This way you count also permutations in which non selected letters may violate the condition that all occurrences of a particular letter belong to the same half.
Try e.g. the test:
Thats where I was confused.I thought only the selected letters have to follow the rule.
Could anyone solve D in O(nk)?
Can anyone explain me problem D ? after we find result with O(n*k*k*k) for number of good string ?
In a normal knapsack when adding an item, we have the following dp
dp[i][j] = number of ways to get sum as j considering the first i items, and the transition is governed by
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - va[i]], val[i]= value of the ith item. Essentially we mean , To get sum as j, you can either exclude the ith item and use only i - 1 items, which is stored in dp[i - 1][j] or you can select the ith item, hence from the remaining i - 1 items you take all ways to generate j - val[i] as your sum, so that on adding val[i] it becomes j.
Now, what we are given is a table using i items, and we want to compute ways to get sum j as using only i-1 items. Basically removal of an item from knapsack. The transition now is,
dp[i - 1][j] = dp[i][j] - dp[i - 1][j - val[i]] ( I have just rearranged the above equation)
This says,(ways of getting sum as j using only i - 1 items) = (ways of getting sum as j using i items) — (ways to get sum as j in which ith item was necessarily included)
Here we know dp[i][j], but we do not know, dp[i - 1][j - val[i]]. But if we know dp[i - 1][j - val[i]], we know dp[i - 1][j]. Similarly if we know dp[i - 1][j - 2 * val[i]] , we know dp[i - 1][j - val[i]] and so on.
And obviously dp[i - 1][0] = 1 since there is always one way of not selecting any element to get sum as 0.
So what we do is we loop j from val[i] to n, and perform the operation dp[i - 1][j] = dp[i][j] - dp[i - 1][j - val[i]]
Now from the ways to generate combinations adding upto j, we get ways to generate combinations without frequency of any particular alphabet. Thus for two alphabets (x,y) we have the ways to get sum as n / 2 without frequencies of x and y. We multiply a 2 to this because the group containing x and y can be placed in any of the halves.
PS: I have removed one dimension from my dp hence it is 1D instead of 2D in the code.
D is a really cool problem IMO. But I couldn't quite grasp one part of the editorial, particularly the way you get to O(n * k2). Won't your "removal" algorithm that you use to obtain O(n * k2) result in the removal of any other character that appears as many times as the i-th one? If the state dp[k - buc[i]] is the number of ways to get k - buc[i], what happens if there is some character that one can use to get to k from k - buc[i]?
EDIT: I got it, it is only subtracted once, so it only accounts for the removal of one character.
Damn, this took me a few days to solve.
Here's an alternative solution to problem D. The idea is quite general in fact. Assume that we have some kind of a DP problem which involves processing a collection of O(k) elements, but we can process them in any order (like in knapsack), and each pass takes, say O(n), but, unlike in this problem, I won't assume that this forward-operation is reversible. Let's assume that the problem "gives" you k elements, then asks you to compute DP values for all k(k - 1) / 2 subsets of these k elements of size k - 2. This can be done as follows: Assume for simplicity that k = 2m for some m. Let s(x, y) be some sequence of numbers 1, ..., k such that x and y are missing from it. Note that we are free to permute this sequence as we see fit. If we could take all these sequences and store them in a trie and this trie ends up having no more than O(k2) nodes, we can compute DP values (in the leaves of the trie) by recursively solving for every node. Unfortunately the obvious way to form the sequence s(x, y) = [1, 2, ..., x - 1, x + 1, x + 2, ..., y - 2, y - 1, y + 1, y + 2, ..., k] does not work because the trie will have O(k3) nodes. Fortunately there is a better way. Form the sequence s by repeatedly finding the largest value w and then the smallest value i such that w is a power of two and i - 1 is divisible by w, such that all numbers in [i, i + w) are unused and different from x, y, then add these numbers to s(x, y). For example, if k = 8, x = 1, y = 3, s(x, y) = [5, 6, 7, 8, 2, 4]. When we insert all these sequences into the trie it will only use around 3k2 / 2 nodes, so the algorithm works in O(nk2).
can you give me some links about Euler tree (E)?
https://codeforces.me/blog/entry/18369
oh thank you
deleted
I didn't fully understand the explanation for the complexity of the solution for C and I would be very grateful if someone could explain it to me.
how is the complexity for C not (roughly) o((2^n*log(k))??
Let's imagine a tree similar to an interval tree. Node 1 is the interval (1,2^n). It has two children, 2 and 3, the intervals (1,mij),(mij+1,2^n). The tree obviously has 2^n*2-1 and the recursive function you described would go trough all of them, RIGHT? Then every node or interval considered has a binary search within it of o(log(k)), so the end result should be o((2^(n-1)-1)*log(k)) I have absolutely no clue where o(n*k) comes from, it would me amazing if someone could tell me.
No you will not be going over all nodes in the segment tree. This is because once we reach a node with no avenger in it, we do not again recurse into it. You kind of do the same thing in a range query. Here on top of not recursing, you take a cost A, with you. 2^n ~ 10^9 >> 10^5. This implies there are lots of points and subsequently ranges which you never need to visit.
Consider an example for more intuition : All avengers are in the first half. So since there is no avenger in the second half you will never go into that part and will get just a cost. Thus here itself, you reduced about 10^9/2 possible nodes to visit.
If you want to think about how many intervals are we not recursing into, the idea is that maximum number of disjoint intervals without any avenger will be k+1. If you imagine these k+1 intervals as a range query, each will yield (O(log(2^n))=n), intervals in the segtree. And once you reach these you do not go any further. Thus the contributing factor are those intervals in which you have avengers, but the number of avengers is much less ~ 10^5, hence such intervals also become limited.
Why this round problems do not have difficulty tag?
Can someone help me with B, https://codeforces.me/contest/1111/submission/49674082 i am trying to solve it by removing i elements at a time.
You are allowed a maximum of m operations. So, the final loop should run till min(m, n-1) instead of n. (n-1 because you can not remove all elements).
Thank you!
.
For E, I'm afraid you forget the dp part when analyzing the time complexity. For each query, it takes O(mk) time to do dp, and that's why the upper bound of m is necessary for the problem.
What is the problem with my submission? I am not able to figure it out.
https://codeforces.me/contest/1111/submission/50346012
Getting WA on testcase 37.
You sort the array increasing order, but then work on it like it wourld be sorted decreasing. One of both iterations must be in reverse order.
1
Good C, D, E problems.
some of those were damn instructive .
Can someone please help me with
1111C - Creative Snap
?if I remove
x == 0
part, i.e. I recur even if there is no avenger, it gives TLE on testcase 5 (My TLE Solution ). I don't understand why so ? How does it change worst case complexity of the code ? and how is it guarenteed that the solution that results from going into recursion will be more than that by not going into recursion ?nitesh_gupta ?
Suppose in the range (l,r) the number of avengers are 0. So the power consumed is A but if we recur for (l,mid) and (mid,r), the number of avengers in (l,mid) and (mid,r) are still 0. So,they return >=2A. Hence it is always better to take A instead of recurring.
but won't the time complexity in worst case be same even if we recur ?
K can be at max 10^5 and n can be 2^30 so you can see that there will be too many gaps, even if we try to put the avengers at distinct places the maximum places we can fill are 10^5. Calling recursion on the remaining empty gaps can be costly.
For problem C I think we can achieve $$$O(k)$$$, by keeping the $$$[l, r]$$$ index range in each recursion, and only perform binary search there in $$$O(1+\log (r-l))$$$ time. Then we can write the recursive formula as $$$T(k) = T(x) + T(k-x) + \log k+1$$$, for some $$$x$$$. Then we use concavity of the log function to get $$$T(k) \le 2T(k/2) + \log k+1$$$. This solves to $$$T(k) = O(k)$$$ by the master theorem.