Friday, October 04, 2013

More answers to Quora questions.

Weeks ago I wrote a post: vexorian answers quora questions. It was a fun blog post to wire it, so I am going to answer some more:

What are the things you wish you knew when you started programming for the first time?

In general:

  • Speed sucks. There will be some situations in which speed matters, and it is good to have a language that is not like super ultra slow. But unless you have very specialized applications, low level speed should never be your primary objective. (high level optimization is cool though)
  • You'll spend more time reading your code than typing it. So make it readable for god's sake.

For "Competitive programming" :

  • There is no money in participating in contests. There is good money in working behind the scenes though.
  • You did not solve a problem until you code a passing solution. No, you didn't. No, just knowing what the solution is is not the same as solving the problem.
  • It is pointless to spend weeks trying to come up with solutions on your own. If you can't solve a (practice) problem after some hours, search for the solution.
  • Similarly, it is pointless to look for answers immediately after reading a problem's statement. Always give yourself a chance to at least try solving it.
  • You need a plugin to code in TopCoder. Really, you do.

(topcoder) Do you use the Coding Area to code your solution or a separate IDE?

IDEs are the spawn of Satan, but the arena is very limited. You need a plugin. Until recently I've been using a modded KawigiEdit. Lately I am using Greed. I use jEdit to edit code. Each programmer needs a specific set of editor features and in my case I prefer to have fewer features as big editors "get in the way".

How should I practice so that I will be at a level where I can approach TopCoder's Div1-500 problems with confidence?

Sink or swim. What I did when I noticed I was getting stuck in division 1 easy difficulty was to open the div 1 500 first. This way I was forced to solve a div1 medium every once in a while or else my rating would be destroyed. Plus I eventually got used to at least being able to try this slot. I know that this doesn't help your issue about [confidence], because you'll need to at least once try to solve a div1 500 during a match knowing that you don't have a confidence to solve them. But you don't really need the confidence.

Difficulty is not static though, with time problems became tougher and I have had to repeat the effort more than once.

Is it better to learn algorithms from a book or by solving online problems?

I've been meaning to say something about the Books topic in this blog for a while now. Books have not really helped me that much. Whenever people ask me about books, I bring the two closest things to a book that helped me, like Programming Challenger and CLRS. But the other day I learned that I don't even know the author's name for Programming Challenger.

In my case, I think that reading online resources (Editorials, tutorials, howtos, wikipedia pages, etc) and asking questions in forums was far, far more useful than books. Any good contest site should have a resource like that. Try to solve a problem, then after the contest, ask how to solve it, read editorials and any material suggested by people explaining the problem. But if you like getting theory from books, feel free to do it.

Why do a lot of successful competitive programmers not participate actively on CodeChef but participate often on sites like TopCoder and Codeforces?

I don't know about successful coders, but I can speak for myself.

  • I don't have time to participate in all contests released in a month, so I have to put priorities.
  • I choose TopCoder as my first priority, because the 75 minutes format is a lot more comfortable than longer format, and because I would likely have to solve those problems anyway because of my job.
  • Second priority is Codeforces because it is has a very competitive userbase. Although it sort of bores me some times.
  • Why Codeforces and not Codechef? The Codechef format is not helpful. Spending 15 days on a contest would really kill me and leave me with no time for other things. The cook-offs sound ok, but they happen only once a month, and on Sundays, and at a very bad time of the day for me.

How should programmers place their hands on the keyboard in order to increase the typing speed

Uh? Unless you have serious difficulty typing at a decent pace, you shouldn't care that much about your typing speed. Other factors are more important, like thinking of the algorithm you need to code.

If you do lack typing skill (For example, you need to see the keyboard while you are typing), then there are good resources to learn typing out there in the web and practice makes best. typeracer offers both a place where you can practice typing competitively and the forum is a good entry point to the part of the internet that cares about typing speed and has tips/etc.

I learned to type in school around 18 years ago. They made do typing in typewriters, if you got something wrong, you had to restart over. Yeah.

Do you find skills you achieved during programming contests to be useful outside of them?

I personally wouldn't have learned C++ nearly as well as I had without programming contests. Programming contests give you a very good opportunity not just to code solutions to known problems. but to make mistakes when coding those solutions. Because the problems are well-defined, we can run your solutions against a fixed-tester and find a plethora of implementation bugs. Constantly. This will teach you about what things can fail, what pitfalls your language has. What sort of mistakes you are likely to make.

Rant: My god, look at the answers to this question. Read this: Regarding the smug opposition to programming contests. Specially the anonymous guy who thinks adding a competitive layer to programming is to "prostitute" programming.

Programming contests are fun and that should be your first priority. There are, however, some nice skills you can learn through them. It is true that they are skills you can learn in other ways like making contributions to open source software, the demoscene, modding, making your own apps, building robots, etc*. To each their own, if you have more fun at competitive programming than in those areas, then programming contests are a good way for you to develop these skills. The trick to programming is to pick an area you are passionate about and develop your skills there. It is incredibly stupid to be afraid to pick areas of programming that do not have the approval from random people in question sites...

(*But of course not college! lol!. I am talking about skills that require creative coding ability, things college cannot really teach (sorry!) ) Speaking of college, while a good college should be better at teaching you CS theory, the programming contest world is probably a better place to learn CS theory than 99% of colleges.

What do you do when your code is not accepted but you don't find a test case that makes it fail?

If you can't really find any test case, then you are wasting your time solving problems in a judge site that doesn't share test cases. That is very bad for your productivity. Avoid those sites like the plague they are. While there are urban myths about how making you find the wrong test case by yourself will make you better at programming, you should consider that transparency is very importance. Have you stopped to think, what if? What if your code is actually correct? What if the judge was wrong? What if that's the reason you can't find a wrong test case? Transparency = guarantees. If somebody thinks he will get better by guessing the test case he is failing, he can just not take a look at the test cases.

If your problem is different and you actually know that your code is failing a case, but it is a very complicated one so it doesn't tell you much. Then you'll need to get creative.

  • First of all, why is it that apparently none of the simple test cases was wrong? Maybe your code has issues that are specific to large test cases? E.g: A memory write out of bounds of an array could be corrupting your memory. E.g.2: Overflow.
  • In topcoder, sometimes some large cases of the system tests are first in order to other, simpler cases. But since system tests finish running once they find a wrong test case, you cannot find out the simpler cases. What I do sometimes is manually pre-code the results to each complex case until I find a simple case that executes after them and is also wrong.
  • Read editorial / tutorial and try solving with the solution described in there . If the solution in the editorial is the same as yours then you probably need to inspect each line for possible errors. That is sometimes all I can do, verify each line, sometimes multiple times. Sometimes I fall sleep while doing it.
  • Ask in the forums. But please, help us help you. You need to explain your solution and why do you think it should be correct. If you don't have a proof that your solution should work, then it probably won't work. Probably its bugs are not small implementation mistakes but the whole algorithm is wrong. Sometimes it is better to just redo the work. If you have been having issues proving a solution is correct, then maybe you should try to prove it is wrong. Unfortunately this involves finding counter-examples and that's exactly what you are looking for.
  • If everything fails: Grab somebody else's correct code and generate random, small, test cases until you find one that makes your solution give a wrong solution. Maybe you will finally find something.
  • If that fails, give up.

Why is Python not allowed as one of the languages for ICPC?

I'd say some tournaments just can't keep up :/

How can I print 1 to 100 in C++ without a loop, GOTO or recursion?

Lambda power (requires c++11):

#include<functional>
#include<iostream>
using namespace std;

int x = 0;
void q()
{
    if (x != 100) {
        cout << (++x) << endl;
    }
}

// t(q())    returns a function that calls q() two times.
// t(t(q())) returns a function that calls t(q()) two times == q() four times
// ...
function<void()> t( function<void()> g) {
    return [&g] {
        g();g();
    };
}

int main()
{
    // call q() 128 times:
    t(t(t(t(t(t(t(q)))))))();
    return 0;
}

Laziness power:

#include <iostream>
using namespace std;

int main()
{
     cout << "Please type all numbers from 1 to 100 in a single line:"<<endl;
     string x;
     getline(cin, x);
     cout << x; //If user does his/her job correctly, this statement will print the numbers
     return 0;

}

1 comment :

como eu nao sabia said...

Great reading youur blog post