Posts

CP journey update on 11 Oct 2019

I have been away from Competitive Programming for a long time (about 2 years). No, not because I lost interest in it. I was simply too busy with university coursework. This break was also beneficial in another way - I realized that there are so many things that are much more valuable and important in Computer Science than Competitive Programming. Competitive Programming, while fun as a hobby, does not have much practical use in most real-world applications. My reasons for saying this are as follows: Many real-world problems are NP-hard (i.e. do not have efficient solutions) and it is more practical to solve such problems by approximation rather than computing an exact solution. However, in Programming Competitions, most of the time, we are given problems that have known efficient solutions and the results simply depend on who can discover and implement the solution the fastest. In the real-world, we need the patience and resilience to try different approaches to problems for whi
1 comment
Keep reading

My debugging and bug prevention strategies

Programmers, such as myself, frequently encounter bugs in our program code. Sometimes, we are able to resolve them quickly, sometimes it take hours. Worse still, after resolving the current set of bugs, another pops up! As a programmer, I have experienced the pain of debugging my program code, for hours on end, not knowing what is wrong with my logic. Over time, I have developed a debugging toolbox that has proven to be effective for myself. I have to mention though, that this only applies to Competitive Programming, not professional programming, where circumstances could vary greatly. Another point to note is, my discussion is more skewed towards C++ programmers so issues like segmentation fault may not apply to languages such as Java. The 5 most common bugs/errors that I have seen are (in no particular order): 1. Segmentation fault. 2. Integer overflow 3. Division by zero 4. Strange output values with multiple test cases 5. Logic Errors No. 1 is mostly easy to
Post a Comment
Keep reading

My direction in Competitive Programming

Having carefully-developed a well-tested template for programming contests, I am currently looking for ways and means to improve my speed and accuracy in contests. The latter can only be improved through more experience and faster typing speed. In order to fix my slow typing speed, I have learnt touch-typing - my typing speed has increased from an average of 40+wpm to 75 wpm ever since. My extensive list of programming macros also puts less emphasis on my typing speed. As for problem-solving speed, I have to admit that the author of "Competitive Programming" is right - use the simplest solution that works. Who cares if it is not the most efficient solution? What matters is the "accepted" status. Hence, I am now working in that direction - to write solutions that just make the cut and are easy to implement. An additional effort that I have made over the past year is to develop a well-documented code library of common data structures and algorithms that I would ne
Post a Comment
Keep reading

Efficient learning in Competitive Programming

Many competitive programmers (myself included) often face difficult problems that we cannot solve for days on end. This is normal because no one knows everything. But I feel that spending many hours trying to crack a single problem is a waste of time and stems learning. If we cannot solve a particular problem, it could probably be due to the lack of one or more specific skills and/or concepts. For example, how would a beginner programmer know how to use dynamic programming? He or she would not even know that the question requires dynamic programming. As a former beginner, I can emphatize with those sentiments. When I first embarked on my Competitive Programming journey, I could spend an entire day working on a single problem, which turned out to be very trivial after using a few simple tricks. As such, it is imperative to read editorials and other AC (accepted) solutions rather than trying to "challenge ourselves". Learning from others will help prevent us from reinventin
2 comments
Keep reading

Mathematical Circles - Days in a month

I chanced across a problem in the book "Mathematical Circles" which I felt was interesting. The problem is described below: In a certain year there were exactly four Fridays and exactly four Mondays in January. On what day of the week did the 20th of January fall that year? On first look, it looks like a regular high school math question that I would use trial and error to solve. But, is there a more elegant way to deduce the solution? The suggested solution, which I thought was pretty clever: Notice that January always has 31 days. Observe that days 1, 8, 15, 22 and 29 of the month are always the same day in a week since they vary by exactly 1 week/7 days. By the same reasoning, 2, 9 ... 30 and 3, 10 ... 31 are also the same days in a week. The particular month of January that is described in the problem statement cannot start with Monday, Wednesday, Thursday, Friday, Saturday or Sunday. Otherwise, there would be 5 Mondays or Fridays (we can infer this
Post a Comment
Keep reading

HackerRank - Search in a 2-D grid

Image
Today, I managed to complete HackerRank 's Grid Search albeit with a little difficulty. In a nutshell, the problem requires us to find a 2-D rectangular pattern in a 2-D rectangular grid. All contents of the pattern and the grid are digits from 0-9. For example: The given grid is: 1 2 3 4 5 6 7 8 9 0 0 9 8 7 6 5 4 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 The given pattern is: 8 7 6 5 4 3 1 1 1 1 1 1 1 1 1 1 1 1 It is not difficult to tell that the pattern exists in the center of the grid (highlighted in red): 1 2 3 4 5 6 7 8 9 0 0 9 8 7 6 5 4 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 The grid's dimensions can be at most 1000 * 1000 and the pattern can be at most as large as the grid itself. Problem source: here What would be your algorithm to solve this problem? On first thought, the naive solution should come to mind: brute-force matching. For every cell in the g
2 comments
Keep reading

USACO - Broken Necklace

I recently completed a mathematical problem "Broken Necklace" on USACO . The abridged problem statement is described below: We have a necklace that contains n  (3 <=  n  <= 350) beads of 3 colors: red ( r ), blue ( b ) and white ( w ). If we break the necklace at some position i , the necklace will clearly have 2 end points x  and y . Starting from each of the end points, we can collect similarly colored  consecutive  beads from each end point (e.g. blue from one end, red from the other) until we reach a bead of a different color. The only exception is, white beads can take on any color. Example: Initially, we have this necklace (sorry for the bad formatting): x y   r b b r r      b r      r r      r b     r b     b b     b b     b r      r b     r b     r r      r  r  b  r We break it at the point between x and y, obtaining the following configuration:                                                  x   brbrrrbbbrrrrr
3 comments
Keep reading