Thread: Are you good at contest-like programming problems?

  1. #1
    Registered User
    Join Date
    Jul 2010
    Posts
    55

    Are you good at contest-like programming problems?

    It takes me a while to figure out a possible solution or an algorithm so I consider myself between decent and mediocre, what about you?

  2. #2
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    I'm horrible. It usually takes me more than a few tries to come up with a decent answer. Sometimes I can't even find said decent answer and just give up. I consider myself a fail at those. But, truth be told, I don't think I'm particularly bright either. I'm your average joe.

    But "strangely enough" I'm good at dealing with everyday programming. I'm actually very good at my job, respected by my colleagues and superiors and I can't seem to remember having said more than once in my >20 year career "I can't do that". So my consolation goes to the fact I don't consider those programming contexts useful for anything other than giving the wrong idea about what is a good programmer.

    There. Feel much better now.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #3
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    I can be fairly quick to hack up a pretty poor solution that gets the job done. Something I consider an accomplishment considering the output is only be meant to run once in order to grade me and the overall time it takes for me to code it and run it once is significantly better than most people take to solve it the best possible way and run it once. (10 minutes coding + nanoseconds to run > 60 minutes coding + a few less nanoseconds to run)*

    As far as getting the best solution... nah, I suck. My professional experience of throwing together mindless interfaces for menial, highly-outdated manual tasks has definitely hindered my problem solving skills. Where I work all it takes to be a "guru" is to automate a process in which a woman is currently paging through a command-line terminal copying and pasting data line by line into an excel spreadsheet. Somebody get me a real job, please... ...



    ... Please ...

    * That's a comparison of accomplishment, not of time
    Sent from my iPadŽ

  4. #4
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    I was very much into it in my high school years (not much to do back then). Did a few hours a day for a year. Ranked 20 something in Canada in a national competition.

    They become repetitive after a while. There are a few classes of questions, and corresponding algorithms. It's just about how to adapt the algorithms to solve the questions.

    I can be fairly quick to hack up a pretty poor solution that gets the job done. Something I consider an accomplishment considering the output is only be meant to run once in order to grade me and the overall time it takes for me to code it and run it once is significantly better than most people take to solve it the best possible way and run it once. (10 minutes coding + nanoseconds to run > 60 minutes coding + a few less nanoseconds to run)*
    For contest questions there are usually an intuitive solution and an efficient solution. And the test cases will begin with a few small ones to test the correctness, and then a few long ones to test the efficiency. The long ones are usually weighted a lot more.

    An inefficient algorithm would only give you 1/3 to 1/2 of the points.

    The implementation is not nearly as important. They almost always make it so that the best implementation of the slow solution is still too slow, and a poor implementation of the fast solution is fast enough.

    A big part of time management is to decide if you want to code the simple solution first. If you are sure you can get the efficient one, coding the simple one is just wasting time. If not, it will earn you about half the points. Difficult choices.

  5. #5
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    My track record points to no.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    An inefficient algorithm would only give you 1/3 to 1/2 of the points.
    Wow, what kind of contest was that? The ones I competed in were different: you'd only get points if your program gave the right output given certain test input within a certain timeframe. If it takes too long - no points at all.

    I am quite okay at it. I can hack together a solution fairly quickly once I know the algorithm and usually there's one fairly easy question. So my team's strategy was always to find the easiest assignment while I typed the template we'd use for every assignment (includes, some macro's, etc). Then I'd join them find the easiest (and I was still usually the first to find the easiest solution as I seem to be very good at that for some reason, only glancing the test input/output), and then I'd type up the easiest. Quite often we were the first team, or at least among the first few, to have a correct answer.
    There were some hacky things I made though. Like... Using "throw variable;" where variable was the answer of the input, just to be able to quickly code it. A simply catch of an integer and output - and that's all ;-).

    Though I wasn't too great with my algorithmic knowledge. So I actually had to think of all algorithms myself... Which cost a great deal of time. I think I could've been great had I actually studied algorithms better...

  7. #7
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Sigh. I don't get it? Why has efficiency been placed above other (very large) areas of SE? Maintenance for example... I suppose it is harder to measure, but metrics exist!

  8. #8
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    Like zacs7 is saying, in most real programming there are a ton of things significantly more important than algorithm efficiency. Maintainability, modularity, portability, obfuscation (if necessary)... all of which has no dependencies outside of the program itself, where as algorithm efficiency could typically be fixed cheaper and faster with a hardware upgrade than with a more time-consuming and certainly more expensive development project.

    Take for example the JavaScript engines that you find in most modern web-browsers and how they're all competing to show that theirs can handle algorithms a millisecond or two faster than their competitors... consider how much resources they have dedicated towards improving their JavaScript engine for a marginal improvement that most people don't even notice; Meanwhile these browsers have real problems that should probably be tended to first.
    Sent from my iPadŽ

  9. #9
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    There's two other aspects to these contests/tests that I find also troubling when they are seen as some kind of gauge of programming capabilities.

    1.
    Everyday programming concerns itself mostly with the ability to solve problems in a reasonable amount of time and within reasonable expectations of performance, quality and readability. There's necessary a place for optimum performance, but it's a niche. The operative word in the vast majority of programming activities is "reasonableness".

    2.
    On the matter of problem solving capabilities of a programmer, there's also an important aspect to today's programming that is missed by these contest. Programming is today an almost entirely modular and reusable activity. The focus is really on problem solving and the methods achieved to solve a problem are secondary if point 1 is met. What this means in everyday programming is that a good programmer is expected to reuse known solutions and adapt them to the problem at hand, not to invent new algorithms if they can avoid it. Today one of problem solving biggest components is identifying the solution, these contests tend to do a near-miss by putting the emphasis on providing the solution.

    I don't wish to completely ignore some of their importance. I mean, more power to anyone who can look at the problems presented in these contests and come up with good, working code performing in record time. However, not being able to do that has definitely nothing to do with one's ability to program or even to outperform the contest winner.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  10. #10
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Wow, what kind of contest was that? The ones I competed in were different: you'd only get points if your program gave the right output given certain test input within a certain timeframe. If it takes too long - no points at all.
    I did the Canadian Computing Competition, and I believe the IOI (International Olympiad in Informatics) works like that, too.

    Anyways, the point is, efficiency matters.

    Sigh. I don't get it? Why has efficiency been placed above other (very large) areas of SE? Maintenance for example... I suppose it is harder to measure, but metrics exist!
    Because they are algorithmic competitions , not SE competitions (nor life competitions).

    I see them more like math contests, on a computer, with similar set of skills required.

    They aren't supposed to be a gauge of programming capabilities. They are a gauge of algorithmic and creative problem solving capabilities.

    Real world programming is a lot more boring IMHO.

    I, for one, have absolutely no interest in most parts of SE (testing, documentation, etc). Which probably means professional programming is not for me, and that's fine.

  11. #11
    Registered User
    Join Date
    Jul 2010
    Posts
    55
    Quote Originally Posted by cyberfish View Post
    I did the Canadian Computing Competition, and I believe the IOI (International Olympiad in Informatics) works like that, too.
    lol, I was actually doing some of those CCC problems, and the senior ones sure are hard, but what really surprises me is that High school students can solve those problems... they must really get some good programming classes in Canada.

  12. #12
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    It really depends on where in Canada.

    In Ontario/Quebec area I heard it's pretty good.

    Here in British Columbia we have 1 course in basic HTML/Javascript/Flash, that's about it. I had to learn it all on my own.

    The top 20 in the CCC are usually 80-90% from Ontario. I think I ranked the third in BC or something. Which is really not as impressive as it sounds, because BC high school education system doesn't make programmers at all. So it's pretty much among the hobbyists.

  13. #13
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Oh and I got really lucky on the competition day, too.

    I can usually get 3-4 problems from the senior set, but on that day I almost got all 5 because the 5th (hardest) problem was about minimax (an algorithm I've never seen in this kind of competitions, so most contestants are probably not prepared for it), and I happened to have done quite a bit of work in that field for a chess AI project, so it was very easy for me.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Another Begginner Contest (ALL Welcome for this One)
    By ILoveVectors in forum Contests Board
    Replies: 16
    Last Post: 09-04-2005, 08:49 PM
  2. New Contest #2 C/c++ Welcome
    By ILoveVectors in forum Contests Board
    Replies: 16
    Last Post: 09-02-2005, 09:28 PM
  3. Beginners Contest #2 For those who wanted more!!
    By ILoveVectors in forum Contests Board
    Replies: 16
    Last Post: 08-12-2005, 12:03 AM
  4. Almost Daily Contest #1
    By Prelude in forum Contests Board
    Replies: 32
    Last Post: 08-05-2003, 08:34 AM
  5. WANTED: Contest Master
    By kermi3 in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-23-2003, 10:15 PM