| | 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.
|