for second part of the question , i was able to think during contest that we have to store all previous string and for current string check all prefixes which are also suffixes and add their count , but not able to resolve how to do all prefixes part optimally
Just added an editorial. But that G problem doesn't appear DP on Trees to me, the given graph is not a tree. Its solution involves Diophantine equation. There was a Div2 contest just before that where problem D was based on Tree DP, you may check my submission to get the approach etc there. Let me know if you feel otherwise...
for second part of the question , i was able to think during contest that we have to store all previous string and for current string check all prefixes which are also suffixes and add their count , but not able to resolve how to do all prefixes part optimally
If possible also explain last problem of recent div 3 G problem which is based on DP on trees
Just added an editorial. But that G problem doesn't appear DP on Trees to me, the given graph is not a tree. Its solution involves Diophantine equation. There was a Div2 contest just before that where problem D was based on Tree DP, you may check my submission to get the approach etc there. Let me know if you feel otherwise...
grt
Bhaiya if possible then plz try to explain cf div3 recent 3rd,4th question ! 🙏
I haven't checked the contest yet, I'll take a look, thanks for asking!