Олимпиадный тренинг

Задача . Валидация дерева


Задача

Темы:
Проверьте, является ли данный JSON корректным деревом решений.

Дерево корректно, если:
  • Есть узел с id=0 (корень)
  • Все ссылки left_child и right_child указывают на существующие узлы
  • Нет циклов (каждый узел кроме корня имеет ровно одного родителя)
  • Все листья достижимы из корня

Формат входных данных
JSON с предполагаемым деревом решений.

Формат выходных данных
VALID если дерево корректно, иначе INVALID

 
Примеры
Входные данныеВыходные данные
1 {"nodes": [{"id": 0, "type": "decision", "feature_index": 3, "threshold": 0.6359, "left_child": 1, "right_child": 2}, {"id": 1, "type": "decision", "feature_index": 0, "threshold": 0.4149, "left_child": 3, "right_child": 4}, {"id": 2, "type": "decision", "feature_index": 0, "threshold": 0.4743, "left_child": 5, "right_child": 6}, {"id": 3, "type": "leaf", "class": 1}, {"id": 4, "type": "leaf", "class": 0}, {"id": 5, "type": "leaf", "class": 0}, {"id": 6, "type": "leaf", "class": 0}]}
VALID
2 {"nodes": [{"id": 1, "type": "leaf", "class": 0}, {"id": 2, "type": "leaf", "class": 1}]}
INVALID

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python1
Комментарий учителя