On DP and graphs

Many DP problems can be presented in the graph theory language. It is good to see a relation between those two worlds. Very often it helps to come up with the solution faster and in a more structured way.

Let's solve a simple problem:

Simple Problem

You are given two dimensional array NxM, which is a map of the forest. Each cell contains the information about the number of blueberries in that place. Alice is standing at the north-west corner of the forest and she wants to move to south/east directions only. Help her get to home which at the opposite corner while  collecting the largest number of blueberries.

On finding majority

I have recently given a thought to a following problem:
You are given an array (size N) of some numbers. Find out if there exists a number that appears at least N/2 – 4 times in it. Print out any of them or “Not exists” if there isn’t any.
Expected solution: linear time, constant additional memory.
Sounds silly and very unpractical, I know, but it’s still a quite interesting problem :) Try to solve it yourself first.

Dynamic Programming - more action

Let's look at some more problems to exercise our brains during Christmas time.

Dynamic Programming - the basics

Have you ever had bad dreams because of not being able to solve any dynamic programming problems?

Yeah, me neither.

Brutal coding

No matter how good you are, there will be problems that you are unable to solve, even after long hours spent on thinking. What can you do with them?
Very often it is possible write a solution that looks at every candidate for the result and chooses the best. This is a brute force approach. I want to talk about it a bit today, because from my and others experience I know that it is easy to say: "you can always write something like that" but usually it is quite tricky. Also, this can be helpful in the future while solving dynamic programming problems. I want to show some simple examples of using brute force technique.

Too long to read

I've always liked thinking about mathematical problems but never proving their solutions.

This is one of the reasons I got interested in the algorithm competitions. Solutions don't have to be perfect, sometimes they don't even have to be correct. It's just enough that they're working on test cases provided by authors. It makes you creative. You can try different approaches based on your intuition, lucky hunches or just theory of probability (like Monte Carlo method) and hoping for merciful test data. It can be considered as fun in some geeky environments.

Hello World!

My name is Rafal and I am a geek. I devoted about 5 years of my life to algorithms and participated in a lot of competitions. Some with successes, some with failures, but since I am apparently getting too old for this I decided to share some thoughts/experience before I die.