yesnomaybe's blog

Longest palindromic path in Tree
By yesnomaybe, history, 3 years ago, In English

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?

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone please tell the reason for downvotes? I will try to rectify it.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like 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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 

    #define FI ios_base::sync_with_stdio(false); cin.tie(NULL);
int main() {
    FI;
    //
    return 0;
}
    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

how can this solution work can anyone explain? https://www.codechef.com/viewsolution/40864714

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Seems like test cases only contains where tree has a single long chain. :/

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried to solve using hashing in O(n^2) per test case, but I got tl (may be due to modulo operations).

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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)$$$.

→ Reply