This blog post started with a personal search for such a post. I have a coding interview in an hour, and I was searching for a good medium post, which can point me out some basic concepts of Competitive Coding so that I can brush up just in time. Inability to find such a post gave me the motivation to write one myself. This blog is mainly for my personal use in the future, and maybe the title is more of a fancy one that a summarizing one. Anyway, so bottom-line is, this is a post to take a look just before you are giving a coding competition. I will try to list down the most commonly used strategies to tackle a Codeforces Round 2 questions or a similar level based on my experience. Hence that being summarized, let’s get our hands dirty with some algorithm. So the list, * Doesn’t show up that often in a question but always a good deal to look into graph traversal and how to use priority queue. And God, is such an angel, shows up almost everywhere. to an implementation. Dijkstra’s shortest path: Priority Queue Link * and Again, a small code but the use-case in numerous. will give you a brief overview. If you’ve done CP(Competitive Programming), you will again see this notorious guy coming up everywhere. GCD Inverse Modular: The link * This is like one of the standard ones every one likes to ask you in a while. The idea of dynamic programming is simple. Why calculate something twice? If you see that in the problem statement, few repetitive calculations can be avoided, a high chance is that DP will get you the desired complexity. and will help you get the flavor. Dynamic Programming: Fibonacci Longest Palindrome * I always think this a gut feeling approach. Most of the time, you will end up missing some small corner cases while using this and won’t get the correct answer. Nevertheless, always, at least for an initial 5 min, think a possible greedy approach and back-test against some test-cases. If you are good with coding and implementation, I’ll suggest to code up and give an upload. Finger’s crossed. Greedy: * More than often, you are asked to find a minimum or a maximum number satisfying some property. Chances are, the property has a sequence property. f(x) => f(x+1) but f(x+1) does not imply f(x). This is best exploited by binary search. Easy implementation:- Binary Search: — — — — 1. Convert all input data to . global variable — — — — 2. Make a for property f. check function — — — — 3. function to find the answer Binary search * Just some randoms that many times show up. I will request readers to comment here on some of their personal favorites observed. Sorting, Sieve of Eratosthenes …. : * As it might have been clear by now, I am no expert in the field, more of a hacker. And I just know that stack can be answer to questions at times. I don’t know when and many times I get the answer wrong. * This one seems silly, but at some of the times, I just multiply two integers that go out of range and have wrong answers. So folks, if there is no limit of memory, use Long Long int. * This one’s easy. No overselling, but this guy is a goto. Unless your question involves string manipulation, then is the answer. I know it will be slow, but a comfortable place to start and who knows, the question setter was easy on you with the test-cases. * One of the easiest ways to traverse a tree, and if you are storing the right variables, many times, you will get the answer quicker than you think. Some Advance topics that may be helpful, not always but who knows, Stack: LONG LONG INT: ALWAYS, C++14: python BFS and DFS: Min Cut Max Flow Grundy Number Segment Tree Union Find : Specially for number of connected components. May the Force be with you.

Flow

Check my website

Read My Stories

Too Long; Didn't Read

Questions about cloud security? Get answers here.

A Hacker's Guide to Competitive Programming

Too Long; Didn't Read

Coin Mentioned

Rupesh

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

A Hacker's Guide to Competitive Programming

Too Long; Didn't Read

Coin Mentioned

Rupesh

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES