Skip to main content

Getting Started with Problem Solving!

What to follow for solving CP and/or Data Structures Problems? 

1. Type Code Fast!

“Quickly as Possible” - This boils down to how much you have practiced problem-solving and how fast are you able to code up the solution! Just improve your typing speed and practice typing on a daily basis. This is going to help you a lot. It helped me a lot to be more productive by solving more and more problems if I am able to type things faster.
Link to 10FastFingers - https://10fastfingers.com/

2. Identify the type of the problems quickly

This comes with practice and patience. As and when you start solving more and more problems, you would be able to identify properly which problem comes under what category. Which data structure would be suitable for what problems. Whether this problem belongs to Dynamic Programming or will the Greedy Algorithm work for this problem?

Should I use Insertion Sort here or the Merge Sort algorithm. Should I use a Balanced Binary Search Tree here or should I use a HashMap here? All these thoughts would automatically come to your mind as and when you start doing more and more questions and problems.

3. Just analyze what the hell have you written!

Once you have designed an algorithm to solve a particular problem in a programming contest,
you must then ask this question: Given the maximum input bound (usually given in a good
problem description), can the currently developed algorithm, with its time/space complexity,
pass the time/memory limit given for that particular problem?

There might be multiple ways to solve a given problem, choose the one that is - Correct, Fast, and Simple! The more the complication is, the tougher it gets to debug the code.

Modern computers process up to pow( 10, 8 ), operations in a few seconds. This is usually the limit in your coding rounds and you can take this number to analyze your algorithms.

Modern computers are quite fast and can process5 up to ≈ 100M (or 108; 1M = 1, 000, 000) operations in a few seconds. You can use this information to determine if your algorithm will run in time. For example, if the maximum input size n is 100K (or 105; 1K = 1, 000), and your current algorithm has a time complexity of O(n2), common sense (or your calculator) will inform you that (100K)2 or 1010 is a very large number that indicates that your algorithm will require (on the order of) hundreds of seconds to run. You will thus need to devise a faster (and also correct) algorithm to solve the problem. Suppose you find one that runs with time complexity of O(n log2 n). Now, your calculator will inform you that 105 log2 105 is just 1.7 × 106 and common sense dictates that the algorithm (which should now run in under a second) will likely be able to pass the time limit.

Master Programming Language

Which programming language should I learn? I would suggest going with C++ and Java! But then it is totally your choice if you wanna implement stuff in Python or any other language of your choice.

For me, I used to make use of C++ with STL and Java with Collection Framework for most of my questions. These helped me in both the Problem Solving as well as the Competitive Coding that is usually the first rounds in the campus placements.

I like implementing more and more questions related to LinkedList and Tree etc Data Structure in Java as Java has an inbuild Garbage Collector for retrieving back the memory that was assigned dynamically. However in C++ if you forget to use the delete operator or the free operator. Then that portion of the memory is lost and this phenomenon is called “Memory Leak” in C++.

What to do if I am not able to solve the questions?

If you are not able to solve a given problem, then learn more about it. Read the editorials. And try to understand others' code as to what approach they have used for solving the problem.

Do this only when you have given a good amount of try from your end. Don’t just see others solution and copy-paste it and submit from your account. This would give you momentary satisfaction seeing the Green Ticks, but in the long term, it is gonna affect you badly.

Good To Keep in Mind!

Familiarity with these bounds:

  • pow(2, 10) = 1, 024 ≈ pow(10. 3), pow(2, 20) = 1, 048, 576 ≈ pow(10, 6).

  • 32-bit signed integers (int) and 64-bit signed integers (long long) have upper
    limits of pow(2, 31)−1 ≈ 2×pow(2, 9) (safe for up to ≈ 9 decimal digits) and pow(2, 63)−1 ≈ 9×pow(10, 18) (safe for up to ≈ 18 decimal digits) respectively.

  • Unsigned integers can be used if only non-negative numbers are required. 32-bit
    unsigned integers (unsigned int) and 64-bit unsigned integers (unsigned long
    long) have upper limits of pow(2, 32)−1 ≈ 4×109 and pow(2, 64)−1 ≈ 1.8×pow(10, 9)respectively.

  • If you need to store integer ≥ pow(2, 64), use the Big Integer technique.

  • There are n! permutations and 2n subsets (or combinations) of n elements.

  • The best time complexity of a comparison-based sorting algorithm is Ω(n log2 n).

  • Usually, O(n log2 n) algorithms are sufficient to solve most contest problems.

  • The largest input size for typical programming contest problems must be < 1M. Beyond that, the time needed to read the input (the Input/Output routine) will
    be the bottleneck.

  • The typical year 2013 CPU can process 100M = pow(10, 8)operations in a few seconds.

Practice and More Practice!

Competitive programmers, like real athletes, must train regularly and keep ‘programming fit”.
Success comes as the result of continuous efforts to better yourself.



Labels:

Comments

Post a Comment

Popular posts from this blog

C++ Setup using VS Code and TDM-GCC Compiler (Windows)

You need to use this blog along with the YouTube Video present here for better understanding of the installation and the overall process.  YouTube Link -  https://youtu.be/l-4SH-QzbgI C++ Setup using VS Code and TDM-GCC Compiler (Windows) Using this setup we will be installing VS Code and TDM-GCC Compiler which is a good way to compile and run C++ programs in Windows. During my school days we used to execute programs in Turbo C++ compiler, which is now discontinued for good. The UI wasn't intiuitive at all for Turbo C++ software and it looked something like the one shown in the image below. But we do have great memories of programming in C++ using Turbo C++ Software in our school days. 😃 Turbo C++ (discontinued) UI Coming back, as for the Linux based systems (Ubuntu, Debian etc, I guess GCC already comes as part of the package. So Linux users can compile their C++ Programs from day 1 of their installations. 👍 To install GCC compiler on Mac OSX, you need to download and insta...
1 comment
Read more

How I tackled lack of motivation problem during my Placements?

Suffering from a lack of motivation? Well, that is something which is common to every human being out there at some point in time in their lives.  There are some facts that you need to grasp very well in your mind -  Everyone has got 24 hours.  Everyone faces a lack of motivation at some point in time.  No one can study for 24 hours straight.  Most of the people have the available resources to study around you. Example - Phone, Internet, Books, and Materials, etc.  Most people tend to waste their time in mobile games, series, movies, etc.  Not everyone gets up at 4 o clock and starts reading Data Structures and Algorithms and starts coding right away.  Not everyone is god gifted.  So, if this is the case with everyone, then where does the difference actually come up? How are some people more productive and achieve more as compared to others?  The difference comes up in the way how some have trained their mind to react to situations and t...
Post a Comment
Read more

What if I am not from CSE or ISE? Does that affect my placement in any way, even if I am good?

The bitter truth about placements in UVCE is - for other branches like Mechanical, Electrical, etc. There are not a lot of core companies coming to the college for placements. Not every second or third company coming to college is a core company. Most of them are for Software Engineering profiles or profiles related to computer science fields. Even if the core companies come for placements, the number of students they usually pick is very less. Just confirm with the Placement Office at your college and ask about Placement Opportunities for the branch that you are currently in. So, my simple advice to all the juniors out there in other branches of engineering would be -  Start learning to code.  There will be more details provided to you, but for security reasons, I have hidden them here.  The list above shows the eligible branches for the respective companies . Most of them will be having a job role which involves computers, coding, and all computer...
Post a Comment
Read more