JOIN Problem Statement
Contest: Marathon Match 108
Problem: CrosswordPuzzler

## Introduction

A crossword puzzle is a two-dimensional grid, where each space is either open or blocked off. Each open space is intended to be filled with a letter, such that contiguous letters read off either horizontally or vertically, each form a word. Single letters that are part of a word in one orientation are ignored in the opposite orientation. A simple example (blocked off cells are indicated by a hyphen '-').

```-CLOCK--
BIO-A---
-SWITCH-
```

Horizontally, we see the words CLOCK, BIO, and SWITCH. Vertically, we find CIS, LOW and CAT. Note that the A in CAT, when read horizontally, being only a single letter, is ignored. The same applies for the B in BIO (and other single letters) when read vertically.

## Problem Definition

You will be given the size of a puzzle to create, in terms of int width and int height. You will also be given a list of "words" that may be used in String[] dictionary. You should return a String[] representing a crossword puzzle, akin to the example shown above, using as many of the words as possible.

The width and height of the return must match what is specified by the input. Every word that appears in the returned puzzle must be one from the provided dictionary, and no word may be repeated. Failure in any of these requirements will score a -1 for the test case. It is not necessary to use all possible dictionary words in the puzzle.

## Scoring

Your raw score for each test case (that produces a valid return) will be calculated as follows:

• Each word used in the puzzle will score points based upon the length of the word.
• A word of length i will score Fib(i) points.
• For each unused cell left in the puzzle, you will lose 1 point.
• If the result is less than 0, you will score a 0 for the test case.

In the example above, SWITCH would score 8 points, CLOCK would score 5 points, while the 4 words of length 3 would each score 2 points. There are 9 cells unused. So the score would be 8 + 5 + 4 * 2 - 9 = 12.

Your overall score will be calculated using relative scoring. That is to say, each test case on which you score greater than 0 will be worth YOURS / BEST points towards your overall score, where YOURS is your score on a test case, and BEST is the highest score anyone achieved on that case. Those values are added, divided by the number of test cases, and the result is scaled to 1000000.

## Test Case Generation

• The width and height are chosen, uniformly at random, in the range [10,50].
• A dictionary length is chosen, uniformly at random, in the range [width * height / 4, width * height].
• A set of rules is created to form a "language":
• A set of 27 distributions is created.
• The first represents the probability of each letter being at the start of a word.
• The other 26 distributions each represent the probability of the next letter to be selected in a word.
• To create a distribution, we start with letter A. We then, with 0.6 probability, add the current letter to the distribution, or alternately, with a 0.4 probability, move on to consider the next letter.
• For each word, a length is chosen by randomly selecting three values (with replacement) from {1, 1, 2, 2, 3, 4}, and computing the sum.
• Each word is then created according to the rules of the language.

## Offline Tester

An offline tester is available here.

## Notes

• The time limit is 10s per test case.
• The memory limit is 1GB.
• There are 10 example cases, 50 provisional tests, and 1000 system tests.
• The first two example test cases use non-standard generation, and a fixed, simplified dictionary, to help facilitate testing.

### Definition

 Class: CrosswordPuzzler Method: createPuzzle Parameters: int, int, String[] Returns: String[] Method signature: String[] createPuzzle(int width, int height, String[] dictionary) (be sure your method is public)

### Examples

0)

```width = 8, height = 3
Dictionary Length = 14
CLOCK
BIO
SWITCH
CIS
LOW
CAT
DOG
TURTLE
LION
MULE
ANT
ELEPHANT
POSSUM
TURKEY
```
1)

```width = 7, height = 4
Dictionary Length = 14
CLOCK
BIO
SWITCH
CIS
LOW
CAT
DOG
TURTLE
LION
MULE
ANT
ELEPHANT
POSSUM
TURKEY
```
2)

```width = 18, height = 12
Dictionary Length = 121
```
3)

```width = 21, height = 27
Dictionary Length = 189
```
4)

```width = 39, height = 31
Dictionary Length = 431
```
5)

```width = 43, height = 44
Dictionary Length = 835
```
6)

```width = 14, height = 28
Dictionary Length = 139
```
7)

```width = 27, height = 18
Dictionary Length = 282
```
8)

```width = 30, height = 43
Dictionary Length = 976
```
9)

```width = 25, height = 46
Dictionary Length = 299
```

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)2010, TopCoder, Inc. All rights reserved.