ZNANSTVE - ZNANSTVENIK

no tags 

 

In this economy, we all know how hard it is to get a job. Mirko, a recent college graduate, however, got
lucky - he is now employed as a runeologist by the Language Institute of Croatia. His friend Slavko
believes runeology isn’t a science and is hence angry at Mirko for believing the opposite. One foggy
Christmas day, Mirko’s laptop broke. Since he isn’t great with computers, he gave it to Slavko to repair
it. Slavko, felling a little naughty, decided to mess up a particular file Mirko was working on.
This file contains a matrix of R rows and C columns. Each element of the matrix is a single letter. No
two columns of the matrix are equal. To have some fun with pseudo-scientist Mirko, Slavko decided
he will delete as much rows as possible from the top of the table, without breaking the no-equalcolumn
rule.
INPUT
The first line of input contains two integers R and C (2 ≤ R, C ≤ 1000), the number of rows and the
number of columns, respectively.
In each of the next R lines there are C small letters of the English alphabet. These R x C letters
represent Mirko’s table (which does not have two same columns).
OUTPUT
Output a single integer, the maximum number of rows which can be deleted from the top of the table
so that no two columns are equal.
EXAMPLE TEST DATA
input
2 6
dobarz
adatak
output
0
input
3 4
alfa
beta
zeta
output
2
input
4 6
mrvica
mrvica
marica
mateja
output
1

 

In this economy, we all know how hard it is to get a job. Mirko, a recent college graduate, however, got lucky - he is now employed as a runeologist by the Language Institute of Croatia. His friend Slavko believes runeology isn’t a science and is hence angry at Mirko for believing the opposite. One foggy Christmas day, Mirko’s laptop broke. Since he isn’t great with computers, he gave it to Slavko to repair it. Slavko, felling a little naughty, decided to mess up a particular file Mirko was working on.

This file contains a matrix of R rows and C columns. Each element of the matrix is a single letter. No two columns of the matrix are equal. To have some fun with pseudo-scientist Mirko, Slavko decided he will delete as much rows as possible from the top of the table, without breaking the no-equalcolumn rule.

INPUT

The first line of input contains two integers R and C (2 ≤ R, C ≤ 1000), the number of rows and the

number of columns, respectively.

In each of the next R lines there are C small letters of the English alphabet. These R x C letters

represent Mirko’s table (which does not have two same columns).

OUTPUT

Output a single integer, the maximum number of rows which can be deleted from the top of the table

so that no two columns are equal.

EXAMPLE TEST DATA

input

2 6

dobarz

adatak

output

0

input

3 4

alfa

beta

zeta

output

2

input

4 6

mrvica

mrvica

marica

mateja

output

1

 

 


hide comments
nadstratosfer: 2019-04-08 16:18:09

There are blanklines between rows, nasty trap for line-reading languages when input is made of strings!

vengatesh15: 2017-09-17 18:50:07

Finally AC after so many attempts.

Shakil Ahmed: 2013-11-05 10:45:16

Try this input :
3 4
alfa
betb
zetz

Output :
0

got 2 WA in 9th test case. After fixing this, got AC.

Gaurav: 2013-08-30 12:57:23

easy pgm in python but i am getting tle :(

Narendra yadav: 2013-06-26 16:20:21

Getting wrong in 9th case ..pl suggest.
Sub id :9556142

Amit RC: 2013-06-23 19:00:51

the only difference between my second last and third last submissions is declaring the variable max as local and global...yet one gives TLE while other gives WA..how is that possible?

adhikari vushesh babu: 2013-03-03 16:42:49

simple got acc :)by brute force

Secret: 2013-01-24 11:23:03

brute force is accepted :P

:D: 2012-02-15 07:30:27

If you delete row 1 and 2, columns 1 and 6 will be identical with "aa", so you can delete only one.

hibernating: 2012-02-14 21:25:06

what is meant by "top of the table"
is it like we have to delete the first row first then second....If it is like this than plz xplain 3rd test case....
plz help


Added by:islam
Date:2012-02-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:COCI 2010/2011 Contest 1 by Adrian Satja Kurdija