DMOPC '18 Contest 1 P6 - Sorting

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 1.8s
Java 4.5s
Python 4.5s
Memory limit: 256M

Author:
Problem type

Harold has been misbehaving and now his teacher has given him detention! The teacher has written N numbers in their binary representation on the chalkboard. These binary numbers are all written with exactly B bits (leading zeroes are allowed) and are written in a list. The teacher tells Harold,

You can leave once the N B-bit binary numbers are sorted from least to greatest.

Harold, being mischievous, decides that as long as there are N B-bit binary numbers in sorted order, then he is done, even if they are not the original numbers. He will change some of the characters so that the resulting numbers are sorted. He can only change 0s to 1s and 1s to 0s. He is not allowed to add more characters or delete existing characters.

Harold is also lazy, so he wants to change as few characters as possible. Help him find the least number of changes he needs.

Constraints

Subtask 1 [40%]

1 \le N \le 200
1 \le B \le 50

Subtask 2 [60%]

1 \le N \le 1\,000
1 \le B \le 50

Input Specification

The first line contains two space-separated integers, N and B.
Lines 2, 3, \dots, N+1 each contain a single string of exactly B characters, either 0 or 1. The string on line i+1 represents the i^\text{th} number in the list.

Output Specification

Output a single integer, the minimum number of changes required to sort the list.

Sample Input 1

4 3
111
110
000
100

Sample Output 1

3

Explanation for Sample 1

Harold can change the first character of the first number, the second character of the second number, and the first character of the third number to get the sorted list.

011
100
100
100

Sample Input 2

10 5
10010
11101
01011
01000
11100
00110
00110
10001
01101
01000

Sample Output 2

10

Comments

There are no comments at the moment.