Petr's blog

An almost Rapid week
By Petr, history, 7 years ago, In English

http://petr-mitrichev.blogspot.com/2017/05/an-almost-rapid-week.html

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

Comments Comments (10)
| Write comment?
»
7 years ago, # |
  Vote: I like it +79 Vote: I do not like it

"With the only successful solution to problem E coming from a contestant with no other solved problems..."

"a contestant"

radoslav11 so close.

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

    :")

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

    CF, please add sad reactions :(

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

    Sorry..but can you please explain what 'a contestant' meant?

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

      A contestant means someone who participates in a contest

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

          Yes, he is not a real contestant. How dare he not solve all problems but just the hardest one!

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

      Actually the joke isn't centered around what "a contestant" means. The joke is people who read Petr's blog hope that one day the will get mentioned. So ___ does something unique and worth mentioning... but he doesn't get mentioned by name! So he got "so close" but not close enough. ¯\_(ツ)_/¯

      Sorry I made the joke a bit obtuse but it was a tradeoff between making it more understandable and making the delivery shorter and sharper.

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

For some reason my comment disappeared so I will add it here: it's easier(in my opinion) way to find vertices ABC such that AB and AC are edges and BC is not. Let A — the vertex of highest degree, iterate over B and C — its neighbours. Then if BC is not an edge — stop. It's O(M) checks in a set. If you didn't find such triangle, then all neighbours of A has same degree as A and then graph is clique

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

    Iterating over all three will probably also work. I can understand why it's but I don't know any case where it's greater than O(M1.5)

    → Reply