The Contest Contest 1 P1 - A Typical Codeforces Problem

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 256M

Problem type

You just came up with a problem to put on a rated contest! You've invited N testers to test the problem, numbered from 1 to N, each of whom will attempt the problem and then vote either YES or NO. In order for the problem to be approved, a majority (strictly greater than half) of the testers must vote YES. You already know how each tester will vote, but it may not be a majority.

However, you have a few tricks up your sleeve. In one move, you can select an interval [l,r]. Let c be the number of testers in that interval that vote YES. Then, you can change the vote of tester c to YES. Determine if you are able to force a majority of the testers to vote YES after making any number (possibly zero) of moves.


2 \le N \le 10^6

Input Specification

The first line of input contains a single integer N, the number of testers.

The second line contains a string of length N consisting of Y or N characters. The i^\text{th} character is Y if the i^\text{th} tester votes YES and N if the i^\text{th} tester votes NO.

Output Specification

Output YES if you're able to force a majority of the testers to vote YES.

Otherwise, output NO.

Sample Input 1


Sample Output 1


Explanation for Sample 1

On the first move, we can select the interval [1,4] to get c=2 and force tester 2 to vote YES.

The votes are now YYNY, which is a majority.

Sample Input 2


Sample Output 2


Explanation for Sample 2

There are no sequences of moves that result in a majority of the testers voting YES.

Sample Input 3


Sample Output 3


Explanation for Sample 3

A majority of the testers already vote YES, so no moves are necessary.


There are no comments at the moment.