# | User | Rating |
---|---|---|

1 | tourist | 4009 |

2 | jiangly | 3823 |

3 | Benq | 3738 |

4 | Radewoosh | 3633 |

5 | jqdai0815 | 3620 |

6 | orzdevinwang | 3529 |

7 | ecnerwala | 3446 |

8 | Um_nik | 3396 |

9 | ksun48 | 3390 |

10 | gamegame | 3386 |

# | User | Contrib. |
---|---|---|

1 | cry | 164 |

1 | maomao90 | 164 |

3 | Um_nik | 163 |

4 | atcoder_official | 160 |

5 | adamant | 158 |

5 | -is-this-fft- | 158 |

7 | awoo | 157 |

8 | TheScrasse | 154 |

8 | Dominater069 | 154 |

8 | nor | 154 |

- problem $$$A$$$ with one boolean as input and arbitrary output
- problem $$$B$$$ with arbitrary input and one boolean as output

$$$A$$$ can never be an NP problem (only two possibilities $$$(0/1)$$$ and each have a fixed answer regardless of the output).

$$$B$$$ can be an NP problem (example : check whether array can be partitioned into two sets of equal sums)

Given a tree of $$$n$$$ nodes, I need to find **for every directed edge** $$$(a,b)$$$ in it the number of **paths in the tree that start** with this directed edge

This was a subproblem I faced in two recent contests (YAC3 B, Codecraft22 F)

I wrote a recursive DP solution to it in $$$O(2*edges)$$$ which is $$$O(2n-2)$$$, but it got **TLE** in both problems and so far I don't know why

Here is my code :

```
int n,ans=0,k;
vector<pair<int,int>>adj[INF],u;
vector<int>dp(SZ,-1);
int slv(int e)
{
if(dp[e]!=-1){return dp[e];}
int c=1,nd=u[e].second,pr=u[e].first;
for(int i=0;i<adj[nd].size();i++)
{
int x=adj[nd][i].first;
if(x==pr){continue;}
c+=slv(adj[nd][i].second);
}
return dp[e]=c;
}
/// n --> size of the node
/// adj[i] --> the adjacency list, for node i it carries a vector of pairs for each edge of node i : (the index of an edge, the node connected to node i by this edge)
/// dp[x] --> the answer for the required problem above for an edge of index x
```

I suspect this could be due to using recursion, is there a way to optimize calculating the answer for this subproblem? It has been haunting me for days :(

Here are my submissions if you are wondering how I got **TLE:**

YAC3 B

Codecraft22 F

I doubt it is in a subproblem other than this one

Because I have been struggling and keep getting ABC very fast, but still Expert performance, what should i do exactly??

We have an array $$$A$$$ of length $$$N$$$, let's define a function $$$f$$$ which takes 3 parameters $$$(L,R,K)$$$ such that $$$(1 ≤ L ≤ R ≤ N)$$$, $$$f(L,R,0)$$$ = $$$\displaystyle\sum\limits_{i=L}^R (A_i)$$$, and $$$f(L,R,K)$$$ = $$$\displaystyle\sum\limits_{i=L}^R (\sum\limits_{j=i}^R (f(i,j,K-1)))$$$

We are going to call the function $$$f$$$ **$$$Q$$$ Times, What is the best time complexity you can achieve?**

My best time complexity to solve this is using **DP** with **2D prefix sum** to calculate the answer for every possible tuple (i,j,k) using previous tuples in **O(n^2 * maxK)**, Unfortunately...That's not efficient

However, I have found an Extra Greedy+Math+Inclusion-Exclusion-Principle **O(n)** pre-processing and **O(1)** per query solution for **$$$(K=0)$$$** or **$$$(K=1)$$$, but that's all I could do**

Any comments on this function?

Note : since the value of this function may grow rapidly beyond the 64-bit integer datatype limit, you are asked to calculate its value modulo $$$10^9+7$$$

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/13/2024 14:41:26 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|