FootballCompetition | Topcoder Archive

Problem Statement

The Football World Championship is coming soon. A lot of people want to know who will win.

There are 2^R teams taking part in the tournament. In order to determine the winner, R rounds will be held. All teams will compete in the first round, and in each next round only the teams will compete that haven't been eliminated yet. In each round, all participating teams will be broken into pairs in an arbitrary way. Each pair of teams will play a match, the winner of which advances to the next round and the loser gets eliminated from the tournament. The tournament's winner is the team that has won all its matches.

At any point during the tournament, each team can be characterized by its current energy level. The initial energy level of team i before beginning of the tournament is initialEnergy[i]. Initial energy levels of all teams are distinct. Let us assume that in a match the team with the greater current energy level will win. If the current energy levels of the two teams are equal then the team with the greater initial energy level will win. The winner of each match is tired and loses some of its energy. Let us assume that the winner decreases its current energy level by the current energy level of its defeated opponent.

Since there can be many ways to break teams into pairs in each round of the tournament, the winner is not necessarily uniquely defined by initial energy levels of the participating teams. Your task is to find for which teams there exists a scenario according to which they could win the championship. Return a String where the i-th character is 'Y' if the i-th team could win and the character 'N' if i-th team can not win.

Definition

Class:: FootballCompetition
Method:: whoCanWin
Parameters:: int[]
Returns:: String
Method signature:: String whoCanWin(int[] initialEnergy)
(be sure your method is public)

Constraints

initialEnergy will contain 2 or 4 or 8 or 16 elements.
Each element of initialEnergy will be between 1 and 1000, inclusive.
All elements of initialEnergy will be distinct.

Examples

```
{1, 3}
```
```
Returns: "NY"
```
Team number 1 is has more energy than team number 0, so team number 1 will be the champion.
```
{2, 3, 4, 5}
```
```
Returns: "NNNY"
```
In any scenario, team number 3 with energy 5 will win.
```
{2, 6, 7, 8}
```
```
Returns: "NYYY"
```
The team that plays against the weakest team in the first round will be the champion.

{51, 65, 214, 216, 218, 219, 500, 501}

Returns: "NYYYYYYY"

{480,393,291,113,162,498,90,212,50,87,452,553,564,189,243,332}

Returns: "YYYYYYYYNYYYYYYY"

{5,8,12,3,2,10,14,11,6,1000,7,4,13,15,1,9}

Returns: "NNNNNNNNNYNNNNNN"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.