http://www.spoj.com/problems/NWERC11A/
I have been trying to solve this problem but am getting TLE for larger
inputs.
Can't come up with an optimal approach!!
--
The length of the cycles could be related to N, and the number of the
cycles could be exponentially related to N, so printing them in linear
time is not possible, even if you could detect them.
Don
On Jan 16, 12:00 am, marti amritsa...@gmail.com wrote:
Detect and *print *all the cycles present
Thanks all for solutions, but this problem can also be solved using DP
right ???
On Wednesday, 16 January 2013 01:57:26 UTC+5:30, Don wrote:
Sprague–Grundy theorem
On Jan 12, 6:28 pm, Nguyễn Thành Danh danhnguyen0...@gmail.com
wrote:
Can you please explain by which theorem you use to
Sure, but why? The solution is n%3. DP will by more complex and
slower.
On Jan 16, 11:43 am, siva sivavikne...@gmail.com wrote:
Thanks all for solutions, but this problem can also be solved using DP
right ???
On Wednesday, 16 January 2013 01:57:26 UTC+5:30, Don wrote:
Sprague–Grundy
Ya I'm aware, Just wanted to confirm. Suppose if the problem can't be
reduced to a mathematical formulae , then DP must be the reliable solution
for this kind of problems.
That's why wanted to know exact DP solution also..
On Wednesday, 16 January 2013 22:42:52 UTC+5:30, Don wrote:
Sure, but
The DP solution is to mark the winning position as winning. Then mark
any positions which can move to a winning position as losing and the
rest as winning.
On Jan 16, 12:21 pm, siva sivavikne...@gmail.com wrote:
Ya I'm aware, Just wanted to confirm. Suppose if the problem can't be
reduced to a
Okay,in the best complexity, whats your method??
On Wednesday, January 16, 2013 8:57:46 PM UTC+5:30, Don wrote:
The length of the cycles could be related to N, and the number of the
cycles could be exponentially related to N, so printing them in linear
time is not possible, even if you
Tarjan's Algorithm can be used to find strongly connected sets of
nodes in linear time. Each strongly connected component contains one
or more cycles. But there could be a lot of them, so enumerating them
will not be O(N) if N is the number of nodes.
On Jan 16, 12:40 pm, marti
int countRight[n][n];
int countDown[n][n];
int i,j,s;
int bestI, bestJ, max=0;
int lastRight = n;
int lastDown = n;
// Start by setting countRight[i][j] to the number of consecutive
black pixels starting at (i,j) and moving right
// and countDown[i][j] to the number of consecutive black pixels
Root the tree at an arbitrary node and preprocess the tree using heavy
light decomposition.
For each query (A,B), find C = LCA(A,B) (It can be done in O(log n) time
now.),
now the required answer is min(level(A), level(B)) - level(C).
On Sun, Jan 13, 2013 at 7:43 AM, Danh Nguyen
This is a impartial game similar to *Take Away Game* that can be solved
using game theory.
solution of *lucifier* is correct.
On Wed, Jan 16, 2013 at 1:57 AM, Don dondod...@gmail.com wrote:
Sprague–Grundy theorem
On Jan 12, 6:28 pm, Nguyễn Thành Danh danhnguyen0...@gmail.com
wrote:
Can you
Looking at this, I realized that I need to reset lastRight=lastDown=n
inside the first loop, before the for(j=n-1 loop
On Jan 16, 2:59 pm, Don dondod...@gmail.com wrote:
int countRight[n][n];
int countDown[n][n];
int i,j,s;
int bestI, bestJ, max=0;
int lastRight = n;
int lastDown = n;
//
int countRight[n][n];
int countDown[n][n];
int i,j,s;
int bestI, bestJ, max=0;
int lastRight, lastDown = n;
// Start by setting countRight[i][j] to the number of consecutive
// black pixels starting at (i,j) and moving right
// and countDown[i][j] to the number of consecutive black pixels
//
13 matches
Mail list logo
