2018-1C Problem A

Final solution

// Lesson: the complexity of a tree traversal won't blow up if only valid inputs are traversed. Don't be afraid to
// traverse a word tree.
// package, import, etc...

func start() {
  // read T, repeat test() T times...
}

type Tree struct {
	charId     int
	subTrees   map[int]*Tree
	idsNotUsed map[int]bool
}

func newTree(charId int, total int) *Tree {
	idsNotUsed := make(map[int]bool)
	for i := 0; i < total; i++ {
		idsNotUsed[i] = true
	}
	return &Tree{charId: charId, subTrees: make(map[int]*Tree), idsNotUsed: idsNotUsed}
}

func (t *Tree) find(charId int, nextTotals int) *Tree {
	subt := t.subTrees[charId]
	if subt == nil {
		t.subTrees[charId] = newTree(charId, nextTotals)
		delete(t.idsNotUsed, charId)
	}
	return t.subTrees[charId]
}

func test() {
	var N, L int
	mustReadLineOfInts(&N, &L)
	words := make([]string, N)
	for i := 0; i < N; i++ {
		words[i] = mustReadLine()
		assert(len(words[i]) == L)
	}
	translationTables := make([]map[byte]int, L)
	revTranslationTables := make([]map[int]byte, L)
	totals := make([]int, L)
	for i := 0; i < L; i++ {
		cnt := 0
		tt := make(map[byte]int)
		translationTables[i] = tt
		revTt := make(map[int]byte)
		revTranslationTables[i] = revTt
		for j := 0; j < N; j++ {
			char := words[j][i]
			_, existed := tt[char]
			if !existed {
				tt[char] = cnt
				revTt[cnt] = char
				cnt++
			}
		}
		totals[i] = cnt
	}
	t := newTree(-1, totals[0])
	for i := 0; i < N; i++ {
		word := words[i]
		currentT := t
		for j := 0; j < L; j++ {
			char := word[j]
			nextTotal := 0
			if j < L-1 {
				nextTotal = totals[j+1]
			}
			currentT = currentT.find(translationTables[j][char], nextTotal)
		}
	}

	var trav func(t *Tree, buf []int) bool
	trav = func(t *Tree, buf []int) bool {
		if len(t.idsNotUsed) > 0 {
			var oneNotUsedId int
			for id, b := range t.idsNotUsed {
				assert(b)
				oneNotUsedId = id
				break
			}
			buf[0] = oneNotUsedId
			for i := 1; i < len(buf); i++ {
				buf[i] = 0
			}
			return true
		} else {
			if len(buf) == 1 {
				return false
			}
			assert(len(buf) > 1)
			for sid, t := range t.subTrees {
				buf[0] = sid
				if trav(t, buf[1:]) {
					return true
				}
			}
			return false
		}
	}

	wordIds := make([]int, L)
	if trav(t, wordIds) {
		word := make([]byte, L)
		for i := 0; i < L; i++ {
			word[i] = revTranslationTables[i][wordIds[i]]
		}
		stdout.Write(word)
		stdout.WriteByte('\n')
	} else {
		stdout.WriteString("-\n")
	}
}

// boilerplate omitted...

Sample test cases given in question

5
4 1
A
B
C
D
4 2
WW
AA
SS
DD
4 2
AA
AB
BA
BB
3 4
CAKE
TORN
SHOW
5 7
HELPIAM
TRAPPED
INSIDEA
CODEJAM
FACTORY