CODEWITHSUNDEEP
pythontime-complexity
Idyllic
Idyllic

Reputation: 1

Time-Complexity of the problem in CodeForces contest #771

I'm currently trying to upsolve one problem from CodeForces and I face so many time issues. I've tried a variety of modifications, however my code still doesn't get submitted.

Any suggestions on how I can improve the time complexity of my code?

The main idea of the problem can be found here: https://codeforces.com/contest/1638/problem/C

A description of the problem is as follows:

You are given a permutation p_1,p_2,…,p_n. Then, an undirected graph is constructed in the following way: add an edge between vertices i, j such that i < j if and only if p_i > p_j. Your task is to count the number of connected components in this graph.

Two vertices u and v belong to the same connected component if and only if there is at least one path along edges connecting u and v.

A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Input

Each test contains multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 10**5) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10**5) — the length of the permutation.

The second line of each test case contains n integers p_1,p_2,…,p_n (1≤p_i≤n) — the elements of the permutation.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10**5.

Output

For each test case, print one integer k — the number of connected components.

import sys
input = sys.stdin.readline
     
for case in range(int(input())):
    length = int(input())
    line = list(map(int, input().split()))
    
    quantity = 0
    for i in range(1, length):
        if line[i] > line[i-1] and max(line[:i]) < min(line[i:]):
            quantity += 1
                
    print(1 if quantity >= length else quantity + 1)

Thanks for your help!

Upvotes: 0

Views: 793

Answers (1)

Tim Roberts
Tim Roberts

Reputation: 54867

This implements my min/max caching scheme. I have not submitted this, so I don't actually know if it will meet the timing. This is O(3N) instead of O(N*N), so it will take slightly longer for short lists, but SHOULD be better for long lists.

You don't need to do input = sys.stdin.readline; that's effectively what the input function already is. Also, the if clause in your final line confuses me. Your final for can never go more than length-1 iterations, so quantity can never be >= length.

import sys
     
for case in range(int(input())):
    length = int(input())
    line = list(map(int, input().split()))
    maxx = 0
    maxs = []
    for i in line:
        if i > maxx:
            maxx = i
        maxs.append(maxx)
    minx = 999999
    mins = []
    for i in line[::-1]:
        if i < minx:
            minx = i
        mins.insert(0,minx)
    
    quantity = 0
    for i in range(1, length):
        if line[i] > line[i-1] and maxs[i-1] < mins[i]:
            quantity += 1
                
    print(quantity + 1)

You can replace the final section of the code with a comprehension, although I think that's a micro-optimization:

    quantity = sum(
        line[i] > line[i-1] and maxs[i-1] < mins[i]
        for i in range(1, length)
    )
                
    print(quantity + 1)

Upvotes: -1

Related Questions