Kuzey's blog

The most Beatiful problem you have ever seen
By Kuzey, history, 9 years ago, In English

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.

  • Vote: I like it
  • +51
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it -20 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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))??

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      First we divide the array into sq = sqrt(n) equal parts Q1, Q2, ..., Qsq , then we sort the queries and answer them offline.

      For each part we sort the queries with l inside that part by their r.(Is this part clear?)

      Then we use a kind of two pointer to answer the queries. We have two pointers s and e representing the segment that we have its answer at the time and an integer tot representing the answer of the segment [s, e].(At the beginning s = e = 0 and we have the answer of the [s, e] equal to a0)

      When we want to know the answer of a segment [l, r] we simply move s to l and e to r. As we have a good sorting the total number of times we move s and e is not too much :)

      let's see how s and e move.

      We answer the queries of each part separately so if we prove that the number of times we move e in Qi is in O(n) then we can say that the total number times we move e is O(n * sqrt(n)).

      As we sorted the queries in each part by their r so e moves at most n times(in each part). So e moves a total of n * sqrt(n) times(at the worst time).

      Also for each query we change s at most sqrt(n) times (from the beginning of Q_i to the end of it) so the total number of times we change s is O(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.

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

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 just sublime.

Here's the link -> Top 10

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply