11675 - Happy Friends

[tryit1]

Code: Select all

10

4 4 0 5
0 1 1 2 2 3 3 1

4 4 0 6
0 1 1 2 2 3 3 1 

4 4 0 35
0 1 1 2 2 3 3 1 


4 4 0 36
0 1 1 2 2 3 3 1 

4 4 0 37
0 1 1 2 2 3 3 1 

4 4 0 47
0 1 1 2 2 3 3 1 



10 9 0 10000
0 1 
1 2 
2 3 
3 4 
5 6 
6 7
7 9
6 8
9 1

10 9 3 10000
0 1 
1 2 
2 3 
3 4 
5 6 
6 7
7 9
6 8
9 1

30 29 15 1000000000
0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15
15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27
27 28 28 29  

30 36 15 1000000000
0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15
15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27
27 28 28 29  
29 1
29 2
17 2
18 2
19 2
19 23
23 3

I get

Code: Select all

Case 1: 1 6 3 5 1
Case 2: 2 5 1 1
Case 3: 7 5 7 7
Case 4: 7 26 7 7
Case 5: 33 26 40 40
Case 6: 954724928 522243248 868722089 868722089
Case 7: 476968169 522243248 259687412 259687412
Case 8: 476968169 518586234 259687412 259687412
Case 9: 945782367 500437378 491146889 491146889
Case 10: 623858145 156758812 218362496 707469520 594504359 982455161 833380645 271795578 982455161 129635338
Case 11: 707469520 812866855 174303658 325608486 466834145 75074564 546781219 833380645 75074564 689924674
Case 12: 110869813 335000887 253184270 570773781 831597252 200401121 383218171 541603351 204386631 461157214 9537668 325116808 716802806 422352629 954373512 375826447 959802501 14468406 175122198 42086943 741604422 551086851 99869556 884737799 447654801 989970233 512238518 245657141 162007002 576753023

[Khongor_SMCS]

I think your input has 10 test cases, output is 12.
And my AC code returns

Code: Select all

Case 1: 7 26 7 7
Case 2: 33 26 40 40
Case 3: 954724928 522243248 868722089 868722089
Case 4: 476968169 522243248 259687412 259687412
Case 5: 476968169 518586234 259687412 259687412
Case 6: 945782367 500437378 491146889 491146889
Case 7: 623858145 156758812 218362496 707469520 594504359 982455161 833380645 271795578 982455161 129635338
Case 8: 707469520 812866855 174303658 325608486 466834145 75074564 546781219 833380645 75074564 689924674
Case 9: 110869813 335000887 253184270 570773781 831597252 200401121 383218171 541603351 204386631 461157214 9537668 325116808 716802806 422352629 954373512 375826447 959802501 14468406 175122198 42086943 741604422 551086851 99869556 884737799 447654801 989970233 512238518 245657141 162007002 576753023
Case 10: 374136232 74471074 648675253 12680690 967169111 314355118 692717992 36186724 120897736 799908442 912116745 833000789 255974432 917788873 891451937 70706912 125159484 608844095 39024006 885125674 430196767 974192846 382840768 838844696 666397592 437820823 703694246 342250646 982950911 683285753

[mak(cse_DU)]

I spent huge time to figure out the solution.

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?

Thanks all problem setter.

[stubbscroll]

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)]

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"


see highlighted section.

[stubbscroll]

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.

[rujialiu]

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.