lmn0x4F's blog

Very useful concepts I haven't seen here
By lmn0x4F, history, 5 years ago, In English

I wanted to finally reach red (after being stuck at orange for some years now) and I asked myself what should I study. I thought I should review one of the most important things I learned, that helped me go from expert to master very quickly, but then I realized I've never seen people referencing that resource here in codeforces, which seems crazy to me.

The main ideas are presented in a paper titled Pessimal Algorithms and Simplexity Analysis by Andrei Broder and Jorge Stolfi, which is available online for free.

I wanted to present this old paper to codeforces, urge you to read it if you haven't (it's just 5 pages long), and, if you have read it, ask you if you have benefited from these very useful techniques and concepts too (I'm sure you have, it's just that I'm perplexed I haven't seen it mentioned here before).

I'm confident that studying again these concepts will make reaching red easy (and make me a better programmer in general)

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

»
5 years ago, # |
  Vote: I like it -32 Vote: I do not like it

Do you really think that reading these 5 pages will make you red?

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

This problem has a long and rich history, whose beginnings can be traced far back, almost certainly to a time before the establishment of reluctant algorithmics as a recognised discipline in the second half of last Wednesday.

This piece of knowledge was all that was standing between me and a jar of Nutella.

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

Is this a paper describing actually useful stuff or is it a joke? I can't tell yet. Edit: Holy crap my mind is blown.

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

How to solve any problem: if you attempt to reluctantly construct a pessimal algorithm, you will instantly find an efficient one.

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

    The problems in the article are quite straightforward and well-known, I think. Is there an example of a problem that is easier to solve by constructing a pessimal algorithm and using its idea to come up with an efficient one? I'm sorry but I can only vaguely imagine how this can be used, and will be very glad if you show one of its applications.

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

      It can be used to practice up to the nutella level in 'sense of humor ranking'. Just read it each day until the end of the time... sorry end of the paper. "Gordon Lack, April 2000."

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

I like to think that I can power through most books and papers, but this one got me. Hope I didn't miss out on too much.

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

I don't understand the purpose of this paper, I tried to read it several times (My English is poor, I don't understand difficult words) Can someone please explain the purpose of this paper briefly?

→ Reply