It was MATRIX exponent in log(D) time.
But how can handle the turn of friend's happiness?
I solved it. I think someone need hints to solve this problem.
Hints for someone:
step1: Color every node using only two colors.
step2: split the original matrix of graph with two parts(A1 and A2). (matrix[j]=1)
-----> A1 matrix for color 1 and A2 matrix for color 2. (This task up to you)
step3: compute (A1*A2)^(D/2) in log(n) time.(Careful for even and odd D)
step4: print K-th row of resultant matrix.
Note:
I think for every problems in UVA need hints to learn problem solving.
So request to everyone, give hints to learn new technique .
Uva problem setter always try to adapt new problem with new idea.
But how can we learn new Idea?
mak(cse_DU) wrote:step4: print K-th row of resultant matrix.
How did you discover this? I couldn't see that the K was explained in the problem statement. I only saw it in the input format section, without explanation.
mak(cse_DU) wrote:step4: print K-th row of resultant matrix.
Problem description:::
"How did you discover this? I couldn't see that the K was explained in the problem statement. I only saw it in the input format section, without explanation.
N(1 ? N ? 30), M(N-1 ? M ? N*(N-1)/2), K(0 ? K ? N-1) and D(0 ? D ? 1000000000), number of nodes, number of friendships,initial happy person and number of days"
mak(cse_DU) wrote:N(1 ? N ? 30), M(N-1 ? M ? N*(N-1)/2), K(0 ? K ? N-1) and D(0 ? D ? 1000000000), number of nodes, number of friendships,initial happy person and number of days"
see highlighted section.
Thanks! D'oh, can't believe I missed this after reading the problem statement several times, looking for an explanation.
mak(cse_DU) wrote:I think for every problems in UVA need hints to learn problem solving.
So request to everyone, give hints to learn new technique .
Uva problem setter always try to adapt new problem with new idea.
But how can we learn new Idea?
Thanks all problem setter.
Right, you need to keep learning If you can't solve my problems, just ask in this forum. There are quite a few problems of mine not being heavily discussed here. Though there are problems that I haven't even read, I'll try to at least answers questions on problems from Elite problemsetter's panel (I've read most of them). Just ask.