This contest was held on October 22nd, but no solutions have been posted. Any ideas for FGH?

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

1 | tourist | 3565 |

2 | Benq | 3540 |

3 | Petr | 3519 |

4 | maroonrk | 3503 |

5 | jiangly | 3391 |

6 | ecnerwala | 3363 |

7 | Radewoosh | 3349 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

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

1 | 1-gon | 199 |

2 | Errichto | 196 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

4 | awoo | 186 |

6 | Um_nik | 182 |

7 | vovuh | 178 |

8 | Ashishgup | 176 |

9 | -is-this-fft- | 173 |

9 | antontrygubO_o | 173 |

This contest was held on October 22nd, but no solutions have been posted. Any ideas for FGH?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/04/2021 00:28:17 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Why the fuck are you minusing this post? It is a NP-Hard problem to understand CF Community. LOL.

http://codeforces.com/blog/entry/55503 this similar blog gets +20 while this got -4...

To be honest, much more than the community itself, I'm sick of people complaining about it...

I am sick about people complaining about people complaining about it.

I am sick about people complaining about people complaining about people complaining about it.

Ahhh... Not this again :/

For

problem G(the complexity is , not sure if it fits the time limit):The x and y coordinates are completely independent, therefore we just have to solve the same problem twice.

To process the queries we use Mo's algorithm. At each step of the algorithm we keep a balanced tree of the values currently in the range (the balanced tree must also keep the sum on a subtree) (a treap seems perfect).

When we add (or delete) a new value to the balanced tree , we also update the answer accordingly. Indeed the new answer differs from the previous one by

s- 2p- (t- 2c)v(wherevis the new value,pis the prefix sum,sis the total sum,cis the position in the balanced tree,tis the total number of elements in the tree).I tried doing something like that here, but I think it's too slow.

Compressing coordinates and using a Fenwick tree instead of a treap might speed it up a lot.

Ideas for F:

The coloring always exists and is always unique.

Assume for now that no line is vertical. Let be the number of lines below a point p. Then the color of

pis given by .Hence we want to compute the number of lines below a query point. This can be done with the Bentley-Ottmann sweepline algorithm. As the algorithm maintains the relative position of the lines in a BST, we can do a binary search to count the number of lines below the point. The time complexity is .

To improve the runtime, split the lines into

kblocks of size . Run the above algorithm for each block. This takes time, which is for .In order to account for vertical lines, add to the color of each point where is the number of lines to the left of

p. can be computed easily in .Ideas for H:

For each segment, consider the line thought the segment and for each endpoint of the segment the line thought that point perpendicular to the segment. Construct the arrangement of the lines. This takes Θ(

n^{2}) time and space.For every segment, look at the arrangement-edges from it's line and mark all edges that are part of the segment. (By construction all edges are either part of the segment or contain no common interior with the segment). For every edge not marked this way, connect the two faces sharing this edge. Then sum over all faces that are not connected to the infinite face. The total runtime is Θ(

n^{2}), as the arrangement has size Θ(n^{2}) and every line gets split into edges.There might also be a solution based on random sampling, as the required precision is quite low.