1

I was going through a problem on CodeChef (https://www.codechef.com/problems/SUBINC) on counting subarrays which are strictly non-decreasing. Despite reading through the description several times, I was unable to decipher what I was expected to do.

I was mainly having a problem with two statements:

1)*"All valid subarrays are A[1, 1], A[1, 2], A[2, 2], A[3, 3], A[3, 4], A[4, 4]."*

If the subarray was 1 4 2 3, then how are A[2,2];A[3,3];A[3,4];and A[4,4] valid?(Given that it is non-decreasing only if forward elements are in decreasing order)Also why is A[1,1] valid?

2)"Only single subarray A[1, 1] is non-decreasing."

Similar problem here. If the array itself is only 1 then how can you count A[1,1] is a sub-array?

Perhaps I have completely failed to perceive what is to be done as this problem has been solved by many, but a bit of help would really be appreciated.

P.S I code in Java and am not so comfortable in C so that is why I could not understand most of the submissions.

Improve this question
1
  • how can you count A[1,1] is a sub-array - Because the instructions say "singleton subarrays are identically non-decreasing" Commented Jan 29, 2016 at 16:20

1 Answer 1

Reset to default
3

Ok, you have an array of four numbers 1 4 2 3

The notation A[i, j] says: "Take all elements of the array from the index i to the index j".

A[1,2] will represent a subarray: 1 4

A[1,3] will represent a subarray: 1 4 2

A[1,4] will be the whole array: 1 4 2 3

And any single element of the array is a subarray too, so when we say A[1,1] it means we need to take the elements starting from the index 1 to the index 1, so it will be just one number: 1

(A[2,2] is 4 therefore and so on).

Non-decreasing means that the next element of array must not be less that the previous. So a one-element array is always non-decreasing, the next element in it just doen't exist (so it's can't be less).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.