### IvayloS's blog

By IvayloS, history, 5 years ago, ,

It so happens that apart from being an active member on Code forces I spend quite some time on stackoverflow.com trying to provide help for users around the world. Every now and then I see a question where the most upvoted and accepted answer is not entirely correct but this time it is a bit different. Take a look at this question: http://stackoverflow.com/q/13713572/812912 The discussion is pretty much on what is greedy and DP and isn't one of them a subset of the other. The most upvoted and accepted answer states the following:

The difference between dynamic programming and greedy algorithms is that with dynamic programming, the subproblems overlap.

(take a look at the whole answer here)

In fact the whole answer is quite interesting. I tried to start a discussion with the poster, explaining what is wrong but I keep getting more and more interesting statements. Here is an example(in the comments section):

@IvayloStrandjev: No, Dijkstra's without the heap would be a greedy algorithm. The heap introduces a dependency whereby when a decision is made about a solution to a subproblem (the shortest path to a vertex) is used to facilitate the decisions to the other subproblems. This is why Dijkstra's is not simply a greedy algorithm (or else you would have to make the decisions independently). This agrees with the top Quora answer. –  Neil G Sep 18 at 13:54


If you also read through the chat you will notice that the same user claims that computing the n-th Fibonacci number using memoization is DP(which is correct), but without memoization it would be greedy(which is nonsense).

It is first time I see an accepted answer that is so off target and where the poster ignores any reasoning. Truth is that this case annoys me quite a lot — I see something that is totally incorrect and yet it seems to be accepted by the community. More people would read this answer and most will believe it is correct. Thus I am turning to code forces community for some support. Apparently my opinion is not authoritative enough and the links I provide are not enough. I would also like to hear what you think on the whole discussion.

• +17

By IvayloS, 6 years ago, ,

I have noticed that problem score distributions are often unfair and the last Round(FF) in Div 1 is not an exception. Although second and third problem gave the same number of points, third problem was solved by way less competitors.

I have a proposal on how to address this: introduce adaptive problem scoring. The problem score will be determined by the number of successful submissions for this problem. There are two options for this: either have a set rule of the type "If problem A has between X% and Y% accepted submissions it will be a 1000 pointer" or create a more flexible formula able to give other point scores, not only 500, 1000, 1500... The score of each problem will be determined at the end of the competition.

Another good feature of this is that with a bit for data mining rounds can be rated according to their quality. We can set expectations for a round and if a round does not meet the criteria it will be considered "not-good". I personally dislike rounds where only 3 out of 5 problems get any solutions and I believe such rounds should be avoided.

• +4

By IvayloS, 6 years ago, ,

While browsing through some old problems I noticed this problem. For it there is a note at the top:

This is simplified version of the problem used on the original contest. The original problem seems to have too difficult solution. The constraints for input data have been reduced.

Statement of the sort "have too difficult solution" sounds like a challenge to me and so I decided I am up to it. I began to wonder is it possible to find the original statement. The problem is I can't seem to find it anywhere on the site. Is it possible to find the original statement somewhere?

• +5

By IvayloS, 9 years ago, ,
This post is totally not about complaining - I think this is the fastest growing and best performing online cometition website recently and I do appreiate all the effort put in it. I simply want to give a few proposals for functionality that can be added to it.

It is not really a neccessity but it would be nice to have the coders grouped by countries. What I want to be able to do is to view the list of coders in code forces registered for a given country ordered by rating and add some of them as my friends. Having country rating is also nice.

I wish you a successful new year and a lot new users performing ever better on the way to perfection!