PROBLEM LINK:
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.