Problem Link : https://www.codechef.com/STRG2020/problems/PADTREE
Problem : Given a tree, where each node is labelled using lowercase latin character. Find the longest palindromic path. (T <= 15 and N <= 5000)
My Idea : Just like finding a longest palindromic substring, we maintain dp[i][j]. And process this dp from length = 1 to length = 2 and so on... We use LCA to find path length and transition states.
My solution : https://www.codechef.com/viewsolution/40866046 Solution summary : I precompute all N^2 paths and sort them by their path length and process as mentioned above. But I got TLE. Complexity — O(T * N^2 Log(N))
Solution by CoderAnshu : https://www.codechef.com/viewsolution/40861653 Solution summary : Uses similar approach but instead of precomputing paths, he expands set from length 1 by keeping queue. Can you please explain the time complexity? And perhaps where I might be going wrong?
Can someone please help with the above problem?
Can someone please tell the reason for downvotes? I will try to rectify it.
I didn't read his code, but looks like his algorithm is $$$O(TN^2)$$$ at least.
How to get rid of $$$O(\log n)$$$? Well, there are three different places.
1) Sorting. You sort values by length of the path, which is at most $$$n$$$, so counting sort will work.
2) $$$O(n^2)$$$ calls to LCA. You can precompute it all in $$$O(n^2)$$$ (the idea is: take direct parent of a vertex with biggest depth and take precomputed lca from resulting pair)
3) $$$O(n^2)$$$ calls to K-th parent. Again, precompute in $$$O(n^2)$$$.
So I did that and added some constant optimizations, here. It is WA. But your solution gives wrong answer on sample test, so that's fine, I guess.
UPD: I copied his code and tested it on a test, where a tree is a line and all letters are 'a'. His solution runs for 3.5 seconds locally (while your initial solution takes 7 secs). It is actually $$$O(N^2 \log N)$$$ because of LCA, but the constant is much better than yours
Maksim1744 Thanks for all the suggestion.
Btw your solution gets accepted : https://www.codechef.com/viewsolution/40900085
Only difference is that I commented Fast-Input line. Also while precomputing lca, you need to use count sort.
Bit cleaned solution : https://www.codechef.com/viewsolution/40900051 If anyone wants to check it out. Complexity is O(N^2) but still runs quite slow compared to CoderAnshu code with complexity O(N^2LogN)
So, I was confused when you said my solution gives wrong answer on sample test. Because on my machine it doesn't give wrong answer. Then I figured that when I take input from file [instead of directly taking it from terminal] it gave wrong answer. This is very confusing.
Can someone please explain why is it the case? I am using fast input as below
You mixed scanf and cin. No wonder it doesn't work without sync.
https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio
how can this solution work can anyone explain? https://www.codechef.com/viewsolution/40864714
Seems like test cases only contains where tree has a single long chain. :/
I tried to solve using hashing in O(n^2) per test case, but I got tl (may be due to modulo operations).
Btw, this exact problem, but with tighter constraints ($$$n \leq 50~000$$$), appeared on COCI 2019/2020, Round 3 (task Lampice).
You can find the editorial here, it describes a solution with complexity $$$O(n \log^2 n)$$$.