I received an email about an event.

Be careful not to provide your password there! This is a scam. After clicking on register page you are NOT getting redirected to codeforces!

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

1 | tourist | 4009 |

2 | jiangly | 3839 |

3 | Radewoosh | 3646 |

4 | jqdai0815 | 3620 |

4 | Benq | 3620 |

6 | orzdevinwang | 3612 |

7 | Geothermal | 3569 |

8 | ecnerwala | 3494 |

9 | Um_nik | 3396 |

10 | gamegame | 3386 |

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

1 | maomao90 | 164 |

2 | Um_nik | 163 |

3 | atcoder_official | 158 |

3 | cry | 158 |

3 | -is-this-fft- | 158 |

6 | awoo | 155 |

7 | adamant | 154 |

7 | nor | 154 |

9 | TheScrasse | 153 |

10 | Dominater069 | 152 |

I received an email about an event.

Be careful not to provide your password there! This is a scam. After clicking on register page you are NOT getting redirected to codeforces!

Hello!

Some time ago I created a problem for local programming competition. Unfortunately it turned out that I had incomplete proof of one lemma, that I can not show even to this day.

**Lemma:** Given an increasing array of $$$N$$$ arbitrary large numbers we define its cost as sum of lengths of all non-trivial, maximal arithmetic progressions starting at the first element. The cost of any array is $$$\mathcal{O}(N\log{N})$$$.

For example for array $$$[0, 2, 3, 4, 6, 8, 9]$$$ — the total cost is $$$|[0, 2, 4, 6, 8]| + |[0, 3, 6, 9]| + |[0, 4, 8]| + |[0, 6]| + |[0, 8]| + |[0, 9]| = 5 + 4 + 3 + 2 + 2 + 2= 18$$$.

It is easy to see, that if we simply take $$$N$$$ consecutive natural numbers we get $$$\mathcal{O}(N\log{N})$$$ cost, but I was not able to prove that this is the worst case scenario.

Best complexity I can show is $$$\mathcal{o}(N^2)$$$, but still far from the goal...

Can anyone show if the lemma is true or false?

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/11/2024 08:43:34 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|