codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

496C.md (1836B)


      1 Source: https://codeforces.com/problemset/problem/496/C
      2 
      3 C. Removing Columns
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 You are given an *n* × *m* rectangular table consisting of lower case English letters. In one operation you can completely remove one column from the table. The remaining parts are combined forming a new table. For example, after removing the second column from the table
     22 
     23 ```
     24 abcd  
     25 edfg  
     26 hijk
     27 ```
     28 
     29 we obtain the table:
     30 
     31 ```
     32 acd  
     33 efg  
     34 hjk
     35 ```
     36 
     37 A table is called good if its rows are ordered from top to bottom lexicographically, i.e. each row is lexicographically no larger than the following one. Determine the minimum number of operations of removing a column needed to make a given table good.
     38 
     39 Input
     40 
     41 The first line contains two integers  — *n* and *m* (1 ≤ *n*, *m* ≤ 100).
     42 
     43 Next *n* lines contain *m* small English letters each — the characters of the table.
     44 
     45 Output
     46 
     47 Print a single number — the minimum number of columns that you need to remove in order to make the table good.
     48 
     49 Examples
     50 
     51 Input
     52 
     53 ```
     54 1 10  
     55 codeforces
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 0
     62 ```
     63 
     64 Input
     65 
     66 ```
     67 4 4  
     68 case  
     69 care  
     70 test  
     71 code
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 2
     78 ```
     79 
     80 Input
     81 
     82 ```
     83 5 4  
     84 code  
     85 forc  
     86 esco  
     87 defo  
     88 rces
     89 ```
     90 
     91 Output
     92 
     93 ```
     94 4
     95 ```
     96 
     97 Note
     98 
     99 In the first sample the table is already good.
    100 
    101 In the second sample you may remove the first and third column.
    102 
    103 In the third sample you have to remove all the columns (note that the table where all rows are empty is considered good by definition).
    104 
    105 Let strings *s* and *t* have equal length. Then, *s* is lexicographically larger than *t* if they are not equal and the character following the largest common prefix of *s* and *t* (the prefix may be empty) in *s* is alphabetically larger than the corresponding character of *t*.