Re: Why is the difficulty of this problem easy?

I totally agree. I am also surprised by some other problems in OJ with misleading labels of difficulty as well. In my opinion, for coding problems, the "difficulty" can be categorized into

- essential complexity: how difficult can you come up with an algorithm.
- non-essential complexity: how difficult can you implement the algorithm above.

As I worked on many problems in OJ, I feels that OJ tends to label lower difficulty to a problem as long as the non-essential complexity is low, I.e., the problem is considered as simple as long as the coding part is not too challenging. However, many difficult problems are actually mathematics problems and need serious "brain calculations" before a single line of code is written.

For the poor pigs problem, if I extracted away all the sugar coating of the ambiguous storytelling, and go straight to ask

**if an object has exactly T+1 different states, how many independent such objects do you need to be able to make at least N distinct combinations?**

I believe everyone would agree the question above is easy if it is stated this way. However, to find out (or prove) the equivalence between the poor pigs problem and the abstracted problem is non-trivial at all and all difficult works are done mathematically instead of programmatically.

A coding problem shouldn't be called easy simply because the coding part alone is easy.