Yandex Trainings 3.0

Path?from?“count the number of characters”?to?“compress graph by going to graph on connected components, build common transitive vertex to reduce number of edges, set problem on state graph and solve it bypassing 0-1 BFS” – or just?[Yandex.Training 3.0]?:D

A couple of months ago there was a competition on algorithms from Yandex. I took 1-144th place in the olympiad division during the main stage, and in the final stage I lacked one point to win :)?The funny thing is that I solved the problem with optimal asymptotic, but because of the memory features in python, the solution didn't pass the tests. I will report on this later :0

[Here] I posted all my solutions and a template, which has already implemented the optimal reading and output of data (yes, this is important part of solution). About my general conclusions You can read in a short post [here].