SCRABBLE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Kulik
Tester: Istvan Nagy
Editorialist: Xellos

DIFFICULTY:

CHALLENGE

PREREQUISITES:

none

PROBLEM:

You’re playing Scrabble on a graph with limited information about tiles in the queue and with some tiles already placed on the graph. Maximise your total score.

IDEA:

A stupid idea to start: just ignore the vertices with previously placed tiles, always try to find a word in the queue and place it on some free path; if it’s impossible or you have some trash tiles among the letters of that word in the queue, just place them on some vertices. (It wouldn’t get many points, I know.)

This is a nasty challenge problem and I didn’t play around with it, so I don’t know what would work and what wouldn’t. It’d be best if people who tried it wrote their approaches.

AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.
The tester’s solution can be found here.

RELATED PROBLEMS:

//