This is word search problem but constraints seem to be quite strict. Can somebody help with a solution which could pass time limit?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 141 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.09.2026 10:46:36 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
How about dp[x][y][i] where (x,y) is the position in the grid and i is the position in the word you're searching? Number of states per word is at worst 100*100*30, transition is 4, which means you'll be able to handle a bunch of maximal words, around 200 or so. Or is the input bigger?
EDIT: I didn't read the problem correctly, "Each grid cell can only be used once." Sorry, thinking on how to fix that.
No input is same. Can you help in code or more detailed explanation for this?
How do you handle not using some cell more than once?
That limit sounds very similar to the longest path problem, for which no polynomial solution is known. I personally doubt we can avoid something exponential on the word's length.
Given that it's a recruitment problem, maybe we can assume that words are indeed English and therefore we're ok with some heuristics appended to dp+backtracking?