2021 December Silver Q2 - "Connecting Two Barns"

Problems and Contests
#1

Hi everyone,

I’m currently looking at the solution from 2021 December Silver Problem 2 (Connecting Two Barns). I have finished the code similar to solution 1 myself.

It is difficult for me to understand this part in the 2nd solution: "It is also possible to do this in linear time by maintaining the pair of indices we consider and considering adding edges from vertex i in increasing order of i. The pair of indices we consider will be nondecreasing, so we only consider a linear number of edges. "

I have read the corresponding code in the 2nd solution, but still not be able to understand.

Could someone please elaborate on this part? Thanks a lot!

Bo

1 Like
#2

Hi there,

Basically, we can use some sort of two-pointers method to replace the binary search.

If we wanted to connect group a and group b for example :
For a certain value for ‘node a’ from group a, we can keep track of two variables/pointers, corresponding to the indices we consider. These are indices corresponding to the {maximum lower} and {minimum higher} values of nodes in group b, comparing them to the current node a’s value.

If we sorted the nodes in each group by value, before the two-pointers, this would take linear time.

Hope it helps!

1 Like