Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Competitive Programming
#1
Competitive programming (CP) is a kind of sport where you solve problems with programs. That is, you are given problems and you attempt to make programs that solve those problems.

An extremely easy example would be the addition of 2 numbers problem, you are given 2 numbers and your program will need to output the added value of the 2 numbers. Note that we don't necessarily know what the 2 numbers will be, your program will be required to output the correct answer for any inputs they may test your program with. You won't know what those inputs will be, only the range (the input will be within what we call the given constraints, for example 0 <= a, b, <= 10^9)

There are competitions for solving these problems, where you get points for each problems that you solve, and you get more points for the less time and attempts (program submissions) you take to solve them. Most of these competitions are online through websites, though some on-site competitions exist, like the ICPC which is for undergrads.

But even if you don't choose to compete and solve problems under the pressure of time limits, you can also of course just solve the problems outside contest, as an exercise, which can actually be quite fun too, because these problems tend to be quite interesting, as the nature of the problem can vary quite greatly.

What's so great about these problems, in my opinion, is because for the most part, it requires logical thinking than just knowledge, making them more like riddles instead of trivia. You get to be creative and get rewarded for innovations, rather than punished for not knowing or memorizing things. It's not like math and physics exams in a lot of places where most of your effort goes to memorizing methods and formulas. Knowledge of algorithms and data structures will often be necessary, but the hardest part is usually on the innovative thinking on how we can use these things to solve the problem. There's usually no problem that only requires you to implement a well-known algorithm - there'll be a catch, you'll have to adapt it to the problem at the very least, if not create your own algorithms.

So some of you may know that I used to make games as a main hobby (Jiggshot and more), but what I eventually realized is that I kind of cut corners and avoid the hard stuff when making games - that is, I usually only make games that are easy to program. I ended up not even knowing some basic stuff, like Stacks. In part because I never needed them, but also because to some extent I steered away from the situations that would require me to learn new stuff.

But then I started doing competitive programming and this made me learn a lot of stuff - mostly data structures and algorithms and their implementations, and now a lot of stuff that used to be intimidating, like recursive functions and pathfinding, becomes a lot less so. There's a lot of controversy regarding whether competitive programming helps you improve, but in my experience, it's made me learn a ton of stuff. (People often argue it makes you write unreadable code, skip good practices and not think of the long term planning - but I think that only happens if you don't distinguish between coding for CP and for projects)

So yeah, this is what I've been up to lately, I think it's cool and you might wanna give it a try if you're into programming.

Here's an easy problem example so you can see what it's like:
https://codeforces.com/problemset/problem/996/A

That website, Codeforces, is my number one recommended website for CP problems and contests, it has thousands of high quality, varied problems, and you can sort by difficulty and tags to practice the kind of problem you want. The difficulty ratings are also pretty accurate in most cases, and they host contests consistently like 2 times a week introducing new problems everytime.

Most people use C++, some use Java (including me), only a few use Python for CP.

Anyway, let me know if you give it a try and what you think of it ^^
I don't have a sicknature
YouTube (original music) | Newgrounds (games)
Reply
#2
CP? That's a rather unfortunate acronym isn't it?
[-] The following 1 user says Thank You to FinalCheetah for this post:
  • aaaaaa123456789
Reply
#3
(2019-03-22 16:35:48)FinalCheetah Wrote: CP? That's a rather unfortunate acronym isn't it?

I didn't realize. Now I can't unsee it.
[Image: 5VbzghW.png]
I don't have a sicknature
YouTube (original music) | Newgrounds (games)
Reply
#4
I've tried stuff like this, but I don't really find it fun. I enjoy making programs that I would use myself, rather than rushing to solve a random puzzle.
[Image: tumblr_nddxf2XzYY1tvf9p0o1_400.gif]
Reply
#5
If I had joined it earlier, it would have been a good experience for future use. Why the heck did I quit programming competition project at that time.... Why didn't I find it fun.... Why did I become alone there.... Darn....
[-] The following 1 user says Thank You to . for this post:
  • Ali
Reply
#6
Quote:Allen has a LOT of money. He has n dollars in the bank. For security reasons, he wants to withdraw it in cash (we will not disclose the reasons here). The denominations for dollar bills are 1, 5, 10, 20, 100. What is the minimum number of bills Allen could receive after withdrawing his entire balance?

This isn't a programming problem. This is a math problem. The only programming involved is reading a number from standard input, doing a trivial calculation on it and printing the result from standard output — something even a complete beginner can achieve.

As for the solution, it is purely math-based. It relies on the fact that every number on that list is a multiple of the previous one, which in turn implies that there is no advantage using smaller bills when you can use larger ones. (This is not true when this property doesn't hold: consider the case of withdrawing $12 using $1, $4 and $5 notes — the best solution is to use three $4 notes, and any attempt to introduce $5 notes results in a larger number of notes being used.)
Thus, the best solution uses as many $100 notes as possible, and distributes the rest in change efficiently, using $20 notes first, and so on. There is a simple formula for this solution, assuming that division rounds down and that remainder(x, y) is the remainder of x divided by y:

bills = n / 100 + remainder(n, 100) / 20 + remainder(n, 20) / 10 + remainder(n, 10) / 5 + remainder(n, 5)

A program would simply have to calculate this expression (which is, again, completely trivial) and output it. There are no challenges in programming involved at all.
If you need to contact me for any reason, or if you have any questions, concerns, problems or requests, message me here or email me at aaaaaa123456789@acidch.at.

This forum has been around for (loading...)
Reply
#7
(2019-03-23 20:58:05)aaaaaa123456789 Wrote: snip - but i actually read it all ok

Yes, it's a very easy problem even a beginner can solve; that's kind of the point why I chose that one for the post, since if you were to start at a difficult problem, there's a chance that you fail simply because you don't know how to submit the program correctly yet. The point of doing a trivial problem first is to know how the website works, how can you submit your solution, kind of like a Hello World test.

This one probably sounds more like a math problem because of how easy it is the to mathematically express the obvious solution, and doesn't really require much programming knowledge, but more difficult problems deal with programming concepts more exclusive to the programming and computer science field, require you to analyze the nature of the problem, innovate algorithms that work for the situation. If coming up with methods to solve problems and implementing them into code doesn't make a programming challenge, I don't know what is. (Maybe project jams that require more long-term architecture, but problem solving too is an essential part of programming)

Ultimately, programming is a kind of maths because of the certain, and of course, mathematical nature of how the program works. (i.e. code is mostly just commands to execute calculations and computations - mathematically) But maybe you'll see them less as math problems once you see that the less trivial problems that mostly deal with CS concepts.

For example, here's one of my favorite, less trivial problems:
https://codeforces.com/contest/225/problem/C - a dynamic programming problem

Or take this one, which is kind of more logic than numerical calculation:
http://judge.u-aizu.ac.jp/onlinejudge/de...sp?id=1122 - in short, you're given guess attempts of someone playing the Mastermind code-breaker game and your program must deduce from them what would then be the answer, if such a deduction is possible.

https://codeforces.com/contest/400/problem/D - more complex problem that deals with graphs

Some problems are best solved through simulation, some require more rigorous implementation while others place their difficulty on the brainstorming and realizing/deducing properties part. Maybe the implementation-heavy problems would fit your idea of "programming challenge" more.

(Side note - Codeforces problems tend to be more straightforward, less implementation-heavy and relies on you realizing/deducing properties, while ICPC problems are more complex and often more implementation-heavy. This is because of the time length of their respective contests, Codeforces contests are short so the challenge is more focused on the thinking than coding)
I don't have a sicknature
YouTube (original music) | Newgrounds (games)
Reply




Users browsing this thread: 1 Guest(s)