Terrible edgecase for CHECHOC (Codechef Lunchtime July 2020)

1

To explain in brief about the question

    We had to find the maximum sum of all cells in a matrix of dimensions N x M such that all elements lie in range[0,X] and **sum of two adjacent cells is <=Y**. 1≤N,M≤100 ,1≤X,Y≤10^4

Now ,considering that sum of two adjacent cells never exceeds Y and that all cells have non-negative integers in them it is safe to assume that the value in an individual cell would also be <=Y.

But there is one wicked edgecase case when this assumption fails and that is when both M==1 && N ==1
Now because cell doesn’t have any adjacent cells , the question wants us to assume that it can have a value >=Y

The question had a rather simple solution otherwise but it became rather ambiguous because of that edgecase.

There were many ways in which this could have been avoided such as:

  1. Better framed constraints.If the queries are regarding adjacent elements , atleast make sure that the question constraints have adjacent elements at all times ! What are we supposed to assume otherwise? IF the constraints were 2≤X,Y≤10^4 it would have never been a problem.
  2. By making an announcement! Like plenty of announcements made on codeforces rounds.
  3. Including more diverse cases in sample tests so that the task becomes more clear.

I request the codechef team to look into this topic. And if possible remove that test case from final testing.

3 Likes
2

I think that is one of the most important thing we need to think in codechefs contest ,right??

2 Likes
3

I think it is always advised to look for the edge cases in the problem.

4 Likes
4
Simple answer to your doubt

Wrong Assumption

Reason

Why to assume anything when they already provided you with appropriate constraints?

There wasn’t any ambiguity in this question.

The samples are naive so you could do a little effort to look for edges cases.

5 Likes