Time Management

help
1

Hello Guys. I recently joined Codechef. I code on Java. I’ve checked out some of the Beginner problems yet. I have got the correct answer to some. But the problem I am facing is that my code seems to take a lot of time. I am getting TLE every time i submit.
For instance: Problem TREE2
My code:

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
		int T=Integer.parseInt(sc.readLine());
		for(int i=0;i<T;i++)
		{
		    int N=Integer.parseInt(sc.readLine());
		    StringTokenizer st=new StringTokenizer(sc.readLine());
		    ArrayList<Long> B=new ArrayList<Long>();
		    long A;
		    for(int j=0;j<N;j++)
		    {
		        A=Integer.parseInt(st.nextToken());
		        if(! (A==0|| B.contains(A)))
		        B.add(A);
		    }
		    System.out.println(B.size());
		}
	}
}
2

Using contains() inside a for loop, will surely result into n^2 time complexity (as for every iteration, its going to search whole array again and again to check the availability of the parameter provided), thus performing more than 10^10 operations (in worst case) considering the bounds given for T and N, which is not feasible enough to pass in the given time limits. Try optimisizing your approach more. If unable to, just see the editorial and try to implement yourself.

3

Thanks for the suggestion @ayushman_25. I have in fact checked the editorial. They don’t have Java. But thankfully i understand basic C and was able to get their approach. I would like to mention that as far as i know in java using a Set or a Hash set will also create the same complexity as even a set checks for all its values before inserting a new value right? I am not able to think of any helpful replacement of the contains algorithm as it is a necessity. The best i can do is keep the arraylist sorted at each step. But even that will take processing time. Please suggest a way to remove the contains method.

4

no it doesn’t. I think “treeset” in java is a implementation of a self balancing BST, giving O(log n) insert and check whether value is contained.

3 Likes
5

thanks for formatting the code :slight_smile:

6

No, HashSet is basically implemented using Hash Table, where elements are not ordered.
So, it’s functions such as add(), contains() will do the work in O(1) expected time for average cases (though lookup time may rise to O(log(n)) due to possible collisions, refer stack overflow if wanted more info about it).

Just replace the below part of your code i.e

ArrayList<Long> B=new ArrayList<Long>();
long A;

with

Set<Integer> B=new HashSet<>();
int A;

(no need to consider long, as values less or equal to 10 ^ 9 can very well fit in int data type)

7

You can solve the problem easily without using any complex data structure like a set or a map. Sort the array first. Then create a new array to store frequencies. Let’s call it B. B[0] = 1. Now for all 1 <= i < n, if A[i] == A[i-1], then B[i] = B[i-1] + 1, else B[i] = 1. Now the number of distinct elements in the array is the number of ones in the array B. Now if zero is present in the array, then the answer is the number of distinct elements minus 1, otherwise the number of distinct elements.
Here’s my code in C++. But I think you might get an idea as I have not used anything more than basic loops.
https://www.codechef.com/viewsolution/38117867

8

Thank you very much.