Need Advice on How to Advance further in Competitive Coding

general
1

Basically, as the title says, I need advice on how do I progress further in competitive coding. It feels as if I have reached some dead end.

Problems-

1.Dynamic Programming

It is something, as I have seen, indispensable when you in competitive coding. I tried to learn it, I read the codechef tutorial (here) and the topcoder tutorial (here) and I am able to successfully identify the conditions/questions where this dynamic programming has to be applied. But I am stuck in the very next step, how to implement it? Either my solutions go all wrong, or are pseudo brute force. I tried to find some easy Q to solve, but am repetitively getting WA (no Correct Answer till now :frowning: )

So, I wanna know if-

  1. Anybody knows reaaaalllly novice Q on dynamic programming? I think I need to work it up from scratch, and once I get the momentum, I should be able to do fine.
  2. What approach did you guys use to tackle dynamic programming? Would you advise me any improvements in my approach (I basically learn by tutorials and then problem solving. )
  3. How do you know that, like, “Yes! NOW I am perfect in Dynamic Programming.”. Allow me to cite an illustration to explain myself-

If I get a Q now, to find sum of natural numbers till N using a for loop, I am like “Yeah, easy. Set loop from I=1 to n and add value of I”

So, are you guys also like this when dealing with dynamic programming Q? As in “Yeah! Simple. Just make a 2-D array, go on iterating …this…and that…and done.” Meaning, does dynamic programming seem really very easy when you people have finished it?

2.Graph Theory

It is a very unexplored area for me. I thought of dealing with it after I finish with Dynamic Programming. (My method is reading the book “Algorithmic Graph Theory and Sage” , and tutorials at topcoder here along with the book “Introduction to Algorithm”.)

Havent touched it yet, but it seems 10x tougher than dynamic programming by looks. My question here-

  1. Any tips for me on how I should start/approach this?
  2. Any language I should change/adopt. I currently use C. I know a little bit of Java too, and am learning python (from scratch- know basic input output only atm). My friends suggested me to switch to C++ for graph theory, so I want to know your opinions. Does graph theory’s easiness depend on language and is tough in C? And in case I should switch to C++, anywhere I can learn the language well? (The only thing I have is Hackerrank Problems on C++ which aim at teaching input output and various features. [link is here )

3.Permutations

This thing is a monster for me. I rally don’t know why, but whenever I see a Q on lines “Print the number of arrangements possible modulo 10^9+7” , my mind just blanks out. I cant even think of a brute force approach! I mean, how am I to do this?

Please have a look at the question here . It asked to print the number of arrangements possible module 10^9 +7. But, I literally blacked out that “How am I supposed to do it?” I am unable to advance after taking the inputs. And I got no idea how to prepare for these type of Questions. Any help would be appreciated !!

(PS: I tried my best to make the Q clear and informative. I referred to all related questions asked on these topics, especially Dynamic Programming, and decided to ask my question after that. I see many other people struggling with it too, and hence Links etc. were added so that anyone struggling with the topics can also refer.)

3 Likes
2

The simple answer to this question would be the following points:

1)Practice ,Practice and Practice…Most think that coding is some talent and its gifted,this is a huge misconception ,if you don’t believe it ,just go check the topcoders profile and look at the amount of practice they do.

2)Stick to some good sites ,Where you can learn the best,Like hackerrank,hackerearth,codechef.Solve the questions,of past contests ,because you will get a mixture of problems ,covering many variety of concepts: DP,graph,general math,etc.

3)If you’re stuck with any question look at the editorial understand and implement it yourself.

4)Have a team of three to two peer group and discuss amongst yourselves.

Thank you this should help you get a good amount of confidence.

2 Likes
3

Here a re a few tips (although I am not that good, but still … ):=

a) For dynamic programming, go through the classical problems, like Integer knapsack and kadane’s and understand how they really work.Most other DP problems are based on some variant of those, in the beginning level.
Also try the DP category in ahmed ali online judge.Go to the category’s section and do the problems, which are graded according to difficulty. Also , try to develop recurrences based on intuition and then add memoization.

b) Graph theory problems are no that difficult in the beginner level and are much easier to understand. I would recommend you to buy a book like, Skiena’s Algorithm Design manual. This is much more simple , to understand atleast than DP and this again uses some variants of well-known algorithms.

c) There is also a category where both graph and DP are mixed, they are complicated though.

d) Permutation problems are also a variation of DP most of the times.

And just to make it clear, I don’t know for very good competitive programmers , but DP is certainly tough, at least for me.But everything is relative, just remember that.Oh and don’t forget to really understand recursion, as it is very important. Also try some video lectures, and of course see MIT OCW 6.006 and 6.046 lecture series. 6.006 is for beginner while 6.046 is advanced.

2 Likes
4

First of all keep in mind that Competitive programming is a RACE, If you don’t code fast then there will be no use of it.

So first of all you must increase your speed whether it is your typing, or it is your thinking or manipulating the words of question etc.

  1. To begin with DP, You should have the idea about how to fill the table in bottom up approach such that each and every step would be able to give your next answer by looking from the previous step. Always try to generalize the question and make a recurrence relation to sort out this. There is no short hand trick to master in DP. To know more problems about this click here.
  2. Next if you are currently in C then please switch this to C++ which is more powerful and stable. And one of best thing is C++ is used world wide, even the tourist also used C++. Of course the reason is STL that are not available in C language. Topcoder has best tutorial to learn in depth about the STL.
  3. For graph theory you should have the basic knowledge of BFS and DFS, these are the backbone of whole concept of graph theory. And C++ is best language to start with. And Graph theory does not depend upon any language, you can make every program either in C/C++/Java/Python etc. But According to your question graph theory would becomes easy if you implement this in C++(because of inbuilt STL)
  4. For permutation, you must clear your whole concept in Combinatorics and Number theory. The question that you asked is one of the classic problem in DP, so please refer the editorial section of this.

At last Foster your skill in Data structure that are base of whole one!

Always remember one thing that Nothing is impossible in the world, Even the impossible itself says ‘i m possible’
Keep practicing and coding.

Practice makes a Man perfect

3 Likes
5

Have you read this tutorial in topcoder about C++ STL? Maybe this can convince you to change to C++.

For dp and graph, also try CLRS’s examples in the context. This book might be too well-known to be mentioned here but since you are asking for simple questions, those are the simplest non-trivial questions I can think of.

As already mentioned above, a permutation group of n elements has size n! which is an impossible growth rate to deal with. So permutation problem is usually just other types of problems disguised in a clever (or stupid) way.

1 Like
6

Thanks for recommendations in dp and the video lectures! Will surely check them out! :slight_smile:

7

The last line is awesome : Even the impossible itself says ‘i m possible’
kudos to u.

2 Likes
8

if i am not wrong, BFS= Breadth first Search and DFS= Depth First search?

Any place for Combinatorics and Number Theory? I am actually weak at permutation and combinations XD

9

Oh! Almost forgot! Kudos for the faster typing thing. But lol, it matters a lot for top coders. Let me reach that phase first XDDD

10

I have already provide both the links at codechef, geeksforgeek. Just click there and get your answer

11

My bad! Saw combinatorics a bit down! THANKS BUDDY!! :slight_smile:

12

I agree, especially with last part. Thanks for answer dear :slight_smile:

13

Thanks for the answer. I guess in Today’s Live Webinar for codechef , you were the instructor right??

14

haha, yea.
Hopefully it was not that terrible.

1 Like
15

It was quite wonderful to see the logic that I struggled for 3-4 days in maximizing the product if bitwise ‘&’.

Thanks a lot for your time and Effort.

Really appreciate the work that you are putting to make the CP community more Indulging.

Could you please ping your codeforces id I was unable to add you there as friend.
Thanks. :blush: :blush:

16

I believe it’s this.

1 Like
17

Thanks

18

I think I feel the same way.

I am good at Number theory , dp (not very much) , graph theory and so on but greedy , it just kills me.

in last educational round on codeforces I was able to solve E problem using dp and graph , and most of the time I am not even able to solve C or D problems which are from greedy tag.

I practice greedy problems but don’t feel as confident as I feel with number theory.

1 Like
19

@rajarshi_basu @bansal1232 I wanted to ask one thing. Will it be fine if I go for Graph theory (and some tree algorithms) first before getting into dynamic programming ?

1 Like