Back to Competitive Programming

2 minute read

Introduction

Competitive Programming and Number Theory are quite interesting things to do in spare time. And a chaotic mind such as my own always needs a break from the mundane things of reality and life every once in a while. However, don’t be fooled, competitive programming can get boring as hell sometimes.

Back in college, when I was first introduced to competitive programming, we were a select few students who were fascinated and even fewer of us, myself excluding unfortunately, were in it for the long run. Its quite helpful for placements, helps you brush up a few concepts on mathematics, and who knows, might be even useful to you in your job as well.

Current Status

Since I’m restarting, I thought of best trying my hand at Project Euler first. The problems are designed to teach a person to look for efficient solutions that can solve it under a minute, and you might learn something new from each problem you approach as you level up. Sounds like a nice restart.

Here are all the problems I have solved (again) so far, along with my experience solving them:

  1. Multiples of 3 and 5 - Dude, come on.
  2. Even Fibonacci Numbers - Took me a minute to write the simplest solution, took me another 2 minutes to figure out the solution listed in the problem’s editorial.
  3. Largest Prime Number - Easy peasy, prime factor of a composite number n cannot exceed sqrt(n).
  4. Largest palindrome product - Simple solution worked for me.
  5. Smallest multiple - Dude, come on.
  6. Sum square difference - Dude, come on.
  7. 10001st Prime - Dude, come on.
  8. Largest product in a series - Easy, but writing code took me a bit longer. Sliding window jutsu.
  9. Special Pythagorean triplet - Brute-force the damn thing and it will run under a minute.
  10. Summation of primes - Go to Cyrene. There’s a guy who solved this. :wink:
  11. Largest product in a grid - Easy because brute-force all over again. Since, its just 20x20, we’ll be fine. Writing code for traversal of rows, columns and diagonals sucks though. :frowning_face:
  12. Triangular Number - Iterate triangular numbers in a loop, check number of divisors for each, easy peasy.
  13. Large Sum - :cough: :cough: Python.
  14. Longest Collatz Sequence - Just go for the easy solution.
  15. Lattice Paths - Difficult for me. My combinatorics is a bit rusty now. Although, I was able to reach to the ultimate solution, I did have a bit of help on this one. I wrote a path-counting solution by imagining the whole thing as a graph of 21x21 vertices, and recorded answers for smaller inputs - 2x2, 3x3, 4x4, 5x5 and so on. And then, I used OEIS.
  16. Power Digit Sum - Dude, come on.
  17. Number Letter Counts - Use inflect, its less hassle if you are lazy like me.
  18. Maximum Path Sum I - Dynamic programming, solve the problem bottom up. The total complexity should be O(n), where n is the number of nodes.
  19. Counting Sundays - Python datetime, need I say more?
  20. Factorial Digit Sum - Use python, it can easily compute large factorials for such problems without you sweating.
  21. Amicable Numbers - We already know how to get the proper divisors of a number. Just sum them up, write sum comparison code and do all this in a loop.
  22. Names Scores - I’m keeping the text file. Seriously, I’ve been looking for a names db to cook up random excuses in my personal e-mail. Later.

Use the form below to send any feedback.