tag:blogger.com,1999:blog-6444310323348364302011-07-08T16:11:56.768+02:00lost in algorithmsRafal Jozefowiczhttp://www.blogger.com/profile/15036348397219692182noreply@blogger.comBlogger71100tag:blogger.com,1999:blog-644431032334836430.post-10357339727704875862010-05-21T21:36:00.007+02:002010-05-21T22:54:49.219+02:00

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 ProblemYou 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

Rafal Jozefowiczhttp://www.blogger.com/profile/15036348397219692182noreply@blogger.com2tag:blogger.com,1999:blog-644431032334836430.post-27007583140443616292010-04-08T23:40:00.002+02:002010-04-09T09:57:14.538+02:00

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

Rafal Jozefowiczhttp://www.blogger.com/profile/15036348397219692182noreply@blogger.com0tag:blogger.com,1999:blog-644431032334836430.post-74563566679427719132009-12-23T02:08:00.006+01:002010-04-17T23:31:24.594+02:00

Let's look at some more problems to exercise our brains during Christmas time. Problem IIIYou are given an N element array filled with integers. Find the non-empty interval in this array with maximal possible sum.Example:T = [1, -2, 3, 1, -3, 2, 2, -7, 4, -2, 1]Here the best solution is interval [2, 6] (indexing from 0) with sum equal to 3 + 1 + (-3) + 2 + 2 = 5. This is a much different problem

Rafal Jozefowiczhttp://www.blogger.com/profile/15036348397219692182noreply@blogger.com2tag:blogger.com,1999:blog-644431032334836430.post-70961081684218308732009-12-15T23:06:00.002+01:002009-12-23T11:08:16.633+01:00

Have you ever had bad dreams because of not being able to solve any dynamic programming problems? Yeah, me neither. Many of my friends hate this technique. Why is that? Let's see the typical process of learning DP: 1. Encounter hard enough DP problem on some competition / book 2. After not solving it, ask someone how to do it correctly 3. “They’re crazy. How the ?#$% should I be able to come up

Rafal Jozefowiczhttp://www.blogger.com/profile/15036348397219692182noreply@blogger.com1tag:blogger.com,1999:blog-644431032334836430.post-29099212284506924662009-12-12T00:17:00.010+01:002009-12-20T21:34:15.692+01:00

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: "

Rafal Jozefowiczhttp://www.blogger.com/profile/15036348397219692182noreply@blogger.com2tag:blogger.com,1999:blog-644431032334836430.post-77686336316278916472009-12-09T01:27:00.011+01:002009-12-10T20:56:06.435+01:00

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

Rafal Jozefowiczhttp://www.blogger.com/profile/15036348397219692182noreply@blogger.com3tag:blogger.com,1999:blog-644431032334836430.post-32337563944611154742009-12-08T03:04:00.002+01:002009-12-09T00:27:34.915+01:00

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.

Rafal Jozefowiczhttp://www.blogger.com/profile/15036348397219692182noreply@blogger.com7