Math and Algorithm Magic

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

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

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

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

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

Hi. I am Gabriel (a.k.a. Lance), a competitive programmer from Singapore. I started this blog to share my journey in acquiring mathematical and algorithmic problem solving skills. Since this is my first post, I will elaborate on my background in math, programming (and algorithms). I was first introduced to programming by a friend in high school, at the age of 14. Back then, I was curious about how to create a website, so I self-learnt web-development languages such PHP, HTML, CSS, etc. Back then, I thought that programming was pretty mundane because I was just following a fixed set of simple procedures to create a webpage layout, write the content, etc. If I didn't know how to do certain functionality, I would just copy and paste code from the web and it magically worked! The fact that I didn't understand what I was doing never really bothered me as I was able to get the job done. This interest was short-lived as I found web-design to be a hassle due to my bad design skills