Can you please suggest problems which are based on segments, intervals, line sweep (for intervals etc), like this one. How to find such problems on codeforces or other judges? Thanks!

Before contest

Codeforces Round sponsored by NEAR (Div. 1 + Div. 2)

2 days

Register now »

Codeforces Round sponsored by NEAR (Div. 1 + Div. 2)

2 days

Register now »

*has extra registration

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

1 | tourist | 3803 |

2 | jiangly | 3707 |

3 | Benq | 3627 |

4 | ecnerwala | 3584 |

5 | orzdevinwang | 3573 |

6 | Geothermal | 3569 |

6 | cnnfls_csy | 3569 |

8 | Radewoosh | 3542 |

9 | jqdai0815 | 3532 |

10 | gyh20 | 3447 |

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

1 | awoo | 162 |

2 | maomao90 | 160 |

3 | adamant | 157 |

4 | maroonrk | 154 |

5 | -is-this-fft- | 149 |

6 | Petr | 148 |

6 | SecondThread | 148 |

8 | atcoder_official | 147 |

9 | TheScrasse | 145 |

9 | nor | 145 |

Suppose for a function f(x) , for different values of x , f(x) is a bool value yes(y) or no(n) as:-

$$$nnnnnyyyyynnnnn$$$

Also suppose the check function in bsearch returns (-1) if its in the left 'n' block , (0) if its a 'y', and (1) if its in the right 'n' block.

So I need to find the largest value of x for which f(x) is yes(y). Is it doable by binary search?

(Usually we have f(x) varying as $$$yyyyyynnnnnn$$$ or $$$nnnnnnyyyyyy$$$ and in that we can easily use bsearch.)

Given array of n elements. Find the number of pairs i, j (1 ≤ i < j ≤ n) such that gcd(ai,aj) = 1.

Constraints are: 1 ≤ N ≤ 30000, 1 ≤ a i ≤ (10^8). TL = 0.6s

One user has explained the solution here but I am not able to understand how subsets are used in the solution and the time complexity part.

If someone can please explain, it would be of much help. Thanks in advance!

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/16/2024 13:11:06 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|