Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Aritra741's blog

By Aritra741, history, 5 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, 6 months 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, 6 months 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, 7 months 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 i_love_fake123'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, 11 months 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