Chef and Strange Matrix

general
,
1

http://www.codechef.com/viewsolution/3898256

I’m getting runtime error but the code is running properly on my codeblocks (probably because I’m not entering very large values)… Since I’m new here, can anyone help me out with this?

2

As given in the constraints, n and m both can be 10^5. Allocating a 2-d array a[10^5][10^5], is not feasible here. You are running out of memory and hence getting RTE.

Refer this
and this

3

You can try this input

100000 100000 1
1 1

if there is not RE on your local PC, there will be TLE (no result in 2 seconds) :wink:

1 Like
4

@prakhar8795 Since you are new here, the above TLE is because you are using nested loop. The number of operations in worst case will be (10^5)(10^5) which is not possible to run within the given time limit.

5

You neither need initial nor final matrix. Its just P and M that is required for the solution.
The approach that I used is as follows.

  1. Take P in Dictionary (HASH).

  2. Starting from the beginning keep checking if there exist some value where a[i][j] > a[i][j+1]. If so set c[i] = -1. Do this for all values in Dictionary if c[i] is already != -1.

  3. After this loop from 1 to N

    ans = p[i].end - p[i].start + (m-1) if end and start both exist.
    else
    ans = p[i].end + (m-1), if only end exist
    else
    ans = (m-1) - p[i].start , if only start exist
    else
    ans = m-1 , if start and end doesn’t exist

Here end and start are a[0] and a[n] for that particular row.

As difference of all elements from a[i][1],a[i][2]…a[i][n] will only yield a[i][n] - a[i][1].

Same goes for the initial matrix which will always yield m-1.

Using this approach you don’t have to care about 10^5 inputs as array’s are not at all required. So no memory exception or TLE.

Hope this will help :slight_smile:

1 Like