Cherries Mesh:
Logic:
use Kruskal to find mst of different components, then suppose there are K component then we require k-1 connection of 2 to connect them. answer=sum of mst of min wt of diff component+(k-1)*2;
code:
https://shashankmishracoder.wordpress.com/2019/08/25/125/
Street Checkers
logic:
- number =2^p1*3^p2*5^p3......... 1.total number of factors=(p1+1)*(p2+1)*....
- total odd factors(X)=(p2+1)*()...
- total even factor=(p1+1)X-X=p1*X;
- diff=(p1-1)*X;
- if p1=0 -x>=-2 so 1 or prime number
- if p1=1 diff=0
- if p1=2 X<=2 so 4 or prime
- if p1=3 then only 8 is possible
calculate if number is prime from L to R(using segmented sieve) the use above conditions.
code:
https://shashankmishracoder.wordpress.com/2019/08/25/google-kickstart-2019round-e-street-checkers/
Ratio might cause precision issues, instead cross multiply and compare
Can you please share link of your solution?
This is good — Mahmoudian's solutions
thanks dude!
I used ratio and got AC Solution
I wrote "might" cause, it's wise to stay away from floating when you can do with integers
Could not come up with any solution that does not involve ratios during the contest :-(
MST of a graph with only unit weights is n — 1, where n is number of nodes
Oh right could have used that
I have some doubts regarding the first question , Cherries Mesh. Like in the second sample test case , it is given that , n = 3 , m = 1 and cherries {2,3} are connected with a black strand. It is given that pairs not mentioned are connected with a red strand. Does that mean that pairs {1,2} , {1,3} are connected with a red strand ?
Also , what does "each pair of cherries is connected directly or indirectly via a sugar strand," mean ? What does a cherry being 'indirectly' connected to a sugar strand mean ?
you don't have to connect both 1,2 and 1,3 anyone will be enough. a direct connection means u,v has the edge of red strand between them indirect means they do not have edge connection of red strand but are connected by some path in tree form of this fully connected graph. question is just about connecting diff trees with a strand of weight 2 to form one minimum spanning tree.
What I meant was, are 1 and 2 along with 1 and 3 connected by red strand originally before removing any strands. I got what indirect connection mean.
What I get is, the question is about forming a minimum spanning tree by removing a few edges. Am I right ?
I did not get this statement though, "question is just about connecting diff trees with a strand of weight 2 to form one minimum spanning tree." What does diff tree means, and why only with strands of weight 2, the MST can have strands of weight 1 as well. Perhaps I am misunderstanding your statement. Thanks, for the clarification though.
Sorry I didn't clarify properly. 1. So you are provided a fully connected graph(n nodes and (n*(n-1))/2 edges. 2. m edges in it have weight 1 and rest (n*(n-1))/2-m have weight two. 3. you have to find a weighted sum of its minimum spanning tree. 4. n can be 10^5 so you cant apply algo to full graph with (n*(n-1))/2 edges. 5. m is given 10^5 .so let's consider only m edges 6. now we might be left with multiple connected components. 7. let's find mst of these components, notice these components have the same weight of one therefore there mst weight will be a size of component-1.(tree of n nodes has n-1 edges) 8. Now you have to connect these components, let's suppose you have K connected components in the graph you can connect them using k-1 edges of weight 2) 9.this will be your final answer. 10.Eg: in test case 1 (2,3) are connected by an edge with weight 1 and other by edge with weight 2.So first consider edge with weight 1 you will get two components(first(2,3) and second 1) ,so ans+=(2-1)+(1-1) now you need k-1 ie 1 edge of weight 2 to connect component (2,3) and (1) ,therefore ans+=2*(2-1) 11. Do ask if you still have any doubt