prodipdatta7's blog

By prodipdatta7, history, 6 months ago, In English

Problem link: 26D. Tickets
Editorial: problem D

I have read the editorial of the problem but I'm not getting the reflection principle part. Especially how the reflection principle works here and why every graph ending at the point (m + n,  - 2 - n - k + m) will intersect with the line y = -1?

If anyone here knows the reason please explain me or if you have solved it with another approach can share it with me.
Thank you.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By prodipdatta7, 19 months ago, In English

How can I solve this problem? Any kind of help regarding this problem will be appreciated.

The abridged problem is:
Given a sequence of numbers. You have to perform 3 types of queries.

1 V: Add V to the end of the sequence.
2: remove an element from the end of the sequence.
3 l r: Find the K'th largest number in the range.
`

It is guaranteed that 1 <= l <= r <= the total number of elements in the current sequence.
Problem link

Read more »

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

By prodipdatta7, 20 months ago, In English

Given a connected undirected weighted graph of n (<= 15) nodes and m(<= 1000) edges.
Every edge is assigned a positive integer which is the length of the edge.
In this graph i need to make the degree of every node even by adding some fake edges between nodes.
The cost of adding a fake edge is the length shortest path between this nodes in the initial graph.
It is obvious that i can use floyd warshall algorithm to compute the shotest path between every pair of nodes. < br> How can I add fake edges with minimum cost ?

Actually this is needed as a sub-problem of another problem i'm trying to solve but can't afford an efficient way.
link: 1086 — Jogging Trails

Your any kind of help will be cordially accepted.
Thanks.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By prodipdatta7, history, 20 months ago, In English

Hello Codeforces!
problem link: Connect and Disconnect
my buggy solution:

Spoiler

I have read the tutorial from here and have tried to solve the problem linked above. But I'm getting WA on test 7. Can't find the bug of my code.
I need help to find out the bug.
please help me.

StayAtHome

TIA.

Read more »

 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it

By prodipdatta7, 3 years ago, In English

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 :)

Read more »

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

By prodipdatta7, history, 3 years ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

By prodipdatta7, history, 3 years ago, In English

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

Read more »

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

By prodipdatta7, history, 3 years ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

By prodipdatta7, history, 4 years ago, In English

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 :)

Read more »

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

By prodipdatta7, history, 4 years ago, In English

Can anyone suggest me some useful blog or resources where I can learn Square root decomposition and Mo's algorithm? I am a beginner and I am very interested to learn SRD...please help me.. (Sorry for my poor English...)

Read more »

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