https://www.codechef.com/viewsolution/24331051
I know this can be done with bitsetā¦but initially i tried set_intersection() methodā¦it gives tleā¦
Any thoughts on this?
1 Like
I think you need to sort those vectors before using set_intersection
Mine passes in 0.23 using set_intersection 
https://www.codechef.com/viewsolution/24332547
1 Like
lol. I thought subgraph meant choosing only some vertices and all edges in that vertices. 
learnt something new 
Now i think about it, Is there any good way to solve this problem. I could not solve it though out the contest?
Your logic is wrong I think
Try the following case :
5 5 2
1 2
1 4
3 2
3 4
4 5
The answer should be YES but your output is NO
1 Like
The method specified in the editorial is really bad for Java, in terms of Time limit. Even after using Fast IO, it kept on giving TLE. In the end, deeper language-specific optimisations had to be used to get AC. Please try to keep less tight Time Limits next time, so that at least the correct solutions pass.
If this would have happened with me during the contest, it would have cost me quite many penalties 
Time limit is too strict, even setterās solution is failing without Fast I/O
Thanks a lot for the test case . Now I realize what is wrong with the algorithm. It only considers that edges may be inserted in the graph leading to components being merged together. But, it does not consider the fact that vertices may be removed which may also split the components. I think incorporating this new idea into the algorithm is gonna be slightly difficult implementation wise.
@r_k_p I think its just to distinguish between x and y so that we donāt end up getting something like cnt[4][4] or any other number.
I solved it with (x!=y) condition and it passed.
How is its time complexity is o(n^2*k) ?
As you need to find k different āyā b/w two nodes say āxā and āzāā¦ So we have total nC2 pairs of x and zā¦
Now we break loop when we find k "y"s b/w any one āxā and āzā and hence we can visit at max
k+(k-1)*(nC2-1) "y"s
And hence complexity is
O(k+(k-1)*(nC2-1)) == O(n^2*k)
As n^2*k is dominantā¦
1 Like
yes ! someone used it here and even got AC. I wonder how a O(n3) got an AC. Is it technical fault ? Or the time complexity is less than O(n3) ???
1 Like
what optimization techniques do you use to get the answerā¦ because i got TLE when i used java.
I used Fast IO reader class. Other than that, I used ArrayDeque to store the edges, as opposed to Arraylist, etc.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool check(vector a,vector b,int k)
{
sort(a.begin(),a.end());
sort(b.begin(),b.end());
vector<int> v(a.size());
auto it = set_intersection(a.begin(),a.end(),b.begin(),b.end(),back_inserter(v));
if(it-v.begin()>=k)
return true;
else return false;
}
int main()
{
int n,m,k;
cin>>n>>m>>k;
vector v1[n];
int x,y;
for(int i=0;i<m;i++)
{
cin>>x>>y;
v1[x-1].push_back(y-1);
v1[y-1].push_back(x-1);
}
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(check(v1[i],v1[j],k)){
cout<<āYESā;
return 0;}
}
}
cout<<āNOā;
}
Can you tell what wrong with this solution?? it is giving TLE.
1 Like
it passed when i used fast i/o.
1 Like
I too made the same mistake. 
Can someone please tell me, why āPigeonhole Principleā is in the tag?
Or please let me know the approach to solve the problem using Pigeonhole Principle.
2 Likes
Yes, using bitsets its possible to get AC. It probably shouldnāt get accepted.