Hello CFC (Codeforces community).

What is the most beautiful problem, you have seen on Codeforces?

Why do you think so?

Come on!

Please share beautiful problems you have seen on Codeforces.

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

1 | tourist | 3557 |

2 | Um_nik | 3494 |

3 | Radewoosh | 3344 |

4 | wxhtxdy | 3309 |

5 | LHiC | 3302 |

6 | Benq | 3286 |

7 | mnbvmar | 3274 |

8 | Petr | 3254 |

9 | yutaka1999 | 3190 |

10 | ksun48 | 3170 |

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

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | PikMike | 165 |

3 | antontrygubO_o | 165 |

3 | Vovuh | 165 |

6 | tourist | 161 |

7 | rng_58 | 160 |

8 | majk | 156 |

8 | Um_nik | 156 |

10 | 300iq | 155 |

Hello CFC (Codeforces community).

What is the most beautiful problem, you have seen on Codeforces?

Why do you think so?

Come on!

Please share beautiful problems you have seen on Codeforces.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/16/2019 04:19:29 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

For me its the most beautiful problem if I could not able to solve it

First of all I should say that I read tags :)

My favorite problem is Powerful array. It has a very useful idea.

nice problem :) can u explain the idea behind dividing the array into p equal parts Q_1, ..., Q_p then sorting them according to the rule mentioned in the editorial ?? how does that improve run time from order O(n^2) to o(n*sqrt(t))??

First we divide the array into

sq=sqrt(n) equal partsQ_{1},Q_{2}, ...,Q_{sq}, then we sort the queries and answer them offline.For each part we sort the queries with

linside that part by theirr.(Is this part clear?)Then we use a kind of two pointer to answer the queries. We have two pointers

sanderepresenting the segment that we have its answer at the time and an integertotrepresenting the answer of the segment [s,e].(At the beginnings=e= 0 and we have the answer of the [s,e] equal toa_{0})When we want to know the answer of a segment [

l,r] we simply movestolandetor. As we have a good sorting the total number of times we movesandeis not too much :)let's see how

sandemove.We answer the queries of each part separately so if we prove that the number of times we move

einQ_{i}is inO(n) then we can say that the total number times we moveeisO(n*sqrt(n)).As we sorted the queries in each part by their

rsoemoves at mostntimes(in each part). Soemoves a total ofn*sqrt(n) times(at the worst time).Also for

each querywe changesat mostsqrt(n) times (from the beginning of Q_i to the end of it) so the total number of times we changesisO(n*sqrt(n)).Now it's easy to say that the total number of our moves is

O(n*sqrt(n)). :)Tell me if it was not clear enough.

One of the most beautiful problems I have solved that come to mind now is

Top 10, from Jakarta 2009. I tried it a few months ago while I was learning Suffix Array, and I was blown away by it. It combines many useful techniques and algorithms. It's justsublime.Here's the link -> Top 10

I solved that problem just sorting, test cases are weak but is a beautiful problem.

Auto comment: topic has been updated by Kuzey-Tekin (previous revision, new revision, compare).