Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem A:
Where is the Boundary

An island country JAGAN in a certain planet is very long and narrow, and extends east and
west. This long country is said to consist of two major cultural areas | the eastern and the
western. Regions in the east tend to have the eastern cultural features and regions in the west
tend to have the western cultural features, but, of course, the boundary between the two cultural
areas is not clear, which has been an issue.

You are given an assignment estimating the boundary using a given data set.

More precise specification of the assignment is as follows:

 JAGAN is divided into $n$ prefectures forming a line in the east-west direction. Each
prefecture is numbered 1, 2, ..., $n$ from WEST to EAST.

 Each data set consists of $m$ features, which has 'E' (east) or 'W' (west) for each prefecture.
These data indicate that each prefecture has eastern or western features from $m$ different
point of views, for example, food, clothing, and so on.

 In the estimation, you have to choose a cultural boundary achieving the minimal errors.
That is, you have to minimize the sum of 'W's in the eastern side and 'E's in the western
side.

 In the estimation, you can choose a cultural boundary only from the boundaries between
two prefectures.

Sometimes all prefectures may be estimated to be the eastern or the western cultural area.
In these cases, to simplify, you must virtually consider that the boundary is placed between
prefecture No. 0 and No. 1 or between prefecture No. $n$ and No. $n+1$. When you get multiple
minimums, you must output the most western (least-numbered) result.

Write a program to solve the assignment.

Input

Each input is formatted as follows:

$n$ $m$

$d_{11} ... d_{1n}$

:

:

$d_{m1} ... d_{mn}$

The first line consists of two integers $n$ ($1 \leq n \leq 10,000$), $m$ ($1 \leq m \leq 100$), which indicate
the number of prefectures and the number of features in the assignment. The following m lines
are the given data set in the assignment. Each line contains exactly $n$ characters. The $j$-th
character in the $i$-th line $d_{ij}$ is 'E' (east) or 'W' (west), which indicates $j$-th prefecture has the
eastern or the western feature from the $i$-th point of view.

Output

Print the estimated result in a line. The output consists of two integers sorted in the ascending
order which indicate two prefectures touching the boundary.

Sample Input

2 1
WE

Output for the Sample Input

1 2

Sample Input

3 2
WWE
WEE

Output for the Sample Input

1 2

Both estimates "1 2" and "2 3" achieve 1 error as the minimum. From the restriction that you
must adopt the most western estimate, you must output "1 2".

Sample Input

3 1
WWW

Output for the Sample Input

3 4

In this case, all the prefectures are western. As described in the problem statement, you must
virtually consider that the boundary is placed between third and fourth prefectures.

Sample Input

3 1
WEW

Output for the Sample Input

1 2

You cannot assume that 'E's and 'W's are separated.



Sample input:
2 1
WE


Sample output:
1 2

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [S() for _ in range(m)]
    r = n
    for i in range(n):
        if r < i:
            break
        for j in range(m):
            if a[j][i] == 'E':
                r = i
                break

    return '{} {}'.format(r,r+1)


print(main())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [S() for _ in range(m)]
    b = [0] * (n+1)
    c = [0] * (n+1)
    for i in range(n):
        for j in range(m):
            if a[j][i] == 'W':
                b[i] += 1
            else:
                c[i] += 1

    for i in range(n):
        c[i+1] += c[i]

    for i in range(n-2,-1,-1):
        b[i] += b[i+1]

    m = b[0]
    r = 0
    for i in range(n):
        tm = b[i+1] + c[i]
        if m > tm:
            r = i + 1
            m = tm

    return '{} {}'.format(r,r+1)


print(main())