Storm_Stark's blog

Google code Kickstart 2019 (Round E)
By Storm_Stark, history, 5 years ago, In English

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:

  1. number =2^p1*3^p2*5^p3......... 1.total number of factors=(p1+1)*(p2+1)*....
  2. total odd factors(X)=(p2+1)*()...
  3. total even factor=(p1+1)X-X=p1*X;
  4. diff=(p1-1)*X;
  5. if p1=0 -x>=-2 so 1 or prime number
  6. if p1=1 diff=0
  7. if p1=2 X<=2 so 4 or prime
  8. if p1=3 then only 8 is possible

  9. 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/

I was unable to solve B I took C/E ratio and proceeded with greedy implementation but was getting the wrong answer.

Can anyone help?

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Ratio might cause precision issues, instead cross multiply and compare

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

MST of a graph with only unit weights is n — 1, where n is number of nodes

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply