Problem Statement |
| | Introduction
You are given a polymer molecule modeled as a chain of L segments on 2D plane. Each segment of the chain has length of 1 and is parallel to the x or y axis. Thus, the chain can be represented as a sequence of turns clockwise and counterclockwise and straight moves. Given such a sequence, the chain itself can be decoded as a trajectory of a point which starts at arbitrary point of the plane, moves one unit in any direction and then changes movement direction accordingly to the elements of the sequence, moving one unit after each direction change. For the purposes of modeling and visualization, the starting point is chosen as (0,0), and the starting direction is chosen as east (so the coordinates of the first interior node are (1,0)).
Thus, the polymer on the image consists of L=10 segments. It has L-1 interior nodes and is described with sequence {-1, -1, 1, 1, -1, 1, -1, 1, 1} (each element of the sequence corresponds to one interior node).
Problem
You can modify the given polymer using mirror operation: choose one of the interior nodes, immobilize the part of the chain from the start to the chosen node and mirror the rest of the chain with respect to the last segment before the chosen node (the polymer on the image is mirrored at interior node 5, note that indices of interior nodes are 0-based). No two nodes may coincide after the mirroring. Your task is to find the sequence of mirror operations which minimizes the area occupied by the chain.
Implementation Details
Your code should implement a method mirrorSequence(int[] directions). directions gives you the initial layout of the polymer chain: each element can be 1 (for counterclockwise turn), -1 (for clockwise turn) or 0 (for straight move). You have to return
a int[] which contains the list of mirror operations you want to perform. Each mirror operation is described with the index of the interior node which you choose as a mirroring one. You can do at most L/8 (integer division) mirror operations, where L is the number of segments in the chain.
Scoring
Once all mirrorings are done, the area occupied by the polymer chain after all mirrorings is calculated as (xmax-xmin)*(ymax-ymin) (minimums and maximums are taken over all nodes of the chain). Your score for a test case is L/area. Your overall score is a sum of individual scores over all test cases.
Tools
A visualization tool is provided for offline testing. It also allows manual play. |
| |
Definition |
| | | Class: | PolymerPacking | | Method: | mirrorSequence | | Parameters: | int[] | | Returns: | int[] | | Method signature: | int[] mirrorSequence(int[] directions) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The initial layout of the chain is generated node-by-node, on each step the next direction is chosen randomly among all possible directions (left, right and straight, if they don't produce coinciding nodes); if straight is not the only possible direction, it is chosen with smaller probability than left and right. If on some step there is no valid direction, the chain is re-generated from the scratch. |
| - | The memory limit is 1024 MB and the time limit is 10 seconds (which includes only time spent in your code). There is no explicit code size limit. |
| - | There are 10 example test cases and 100 full submission test cases. |
| - | Note that if you mirror the sequence at index i, then i switches from -1 to 1 (and vice versa) and all indices greater than i also reverse. |
| - | Invalid return of any kind (invalid node index, a mirror operation which produces coinciding nodes etc.) results in zero score for that test case. |
| |
Constraints |
| - | The polymer chain will contain between 100 and 500 segments, inclusive. |
| - | The initial layout of the chain will not contain coinciding nodes. |
| |
Examples |
| 0) | |
| | | Returns: "seed = 1
L = 154" | |
|
| 1) | |
| | | Returns: "seed = 2
L = 182" | |
|
| 2) | |
| | | Returns: "seed = 3
L = 335" | |
|
| 3) | |
| | | Returns: "seed = 4
L = 233" | |
|
| 4) | |
| | | Returns: "seed = 5
L = 294" | |
|
| 5) | |
| | | Returns: "seed = 6
L = 409" | |
|
| 6) | |
| | | Returns: "seed = 7
L = 111" | |
|
| 7) | |
| | | Returns: "seed = 8
L = 408" | |
|
| 8) | |
| | | Returns: "seed = 9
L = 240" | |
|
| 9) | |
| | | Returns: "seed = 10
L = 209" | |
|
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)2020, TopCoder, Inc. All rights reserved.