Kognition's blog

Problem to Create Interest in Competitive Programming
By Kognition, history, 6 years ago, In English

If you had a smart friend who liked puzzles, and you could choose one problem that you thought was accessible and interesting enough to get them curious about competitive programming, what problem would you choose?

Edit: To be clear, I’m curious about specific problems, not just general topics.

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

Comments Comments (36)
| Write comment?
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Fibonacci with Matrix Expo did it for me. Knapsack would have probably worked too.

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

    I agree that Fibonacci with Matrix Expo is really cool when you first see it. That said, if just presented with the problem, i.e. (given this recurrence, find the $$$n$$$'th term), one could get a closed form with generating functions and might not immediately see why fast matrix exponentiation is, in fact, really cool and more generally useful.

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

geometry problems :P

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

For me, I think the most important and interest thing is that you should use computer to calculate complex processes to get final result. So give problem which is hard to describe exact answer directly, then he or she will have interest in competitive programming.

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

I agree with a previous commenter; Fibonacci with Matrix Expo similarly got me hooked.

Combi in general was something I found interesting from Math competitions, but with a computer, so many more avenues are opened and much more interesting problems can be asked.

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

I will give Number Theory problem.

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

Median Pyramid Hard

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

When I started competitive programming I was absolutely thrilled by problem "Garden" from IOI 2005. You start by the trivial $$$O(N^{10})$$$, come up with smart ideas to make it $$$O(N^5)$$$, and optimize to $$$O(N^4)$$$ and finally $$$O(N^3)$$$ by discovering new optimizations that have general implications.

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

32C - Flea

Was also the problem that got me into CP

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

    And so here come the story of the fastest-to-reach-IM in Vietnam.

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

i really liked this problem 1092D1 - Great Vova Wall (Version 1)

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

For me it was this problem about ants.

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

    Ah yes, that's a nice one. I first heard the problem presented where you had to prove (noninductively) that all the ants would fall off the log.

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

any love for Your Ride Is Here?

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

This is an interesting question but also a strange one. Do you want a reaction like "you can solve this? This is incredible" or for a person to understand and maybe be able to solve the problem? If second — do this person know about time complexity? If yes, this is incredible, why would anyone know about time complexity outside of CP? If no, I don't believe that you can show relation to programming, it should be pure mathematical problem, which is not what you want, I suppose.

I guess there is some middle ground like being able to grasp the problem statement and think about the problem a little bit, but hardly coming up with a solution.

Anyway, my recommendations (probably too hard for someone not in CP, especially the first one, I mean tourist and Petr didn't solve that one, though my classmate did): TCO16 Semifinal2 Easy, TCO17 2C Easy. Wow, two problems from TopCoder from a person who don't like TopCoder. That's embarrassing.

Also kinda theoretical problem if they know about complexity: Given an array of length $$$n$$$, you can take a segment and reverse it. The cost of this operation is length of reversed segment. Come up with an algorithm that sorts the array spending $$$o(n^{2})$$$ (faster than bubble sort. I don't know optimal complexity, but I do have pretty good one). To all: feel free to write your algorithms in comments to this one (using spoilers, of course).

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

    People ask you for question, you give them history books !

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

      I still recommend you to stick to "just Petr" comments, because otherwise you always write something stupid. On the other hand, Petr is not stupid.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it
    Complexity
    Solution
    tl;dr

    Nice problem!

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

    So, my intended audience would probably have some basic knowledge about time complexity (perhaps they wouldn't be able to do certain things like prove Manacher's is $$$O(n)$$$ or something, but they would probably be able to reason about some pretty simple data structure complexities). The middle ground you presented sounds accurate to what I was looking for. That said, you can interpret the question in whatever way you are comfortable with answering; I enjoyed the problems you shared.

    Also, time complexity is really not specific to CP; most algorithm and discrete math classes in the US teach about time complexity, and to be honest I would be astounded if it was not taught in Computer Science classes in Russia, which has a much better STEM education system than the US.

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

Interactive problems would be a good choice. They rarely require knowledge of algorithms.

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

    I agree; in fact, when I wrote the question, I was thinking of problem D from this year's Code Jam qualification.

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

      Really? It's not interesting, there are much better interactive problems.

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

        That's unfortunate that you didn't think it was interesting; I suppose it was probably too easy for you. It was nontrivial for me and the solution was pretty and simple enough that I could present it to my friends without much background, and still see the "Oh!" looks on their faces afterward.

        Perhaps you'd like to share some of your favorite interactive problems? Although not interactive, I enjoyed your segment reversal problem from above.

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

baseball elimination problem :D

How you solve it using Graph and Max flow out of nothing really amazed me the first time I read about it.

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

This problem from NCPC is rather interesting (realistic): you have $$$N$$$ teams, each with $$$M$$$ people, and you want to run a tournament where each pair of contestants from different teams plays exactly one game against each other, with the minimum number of rounds — $$$M(N-1)+1$$$ is enough. In one round, each player can play one game. The goal is to make a tournament table — who should play against whom in each round.

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

    I have no clue why this was downvoted so much. I think this is quite a cool problem.

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

      Haters gonna hate. Don't look for any sense in CF votes.

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

      I think this problem is way too hard, hard enough thst copy-pasting Vizing’s coloring algo is a most sensible choice. I can imagine someone liking this problem but it’s not in my taste.

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

        Ah, I see. I suppose my opinion was positively influenced by the fact that I didn’t know the solution.

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

        I didn't mean that it's a good problem to give someone to solve. It's something people without experience in competitive programming can connect with and that can serve as an entry to the topic. From real-life experience with such people, I'm pretty sure a "smart friend who likes puzzles" will find the sieve of Eratosthenes way too hard, even though it's trivial for us.

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

I like this problem a lot — Trapping Rain Water 3D , but the preferrence depends a lot on personal skill, interests, problem solving history, etc.

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

997B - Roman Digits

→ Reply