F. Coupled Polygons

Codeforces

IDCF10054F

Time9000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

A nice polygon is defined as: A nice polygon can be encoded by a string consisting of only four type of characters: N, E, W and S standing for North, East, West and South, respectively. The polygon can be reconstructed from the string by drawing the edge following the direction described, with each character represents exactly 1 unit long. For example, the following 2 polygons are encoded as EEEESSSSWWWNNESENNWWWN and NNNEEESSWNWSSW, respectively. A nice polygon B is said to be a perfect match for a nice polygon A if: For example, the light-colored polygon NNNEEESSWNWSSW is a perfect match for the dark-colored polygon EEEESSSSWWWNNESENNWWWN, illustrated as follows: In contrary, the following two polygons (light and dark) cannot form a square with no holes inside, hence they cannot be a perfect match for each other. The following two polygons are not a perfect match for each other either, as they cannot form a square without overlapping each other In the following example, the two polygons form a perfect square but the light-colored polygon is not a perfect match for the dark-colored polygon, as the light-colored polygon is not the smallest one to form a square. The dark-colored polygon is, however, a perfect match for the light-colored polygon. Given a nice polygon A, your task is to find a nice polygon B such that B is a perfect match for A. The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 30. The following lines describe the datasets. Each dataset has one string representing the polygon A on a single line. The string consists of only N, E, W and S and contains at most 100, 000 characters. For each dataset, write on one line a string representing the nice polygon B that is a perfect match for A. If there are multiple answers, write out the one that come first lexicographically. If there is no solution, write out the string NONE on one line. ## Input The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 30. The following lines describe the datasets.Each dataset has one string representing the polygon A on a single line. The string consists of only N, E, W and S and contains at most 100, 000 characters. ## Output For each dataset, write on one line a string representing the nice polygon B that is a perfect match for A. If there are multiple answers, write out the one that come first lexicographically. If there is no solution, write out the string NONE on one line. [samples]

**Definitions** Let $ A $ be a string over the alphabet $ \Sigma = \{N, E, W, S\} $, representing a closed polygonal path in the plane, where each character denotes a unit-length step in the corresponding cardinal direction. Let $ P_A $ be the polygonal path defined by $ A $, starting at the origin and following the sequence of directions. The path is closed if and only if the net displacement is $ (0,0) $. A polygon $ B $ is a **perfect match** for $ A $ if: 1. $ P_A $ and $ P_B $ together form a **filled square** with **no holes** and **no overlaps**. 2. $ P_B $ is the **smallest** such polygon (in terms of enclosed area) that, when combined with $ P_A $, forms a square. 3. The union $ P_A \cup P_B $ bounds a **solid axis-aligned square**. **Constraints** 1. $ |A| \leq 100{,}000 $ 2. $ A $ represents a **closed** polygon (net displacement: $ \sum \vec{d}_i = (0,0) $) 3. The square formed by $ A $ and $ B $ must have integer side length and axis-aligned boundaries. **Objective** Given $ A $, find the lexicographically smallest string $ B \in \Sigma^* $ such that $ B $ is a perfect match for $ A $. If no such $ B $ exists, output `NONE`. **Lexicographic order**: $ N < E < S < W $

API Response (JSON)

{
  "problem": {
    "name": "F. Coupled Polygons",
    "description": {
      "content": "A nice polygon is defined as: A nice polygon can be encoded by a string consisting of only four type of characters: N, E, W and S standing for North, East, West and South, respectively. The polygon c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 9000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10054F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A nice polygon is defined as:\n\nA nice polygon can be encoded by a string consisting of only four type of characters: N, E, W and S standing for North, East, West and South, respectively. The polygon c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ A $ be a string over the alphabet $ \\Sigma = \\{N, E, W, S\\} $, representing a closed polygonal path in the plane, where each character denotes a unit-length step in the corresp...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments