fofao_funk's blog

Most beautiful solutions ever
By fofao_funk, history, 6 years ago, In English

Hey, all.

I think that from time to time all of us stumble upon a solution for a problem that make we go 'holy shit, this is beautiful'. So, I'd like to ask you guys to post the most beautiful/creative/out of the box solutions you've ever seen/created in the programming competitions world, so we can all see how cool some of them are and get a little bit inspired.

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

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

http://codeforces.net/blog/entry/62742?#comment-468717

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

    Ok, what about it isn't beautiful?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      It is beautiful, just idiots on cf too lazy to read it

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

    I also have made quite a nice solution for this problem: 44868649. It looks complicated, but it isn't. I made a recursive function to count sum of those numbers with prefix X. And then I know, that this number is always not in [l,r] I return 0, if I know that this number is always in [l,r] I return another, simplier function. Sometimes it is easier to calculate (1,r) and subtract (1,l-1). But I always do prefix recursion, because after doing it your dp state is much cleanier.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.spoj.com/problems/ADACOINS/ A lot of you would've seen this problem, but the first time I solved this, it felt amazing.

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

I remember that all other solutions for this where Max Flow/Matching but mine was a simple nested for loop it felt amazing to solve it that way.

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

This div2A 31086095 from round 439, AC in 5 characters

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    I can't believe there's a problem with such test cases

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

      The test cases aren't weak, the answer is Karen for any input

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

        Well I didn't mean the test cases are weak, It's just interesting to see a problem with only 1 answer for any input.

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

http://codeforces.net/contest/1041/submission/42923868

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved this problem before with this 42353615 and It was beautiful solution for me, but seeing this blog, I've just improved the code to be 45168777, what do you think about it :)?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it

    One of the authors solutions on Python:

    Solution
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow! It's very important geometry point to solve this problem. Thank you very much for pointing this way out for us <3.

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

It is the most beautiful, greedy solution that I've ever seen.

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

IOI 2006 joining points: Solution

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

    I agree, this is one of the most beautiful problems I have ever seen.

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

this 22059230.

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

    Ctrl+D Approach

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

      When there are so many nested for loops you don't even care about indenting them

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

        Yeah, to not reach to another country while writing and debugging:

        "Mom, I'm going to the CodetailLand, do you want any thing from me :'(?"

        "Nothing other than your healthiness, my soul QAQ"

        → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The following queue-based solution of this recent problem 999C - Alphabetic Removals is among the most elegant solutions I have ever written.

45174979

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

How about the easiest problem ever?)

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

I had the reaction that you described when I saw the solution for an problem from the JOI Spring Camp. The solution was so elegant and simple that I decided to write a blog about it.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +73 Vote: I do not like it

I don't know from where this problem is, but it's beautiful. There is no need to know complex algorithms (just basic), it's all about thinking. Thanks to kostka for showing it to us.

You are given a connected graph with n ≤ 200, m ≤ 10000. Each edge has two weights — 1 ≤ ai, bi < 256. We say that cost of spanning tree of this graph is equal to over picked edges. Find the spanning tree with minimum cost.

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

    It's from BalkanOI 2011, me and Radewoosh are also big fans of this problem.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Ok, now two out of my three favorite problems are mentioned here. I am waiting for someone to post the third one ;P

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    I understand it a little. When we map it on plane, first we should observe that the best answer is on bottom convex. Then we can solve it recursive. And the init 2 endpoints are the best t and best c. Then we should find the best midpoint which has max distance to the line connected by the 2 endpoints. To find max distance is equal to find max area. Then the area can use c.x(b.x-a.x)-c.y*(b.y-a.y) + Constant. Then we change it to find min. Then it equal sum (c.x*(a.x-b.x)+c.y*(b.y-a.y)), which is minimum spanning tree.(finally we know how to do it).

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

      You map it on a plane (sum a, sum b) and get a convex figure. Also a*b=const is convex. And if you dont get minimal value every time you search for a better one you are getting closer.

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

This is the Best : http://codeforces.net/blog/entry/43886?#comment-285657

→ Reply
»
6 years ago, # |
  Vote: I like it -63 Vote: I do not like it

Would like to hear from tourist mnbvmar TLE FizzyDavid and other legends XD

→ Reply