fofao_funk's blog

By fofao_funk, history, 19 months ago, ,

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.

• +77

 » 19 months ago, # |   -20
•  » » 19 months ago, # ^ |   0 Ok, what about it isn't beautiful?
•  » » » 19 months ago, # ^ |   -8 It is beautiful, just idiots on cf too lazy to read it
•  » » » » 19 months ago, # ^ |   +6 I hardly understand it, but god damn.
•  » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   0 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.
 » 19 months ago, # |   +27 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.
•  » » 19 months ago, # ^ |   0 Which problem?
•  » » » 19 months ago, # ^ |   +3 It seems from the link it is K.
 » 19 months ago, # |   +106 This div2A 31086095 from round 439, AC in 5 characters
•  » » 19 months ago, # ^ |   -26 I can't believe there's a problem with such test cases
•  » » » 19 months ago, # ^ |   +12 The test cases aren't weak, the answer is Karen for any input
•  » » » » 19 months ago, # ^ |   +7 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.
 » 19 months ago, # |   +29
•  » » 19 months ago, # ^ |   +101 using namespace std;
 » 19 months ago, # |   0 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 :)?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +21 One of the authors solutions on Python: Solutionn = int(input()) print((n - 4) // 2) 
•  » » » 19 months ago, # ^ |   0 Wow! It's very important geometry point to solve this problem. Thank you very much for pointing this way out for us <3.
 » 19 months ago, # |   +9 It is the most beautiful, greedy solution that I've ever seen.
 » 19 months ago, # |   +49 IOI 2006 joining points: Solution
•  » » 19 months ago, # ^ |   +57 I agree, this is one of the most beautiful problems I have ever seen.
 » 19 months ago, # |   +21 this 22059230.
•  » » 19 months ago, # ^ |   +23 Ctrl+D Approach
•  » » » 19 months ago, # ^ |   +22 When there are so many nested for loops you don't even care about indenting them
•  » » » » 19 months ago, # ^ |   0 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"
 » 19 months ago, # | ← Rev. 2 →   0 The following queue-based solution of this recent problem 999C - Alphabetic Removals is among the most elegant solutions I have ever written. 45174979
 » 19 months ago, # |   +3 How about the easiest problem ever?)
 » 19 months ago, # | ← Rev. 2 →   +6 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.
 » 19 months ago, # | ← Rev. 3 →   +73 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. TipTry to find most optimal solutions just for weights ai and just for weights bi. What about representing it on a plane?
•  » » 19 months ago, # ^ |   +21 It's from BalkanOI 2011, me and Radewoosh are also big fans of this problem.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Ok, now two out of my three favorite problems are mentioned here. I am waiting for someone to post the third one ;P
•  » » » 19 months ago, # ^ |   +3
•  » » 19 months ago, # ^ | ← Rev. 3 →   +1 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).
•  » » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   +6 This is the Best : http://codeforces.com/blog/entry/43886?#comment-285657
 » 19 months ago, # |   -63 Would like to hear from tourist mnbvmar fjzzq2002 FizzyDavid and other legends XD
•  » » 19 months ago, # ^ |   0 Do you mean tzuyu_chou?
•  » » » 19 months ago, # ^ |   0 Do you mean Iightcode? I mean, if we are talking about true legend that is