question — Kuroni and Cowsheds

link to question — https://www.codechef.com/LTIME85A/problems/COWSHEDS

can someone please explain the solution?

I couldnt do better than Q*N basically go L to R + dsu

Before contest

Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)

17:49:14

Register now »

Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)

17:49:14

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | Radewoosh | 3707 |

2 | Benq | 3691 |

3 | tourist | 3669 |

4 | ecnerwala | 3565 |

5 | Um_nik | 3533 |

6 | ksun48 | 3489 |

7 | maroonrk | 3457 |

7 | jiangly | 3457 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 187 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 178 |

6 | Radewoosh | 176 |

6 | -is-this-fft- | 176 |

8 | maroonrk | 175 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 171 |

question — Kuroni and Cowsheds

link to question — https://www.codechef.com/LTIME85A/problems/COWSHEDS

can someone please explain the solution?

I couldnt do better than Q*N basically go L to R + dsu

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/13/2021 00:45:47 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I couldn't solve it myself but I'll explain a solution I've heard from someone else.

Throughout all the queries combined, observe that the merging of two different sets of DSU happens N-1 times at max. Now let's look at a single query [L, R]. Let's identify all the elements getting merged as a_1, a_2, ..., a_2k, in order. As we've observed, the sum of k over all queries is less than N. These elements partition the query into 2k+1 parts, where i th part is identical to the reversed 2k+2-i th part. Instead of doing a linear search, we can just use binary search + hash (using the label of DSU) to find each of these parts in O((logN)^2). Since there are O(N+Q) such parts throughout all the queries, our final complexity is O((N+Q)(logN)^2). Code.

in your code why are you checking for the dsu merge as well?

while(l < r && dsu.merge(l, r — 1, tr))

once we get the length from where we cn start merging i.e. L + len and R — len are in same component dont we just merge till they meet?

It could be the case that there are multiple isolated merges separated by intervals which don't get merged. We have to repeat "(1) Binary search to find the maximal interval which don't get merged (2) Merge relevent elements" this two processes multiple times until we're done querying [L, R].