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.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
Fibonacci with Matrix Expo did it for me. Knapsack would have probably worked too.
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.
The most interesting problem I have seen till date : https://www.codechef.com/SEPT17/problems/WEASELTX/
It provides a really beautiful linkup between graphs and combinatorics, I'm sure ur friends will like it.
geometry problems :P
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.
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.
I will give Number Theory problem.
Median Pyramid Hard
Wow, that's a really cool one!
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.
32C - Flea
Was also the problem that got me into CP
And so here come the story of the fastest-to-reach-IM in Vietnam.
i really liked this problem 1092D1 - Great Vova Wall (Version 1)
For me it was this problem about ants.
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.
any love for Your Ride Is Here?
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).
People ask you for question, you give them history books !
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.
I think I can do $$$O(n \log^2 n)$$$. Who knows whether it's optimal or not.
Let's first solve the simplified version of the problem where we sort arrays consisting of 0s and 1s. We're aiming at $$$O(n \log n)$$$ here. We'll use merge sort here: we'll sort two halves of the array recursively, and then merge two sorted subarrays. Merging is straightforward as it's really a single subarray reversal, which costs us $$$O(n)$$$ for an array of length $$$n$$$. Then, if $$$T_{01}(n)$$$ is the cost of sorting 01-arrays using this algorithm, we achieve the "cost complexity" $$$T_{01}(n) = 2T_{01}(n / 2) + O(n)$$$; that is, $$$T_{01}(n) = O(n \log n)$$$.
Now, we'll use the routine above to implement an efficient variant of quick sort in the general setting. Given an array of size $$$n$$$, we find its median. Create an auxilliary array that consist of $$$0$$$s for values smaller than median and $$$1$$$s for values greater than median (values equal to median can also be taken care of, but it's a small nuisance). We sort these values using the algorithm above, simultaneously applying the operations to the original array. What is the state of the original array after we sort the 01-array? It's actually partitioned by the median! Therefore, we can recursively sort two halves of the resulting array to finish the solution. What's the time complexity of the solution? In order to sort an array, we need to apply the algorithm above and run the recursive algorithm twice. We get $$$T(n) = 2T(n / 2) + O(n \log n)$$$, that is, $$$T(n) = O(n \log^2 n)$$$.
Perform a quick sort; use merge sort to partition the array into halves.
Nice problem!
Yep, that's what I would do. Maybe someone can do better?)
It's very interesting that the sorting one requires an exactly same idea from Median Pyramid Hard recommended by woookje. I love such optimizations, too :D
Maybe people can collect more problems that can be solved in a similar way? Zero-one principle of sorting networks first hit my mind.
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.
Interactive problems would be a good choice. They rarely require knowledge of algorithms.
I agree; in fact, when I wrote the question, I was thinking of problem D from this year's Code Jam qualification.
Really? It's not interesting, there are much better interactive problems.
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.
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.
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.
I have no clue why this was downvoted so much. I think this is quite a cool problem.
Haters gonna hate. Don't look for any sense in CF votes.
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.
Ah, I see. I suppose my opinion was positively influenced by the fact that I didn’t know the solution.
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.
I like this problem a lot — Trapping Rain Water 3D , but the preferrence depends a lot on personal skill, interests, problem solving history, etc.
997B - Roman Digits