Google kickstart 2019 E

In the Cherries Mesh problem, what logic is to applied?


I wrote this code but i am not sure in which test cases it’s giving wrong ans, is the soln right?

int main(){
ios_base::sync_with_stdio(false) ; cin.tie(nullptr) ;
int t ;
cin>>t ;
while(t–){
int ans= 0;
int n,m,ci,di ;
cin>>n>>m ;
for(int i=0;i<m;i++){
cin>>ci>>di ;
}
int cnt=m ;
int tedge = n-1 ;
cout<<m+(tedge-cnt)*2<<endl ;
}

}

Copy pasting my reply:-

this gave me AC:-
Found all connected components, added the weights of their spanning trees, finally I connected all those components using red edges.
AC code:-https://docs.google.com/document/d/1V1NGuwGiPC5D_yeRgDAZSa5RW1v-n9eN2-DlnB-9SlY/edit?usp=drivesdk

2 Likes

bro, i also thought to use a graph and connected components, but can u analyse my solution, just take a glimpse, and sort out anything from it it will be helpful :slight_smile:

Answer is not very correct because your code didn’t count the number of connected components. Thats my conclusion. Only Graph/DSU can solve this problem.

2 Likes

I used to the fact that for V vertices, we need V-1 edges, counted all the Black edges first and then added the remaining red edges

can u provide some tricky testcases for the same

We should discuss that in DM as it deviates from the topic.(I don’t want anyone to bash both of us.)

1 Like

I figured dfs would time out looking at the constraints since dfs takes {O(|E|+|V|)} and in worst case may take {O(|V|^2)}. Hence, I used DSU. How is that your solution was able to pass the given constraints?

Because my solution’s time complexity is :- Time Complexity of DFS.(I didn’t actually calculate spanning trees as there was no need, only observation was enough for me to calculate each spanning tree, my bad, I never studied DSU.)

Well, you can do dfs on any graph which has (10^5) number of nodes, and (10^5) edges…I don’t think there is anything new in it . No one gets TLE for dfs for sparse graphs. And worst case for DFS is :- O(V+E).

I repeat, WORST CASE FOR DFS IS :- O(V+E) .

But wait. What happens if {|E|=\dfrac{|V|*|V-1|}{2}}. Won’t it be {O(|V|^2)}?

Now, its frustrating for me. Who said the number of edges is always ‘v*(v-1)/2’??? This is the condition only for a complete graph. My graph has only ‘M’ edges , mentioned in the problem statement itself. In short, my graph has 10^5 nodes and 10^5 edges.(All edges in my graph are BLACK.) . I won’t give further clarifications.

2 Likes

what there will be only 1e5 edges so dfs will never go beyond 2*1e5 in worst case …dfs is the optimal solution here /////

1 Like

karan what about third question can u help me with a littile bit–
here is my solution : https://ideone.com/CBxHy1
How can i optimise my solution, correct me if i m wrong

  1. instead of checking for each odd n0. first check it is prime or not
  2. already store ount upto 10^9
    @samarthtandon plz see and help me
1 Like

DSU is only useful for trees not for graph…

this passes small test cases??

yes,it passes small test cases

Damn. I saw only {M \leq N*(N-1)/2} and didn’t see {0 \leq M \leq 10^5} which is given at the end. Did I just get 3 penalties for not seeing this. My first attempt with dfs passed all testcases. And to optimize it I used DSU.

Kickstart considers last successfully submitted solution as final solution?

And thank you @karangreat234 for pointing it out

1 Like

3rd one was sad event. As my brute-force didn’t pass anything. 2nd problem is standard Gaussian+Diophantine.