If you're interested in learning more about CPU hardware details and how they affect program performance, read my blog post here on how memory latency impacts binary search and causes an

$$$O(\sqrt[3]{n})$$$

runtime.Enjoy!

Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

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

1 | MiFaFaOvO | 3681 |

2 | tourist | 3404 |

3 | TLE | 3356 |

4 | apiadu | 3351 |

5 | mnbvmar | 3281 |

6 | LHiC | 3276 |

7 | Um_nik | 3268 |

8 | 300iq | 3267 |

9 | yosupo | 3249 |

10 | ainta | 3226 |

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

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 169 |

5 | vovuh | 167 |

6 | pikmike | 166 |

7 | ko_osaga | 161 |

8 | Um_nik | 160 |

9 | Petr | 155 |

10 | McDic | 153 |

If you're interested in learning more about CPU hardware details and how they affect program performance, read my blog post here on how memory latency impacts binary search and causes an

$$$O(\sqrt[3]{n})$$$

runtime.Enjoy!

I recently wrote an article about Schonhage-Strassen on my personal blog here. It is an algorithm to multiply two *N* bit integers in time. If you want additional background on the signal processing stuff mentioned in the article, read the first part of the post here.

I doubt this will be useful for competitive programming because Schonhage-Strassen has a pretty high constant factor and is pretty tedious to implement--in general floating point FFT-based solutions are fine for competitive programming size inputs and NTT-based stuff like this is overkill. Hopefully some of you will still find it interesting though!

Here's a technique to do C — New Year and Curling in time with segment tree. Brute force *n*^{2} is of course fast enough, but I think speeding it up was interesting.

Suppose we are about to place disk *i* at *x*_{i}. The relevant x range we should look for disks is [*x*_{i} - 2*r*, *x*_{i} + 2*r*] because things outside of this range are too far away to intersect with this disc. Say we find *j* such that *j* < *i*, *x*_{j} is in the needed range, and *y*_{j} is maximized. We can find such *j* with a basic segment tree in time. The intuition behind the approach is that is a good lower bound for *y*_{i}. Specifically, *y*_{i} < *y*_{i}' + 2*r* as shown by the diagram:

In this worst case scenario we find that disk *j* corresponds to the left disk. However, another disk is centered at (*x*_{i}, *y*_{j} - ε). So *y*_{i}' in this case is *y*_{j} but the true answer is *y*_{j} + 2*r* - ε. If we could find the second-highest circle with our segment tree, we'd get the answer right in this case. We can do this by first querying [*x*_{i} - 2*r*, *x*_{i} + 2*r*] and getting back a result *x*_{q1}. Assume *x*_{q1} < *x*_{i} (the other case is symmetric); we next query (*x*_{q1}, *x*_{i} + 2*r*]. Say this second query result is *x*_{q2} with *x*_{q2} > *x*_{i} (again other case is symmetric); we next query (*x*_{q}, *x*_{q2}) to get the third-highest circle. If we do this just a few times we're guaranteed to get the right answer.

The reasoning behind this is that a constant number of circles fit in the "relevant area," regardless of what *n* or *r* are. The relevant area is a 4*r* x 2*r* rectangle horizontally centered at *x*_{i} and with the top y value *y*_{q1}. It's the black box in the diagram above. If a disk's center is horizontally outside this range, the disk won't intersect the query disk. If the disk is below the relevant area, it's too low to matter (*y*_{i}' is higher). And no disk can be above this area because of how *y*_{q1} is defined. The relevant box has area 8*r*^{2}, and any circle centered in it must occupy at least π *r*^{2} / 4 area, so at most 10 circles inside of the box. So, if we do our procedure 10 times (so 10 segment tree queries), we're guaranteed to get the answer. 10 is a pretty loose bound and I got AC with 4.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/20/2020 02:47:57 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|