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

general
1

problem link:- TRAINSET Problem - CodeChef

please help :pray:

2

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.

3

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
4

what is a map ?

5

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

6

Refer this.

1 Like
7

Ok thanks a lot :smiley:

1 Like
8

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

1 Like
9

Learn another language :slight_smile:

2 Likes
10

Ok :+1: :v:

11

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
12

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

13

Why using structure will reduce the time ?

14

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