Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

prodipdatta7's blog

By prodipdatta7, 6 months ago, , Problem: 13101 — Tobby On Tree

Solution: Using HLD or Using HLD

The problem is, You are given a tree. In every node, there is a value assigned to it and also given some query.

Query:

1 u v: compute the gcd on the path from u to v.

2 u x: Change the value of the node u to x.

I have written a code of HLD and submitted but it gave me TLE. I haven't found anything in the code to optimize.

In this case, I need help to optimize the code if it is possible. Please help me if you are free.

Thanks in Advance :)

By prodipdatta7, history, 6 months ago, , Hello Codeforces!

Recently I have solved some problem with Articulation Bridge. Then I have come up with a problem that can be solved using Bridge but till now I can't figure out an appropriate solution.

Problem Description

==================

You are given a connected undirected graph of n nodes and m edges and an integer k.

Now the question is, What is the maximum number of connected components you can create by deleting exactly k edges (k <= m)?

Addition: How to solve the problem if there are Q queries of k?

time limit: 1s for a single case, 2s for the query. memory limit: 512 MB.

Note: if k <= number_of_bridges in the graph, then it is easy to prove that the answer will be k + 1.

Please give me some hints/resources that how can I come up with an efficient solution... By prodipdatta7, history, 10 months ago, , Hello guys, I am searching for some OJ problems which is solvable using Manacher's algorithm. So far I have found some problems like 1 . problem 1 2 . problem 2 3. problem 3 4. problem 4 I will be thankful to you if u provide me some more problems on this algorithm that u know. Thanks in Advance:). By prodipdatta7, history, 16 months ago, , Given a graph of n nodes and m edges. The number of nodes and edges can have at most 100000. After adding each edge to the graph, you have to calculate the Minimum Spanning Tree of the current graph.

it is not any OJ problem. The problem idea has come to my mind but I can't figure out any solution except brute force. Is it possible to write a solution that will pass within 2s? I will be thankful to u if u share any idea related to the problem solution... mst,
By prodipdatta7, history, 2 years ago, , Is there any efficient way to calculate the number of digits and sum of digits in the n'th Fibonacci number?? Range of n can have 1 <= n <=10^18...Any answer related to this topic will be appreciated... Thanks :) By prodipdatta7, history, 2 years ago, , 