How to solve "Select Training Set" without getting TLE ||please help|| (prob. link in description )

problem link:- https://www.codechef.com/problems/TRAINSET

please help :pray:

For each string, keep a count of how many times it occurs as 1 and how many times it appears as 0. Then take the sum of maximum over all strings in the answer.

You can use a simple hash-table like map and get the answer, doesn’t require much of a tweak.
maybe something like

map < string,pair<int,int> > frequency

key has two values i.e. frequency of (0,1). while iterating always take the maximum among both and add to your answer.

1 Like

what is a map ?

can you tell me what is map as i don’t have CS background ?
I have not heard of it earlier .

Refer this.

1 Like

Ok thanks a lot :smiley:

1 Like

is there any other way since I know only C language and in C language map function is not available ?

1 Like

Learn another language :slight_smile:

2 Likes

Ok :+1: :v:

there’s always a way !

make and array of structures (having two elements string si and integer wi), scan all the elements for each i, now apply qsort() and sort them, now run a loop and check for equal elements, and update the result accordingly.

1 Like

what if I do all these thing but without creating array of structures ?
then will it give TLE ?

Why using structure will reduce the time ?

It is no where reducing time, using structures helps you store two values at a time. also further sorting take O(NlogN), thus optimising it from O(N^2).

1 Like