Before contest

Codeforces Round #687 (Div. 1, based on Technocup 2021 Elimination Round 2)

37:32:40

Register now »

Codeforces Round #687 (Div. 1, based on Technocup 2021 Elimination Round 2)

37:32:40

Register now »

*has extra registration

Before contest

Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)

37:32:40

Register now »

Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)

37:32:40

Register now »

*has extra registration

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

1 | tourist | 3687 |

2 | ecnerwala | 3600 |

3 | Benq | 3503 |

4 | ksun48 | 3421 |

5 | Um_nik | 3412 |

6 | Radewoosh | 3382 |

7 | maroonrk | 3323 |

8 | Itst | 3239 |

9 | apiadu | 3238 |

10 | ko_osaga | 3232 |

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

1 | Errichto | 205 |

2 | SecondThread | 197 |

3 | Monogon | 195 |

4 | vovuh | 189 |

5 | Um_nik | 186 |

6 | pikmike | 185 |

7 | antontrygubO_o | 184 |

8 | Ashishgup | 182 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/27/2020 20:32:21 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been translated by omoyamo (original revision, translated revision, compare)What is the source of this problem?

His imagination.

What is the range of the integers in the array?

10^4

I don't know exact time complexity, but use treap, where every node maintains '2D-Persistent tree with FFT on each node'. To further optimization use meet-in-the-middle, but I don't know how to merge, but at all you can create a graph, after that go to Dominator tree and do some stuffs with combinatorics or Burnside's lemma. But I don't know time complexity.

I calculated time complexity, it is approximately $$$O(-1)$$$

reported

wtf MADEVIL? You stole my comment. Wtf!?

I don't have an exact time complexity, but I think I do have a few steps towards a solution.

First let's make a segment tree of sets. Since it doesn't help to have multiple of a single number, we can operate on those sets instead of the raw array.

Second, let's compensate for the GCD by getting the maximum 2-3 LCM's. This should be safe because GCD is almost always small relative to LCM.

Now, how do we find the largest LCM quickly from a set of numbers? I suggest we simply run two for loops, each starting from the large end of the set, and calculate the LCMs. Importantly, we should short-circuit when we cannot possibly find a larger LCM later in the loop.

If we consider the first run of the outer loop, either we find some LCM greater than the largest number in the set, or it we don't. If we don't then we know all the rest of the numbers are factors of this one, so there is a small number of them and our loops will be short. If we don't, then we have some larger number as out biggest current LCM. Each inner loop can them be short circuited when the two elements multiplied is smaller than that LCM.

"This should be safe because GCD is almost always small relative to LCM." Yeah, but this is not an approximation problem. What about something like 4 7 10 15 4 7 10 15 4 7 10 15 etc.?