Time limit exceed 451B codeforces

1

submission link →

i have solved the TLE problem but i am not able to understand why it was occurring .
It will be helpful if anyone can share his/her insight about the issue.
correct submission->Submission #115141873 - Codeforces

2

What is comp for these lines

rep(i, 0, t - 1) {
    if (v[i] > v[i + 1]) {
      if (st == -1) {
        st = i;
      }
      rep(j, i, t - 1) {
        if (v[j] < v[j + 1]) {
          en = j;
          break;
        }
 
      }
 
    }
 
  }
1 Like
3

Looks like n^2 for array sorted in non increasing order.
Ex-

5
5 4 3 2 1
3 Likes
4

how

5 
rep(i, 0, t - 1) {
    if (v[i] > v[i + 1]) {
      if (st == -1) {
        st = i;
      }
      rep(j, i, t - 1) {
      	cout<<i<<" "<<j<<endl;
        if (v[j] < v[j + 1]) {
          en = j;
          break;
        }

      }

    }

There are others way to see but easiest to print i and j in the inner loop.
Running the test case ,

5
5 4 2 3 1

I get-

0 0
0 1
0 2
0 3
0 4
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
1 Like
7

For whole this time I was thinking about increasing order

8

maybe i should highlight…

9

maybe tle simply because in TLE submission you checked
this if (v[i] > v[i + 1]) everytime from rep(i, 0, t - 1) ,
but in AC submission , you checked it only till it’s first true occurrence

10

Thank you for explaining.

1 Like