nownikhil's blog

By nownikhil, 8 years ago, In English

Hi all,

I was trying to solve this problem on spoj. http://www.spoj.com/problems/WILD/

If we treat each evil candidate as a point and consider the cube (0,0,0) — (x,y,z). The problem is reduced to finding the volume of union of cubes. The answer in this case will be m^3 — volume.

The complexity is turning out to be n*n*log(n). Can anyone suggest a better algorithm?

Thanks

Read more »

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

By nownikhil, 9 years ago, In English

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=392&page=show_problem&problem=3235

This problem on UVA was categorized under bipartite matching. I am not able to figure any algorithm for this. If we make a graph, where edge denotes that 2 people can form a couple, wouldn't the problem be of maximum independent set ?? It would be really great if someone can give some hint about this.

Thanks

Read more »

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

By nownikhil, 9 years ago, In English

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2753

I have been trying to solve this UVA problem(11706 — Party Night), but am unable to find a solution to this. Can someone tell how to solve this problem.

Thanks in advance.

Read more »

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

By nownikhil, 9 years ago, In English

http://www.spoj.com/problems/BOMBER/ I was trying to solve this game theory problem. basically at every step we split a block in 4 sub blocks. It is something like kayle's game, and hence its logic can be used. So we need to compute grundy number for every block of size X*Y. I am not able to think of an efficient method for this problem.

There was another problem. Variant of Nim. In this pile sizes should be in increasing order. In one move a person can either remove an entire pile, or reduce its size maintaining the property that pile sizes are strictly increasing in length. Can we simple consider new set of piles where each pile size is the difference between consequtive pile sizes.

Thanks in advance. Any help is greatly appreciated.

Read more »

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

By nownikhil, 9 years ago, In English

Can anyone suggest me a method for finding all the cycles and their lengths in a directed graph. Cycles might be overlapping. Lets say the graph had 2 OVERLAPPING cycles, so answer should be 3 along with their lengths. We must find smaller as well as larger cycles in the graph.

Thanks in advance.

Read more »

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

By nownikhil, 9 years ago, In English

http://community.topcoder.com/stat?c=problem_statement&pm=10573&rd=13900

I couldn't think of any algorithm for this problem, neither an editorial have been posted for the same. Please help me out with this.

Read more »

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

By nownikhil, 9 years ago, In English

This is the link to the problem. https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2630

Can anyone give some hint on how to solve this.

Would it be correct to say that if we have large number of rows, answer would exist only for few columns ?? Since length of slabs in each row equals L, there has to be enough space to move the slabs, hence if no of rows are fairly large, only few columns can have a solution.

Read more »

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