Aritra741's blog

By Aritra741, history, 2 months ago, In English

Problem source: click

The problem states that you'll be given some queries of 2 types. You will either be asked to add a binary digit at the end of the existing string or you'll be asked to delete the last digit. After each operation, you're required to print the longest palindromic substring of that string.

I am aware of a solution involving hashing (Editorial). But I'm wondering how the regular palindromic tree can be modified to handle this.

Read more »

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

By Aritra741, history, 8 months ago, In English

I was wondering if it's possible to use Merge Sort Tree to find out the sum of K-largest numbers in a range. I've seen people solve it using Wavelet tree and Persistent Segment Tree. I failed to implement Merge Sort Tree in such a way that it solves the given task and now wondering if it's possible to do so.

Read more »

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

By Aritra741, history, 8 months ago, In English

I was trying to solve this(LightOJ 1370) problem. When I failed to come up with a memory efficient solution, I looked at some AC solutions.

Interestingly, the solutions used a property that states that the minimum number that has a phi value greater than or equal to a given number, must be the first prime number greater than the given number. For example, For 20, the answer is 23. I am looking for a proof of this property.

Read more »

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

By Aritra741, history, 19 months ago, In English

Hi. I've been struggling to solve this problem from UVA.

It asks for the number of lattice points ( points with integer co-ordinates ) on a given line segment. But the endpoints on the segment can be fractions. I'll appreciate it a lot if someone tells me how this problem can be solved.

Read more »

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

By Aritra741, history, 21 month(s) ago, In English

The problem is the following one:

Given an equation ax+by+cz=d, where a,b,c,d<=1e8 , find the number of non-negative integer solutions to this equation.

It will be very helpful if you provide me with an approach to solve this problem.

Problem source: UVA 12775

Read more »

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

By Aritra741, history, 21 month(s) ago, In English

The problem goes like this: You have a book with n ( n<=10^7 ) pages. You can flip exactly X pages to the right and exactly Y pages to the left. If you're initially on page 1, what is the minimum number of moves to go from page 1 to page A? (**100 test cases**)

You can find the problem Here( UVA 11312- Flipping Frustration ).

I will be very thankful if you provide me with a solution.

Read more »

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

By Aritra741, history, 21 month(s) ago, In English

Given a graph with n(<=100) vertices and m( <=n(n-1)/2 ) edges, you are asked to find a spanning tree with the minimum difference between the biggest and the smallest edge of the tree.

The problem can be found Here (UVA 1395). I can't figure out an efficient way to solve this. Any kind of help is appreciated.

Update: Got AC using fake123_loves_me's approach. this is my code if anyone is interested.

Read more »

Tags mst, dsu
 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

By Aritra741, history, 2 years ago, In English

I recently came across a problem in SPOJ that asks the minimum length of the cycles starting at each node of the graph. For details: Link .

I solved it by considering each node as the root and found the minimum length cycle with BFS. You can find my code Here .

Now I'm wondering how it could be solved if there were 10^5 nodes instead of 2000. Any kind of help is appreciated.

Read more »

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