10911 - Forming Quiz Teams

[Bunda001]

Can someone send here correct code of this program, please?

[andysoft]

Hail!
I cannot think of any DP solution for second day.. Can anyone please give me a small hint on how to solve this problem dynamically?.

Thank you in advance

[Jan]

Since n is small, you can think of Dp (bitmask). 2^16 is small enough. Hope it helps.

[andysoft]

Hello!
Thank you Jan for your hint.
At first look, I thought this hint will not be enough for me to understand how to solve..
But after thinking a bit, I developed an algorithm.


I have an array of 2^16 elements - the elements of array are of type 'double', index is a bitmask, marking which people are taken
First of all, I initialize all bitmasks with two bits in them with simply given distance.. for example if distance from 1st man (0th) to 2nd (1st in zero-numeration) is 15, then a[3]=15 (3 is ..00011 in bits). I also push all these values to queue
Then I make N-1 steps of the following:
****get bitmask from queue
****then I take all n*(n-1) pairs and look if this pair is not present in bitmask.
********if it is really not present, then I take another bitmask = current bitmask + two bits for people from the pair and check value of a[another bitmask]
********if this value is greater, which can be achieved with current pair, I overwrite it and add 'another bitmask' into queue2.
****queue = queue2

Indeed, I used set from STL instead of queue, to avoid repeating (maybe its not needed)


My solution got Accepted in 1.44 time.
I wonder if this algorithm was expected from me

Thank you again, Jan

Good luck

[Shafaet_du]

Why you need a queue? Pick two person(i,j),set corresponding bit and recursively find d[j]+call(mask).

[DD]

I think branch-and-bound with proper tuning is sufficient to solve this problem

[DuDuCt]

Nevermind, got it accepted after declaring hypot in the header.

I got AC in more than 3 seconds.. is there a greedy way to do it or something? The times were really fast..

My timing was .082 sec. I used O(2^n* n) DP. When dividing the original problem into subproblems, you only need to match only one person with (n-1) different persons. You don't need to try every pair.


Regards
Sanny

Can you tell me how to know who are (n-1) different persons.

[@ce]

Getting WA...plzz anyone help...
Getting correct output for all of Larry's testcases...

Code: Select all

AC :)

[brianfry713]

Input:

Code: Select all

1
a 742 294
b 617 319
1
a 816 914
b 405 65
2
a 448 531
b 870 571
c 597 424
d 802 947
3
a 78 498
b 418 317
c 626 886
d 186 452
e 147 299
f 608 165
7
a 617 597
b 196 749
c 254 530
d 935 952
e 483 391
f 652 382
g 497 42
h 990 248
i 546 298
j 67 177
k 595 553
l 178 643
m 829 737
n 575 478
1
a 15 776
b 392 591
8
a 613 478
b 119 709
c 99 547
d 620 602
e 335 442
f 690 116
g 414 324
h 501 926
i 479 171
j 815 787
k 213 657
l 134 643
m 327 788
n 494 600
o 993 609
p 777 948
6
a 896 346
b 446 842
c 461 188
d 523 888
e 267 267
f 372 537
g 728 193
h 672 543
i 357 204
j 418 18
k 153 691
l 17 205
5
a 316 389
b 337 125
c 420 92
d 679 683
e 819 262
f 413 557
g 79 396
h 354 371
i 743 306
j 724 237
3
a 929 599
b 617 333
c 23 36
d 932 460
e 904 731
f 47 321
4
a 830 348
b 721 449
c 401 508
d 755 540
e 626 504
f 875 834
g 830 670
h 907 617
2
a 505 593
b 926 482
c 518 813
d 272 949
5
a 175 679
b 416 460
c 808 895
d 33 246
e 444 529
f 759 434
g 938 199
h 723 74
i 745 503
j 119 243
7
a 712 797
b 969 537
c 349 637
d 275 176
e 315 311
f 177 645
g 60 466
h 273 71
i 795 997
j 131 492
k 250 919
l 546 330
m 743 15
n 760 48
4
a 791 168
b 570 472
c 130 17
d 366 898
e 172 997
f 2 368
g 545 817
h 878 468
5
a 564 741
b 924 100
c 18 695
d 715 173
e 188 564
f 613 458
g 133 638
h 119 781
i 40 296
j 116 136
2
a 113 193
b 561 110
c 927 115
d 273 105
3
a 13 411
b 201 749
c 443 937
d 801 219
e 783 158
f 306 679
2
a 129 7
b 817 866
c 597 425
d 232 953
6
a 345 836
b 86 644
c 261 150
d 423 191
e 292 445
f 193 126
g 754 493
h 402 327
i 175 244
j 613 185
k 270 481
l 300 620
5
a 416 436
b 79 423
c 957 648
d 683 605
e 692 291
f 242 833
g 946 573
h 866 687
i 571 762
j 515 48
2
a 449 451
b 326 72
c 243 62
d 682 596
8
a 809 112
b 535 959
c 296 578
d 182 182
e 473 979
f 501 874
g 137 715
h 91 446
i 208 2
j 741 352
k 249 413
l 863 882
m 207 11
n 945 615
o 987 494
p 606 178
8
a 832 136
b 123 62
c 936 13
d 176 101
e 603 499
f 636 581
g 362 739
h 637 328
i 69 715
j 654 50
k 603 951
l 849 666
m 610 217
n 203 342
o 948 788
p 615 689
5
a 428 441
b 376 482
c 348 529
d 822 876
e 201 619
f 982 251
g 888 530
h 289 696
i 349 628
j 921 930
7
a 828 778
b 119 5
c 483 31
d 410 758
e 226 788
f 215 541
g 918 709
h 747 435
i 256 483
j 684 366
k 347 197
l 85 904
m 192 733
n 772 403
5
a 477 324
b 151 900
c 710 172
d 655 873
e 973 467
f 693 443
g 348 514
h 431 91
i 839 783
j 730 604
4
a 927 978
b 882 932
c 664 702
d 105 764
e 576 125
f 292 119
g 270 166
h 876 464
5
a 342 119
b 252 806
c 319 725
d 817 600
e 73 440
f 734 345
g 239 803
h 419 712
i 283 861
j 214 121
2
a 339 917
b 35 313
c 479 632
d 95 996
5
a 905 829
b 635 386
c 110 156
d 757 644
e 775 617
f 962 520
g 322 508
h 910 891
i 751 741
j 552 883
3
a 468 620
b 933 995
c 626 503
d 499 101
e 145 721
f 316 327
6
a 472 652
b 987 331
c 639 919
d 438 761
e 959 290
f 181 760
g 191 869
h 751 622
i 277 743
j 211 370
k 993 271
l 897 404
2
a 307 903
b 921 929
c 149 623
d 786 262
2
a 704 248
b 699 810
c 790 833
d 282 658
3
a 473 526
b 967 283
c 560 907
d 808 27
e 710 831
f 417 211
1
a 414 805
b 415 112
2
a 677 953
b 814 513
c 216 616
d 314 313
3
a 972 102
b 73 331
c 494 187
d 154 46
e 606 400
f 898 872
3
a 800 581
b 765 543
c 957 604
d 18 878
e 830 684
f 887 385
4
a 103 0
b 315 646
c 748 842
d 863 977
e 164 511
f 557 47
g 137 8
h 880 162
4
a 150 288
b 521 835
c 128 916
d 793 168
e 542 146
f 221 312
g 645 429
h 222 222
6
a 754 227
b 894 728
c 239 307
d 354 57
e 756 796
f 959 491
g 526 635
h 786 937
i 148 50
j 178 391
k 183 316
l 858 324
4
a 977 236
b 148 520
c 500 889
d 643 65
e 959 227
f 466 950
g 303 707
h 462 262
4
a 788 911
b 537 10
c 60 263
d 654 685
e 691 239
f 253 527
g 402 239
h 215 179
5
a 104 327
b 392 421
c 338 747
d 386 41
e 748 805
f 757 379
g 863 209
h 687 357
i 894 873
j 624 950
1
a 553 293
b 820 960
7
a 221 198
b 414 676
c 693 142
d 253 208
e 645 776
f 817 592
g 86 30
h 99 564
i 463 533
j 890 962
k 525 150
l 790 473
m 432 148
n 391 83
2
a 577 903
b 815 590
c 694 252
d 636 647
4
a 411 591
b 873 236
c 957 227
d 481 959
e 181 55
f 17 634
g 784 761
h 233 542
4
a 666 380
b 461 347
c 940 748
d 27 37
e 981 754
f 91 722
g 3 616
h 717 682
8
a 634 554
b 202 887
c 633 114
d 438 383
e 143 650
f 882 913
g 176 66
h 422 952
i 412 213
j 152 169
k 197 139
l 119 597
m 688 609
n 612 425
o 141 369
p 613 542
2
a 815 119
b 752 579
c 708 888
d 30 91
4
a 787 973
b 614 796
c 8 209
d 68 716
e 855 851
f 447 956
g 564 665
h 89 825
2
a 922 884
b 496 98
c 908 386
d 656 0
2
a 363 888
b 608 750
c 412 983
d 468 395
2
a 166 604
b 362 431
c 977 16
d 154 318
6
a 669 882
b 438 420
c 341 553
d 739 227
e 134 728
f 383 740
g 317 794
h 233 436
i 418 926
j 10 336
k 51 576
l 742 614
2
a 448 666
b 984 459
c 99 292
d 962 556
4
a 204 994
b 911 551
c 278 943
d 372 45
e 529 351
f 787 380
g 996 762
h 788 895
7
a 840 470
b 211 309
c 975 322
d 471 349
e 642 959
f 514 260
g 469 293
h 497 507
i 108 19
j 988 129
k 192 153
l 372 28
m 815 572
n 567 824
7
a 572 612
b 451 869
c 770 881
d 855 463
e 934 119
f 451 503
g 16 884
h 352 744
i 240 214
j 322 372
k 49 59
l 251 165
m 537 78
n 583 513
8
a 983 770
b 31 972
c 112 851
d 311 602
e 147 575
f 198 430
g 571 650
h 667 81
i 434 314
j 244 881
k 202 496
l 545 994
m 245 367
n 594 313
o 897 448
p 218 954
2
a 249 616
b 728 419
c 730 542
d 689 303
1
a 338 501
b 583 420
1
a 707 424
b 358 575
7
a 352 467
b 524 437
c 441 287
d 735 117
e 762 337
f 596 643
g 583 377
h 104 14
i 435 124
j 813 407
k 599 975
l 85 150
m 846 872
n 578 199
8
a 470 558
b 910 578
c 792 597
d 37 196
e 621 910
f 671 64
g 660 264
h 537 738
i 842 365
j 490 661
k 163 249
l 538 464
m 239 3
n 849 409
o 677 439
p 687 650
5
a 596 918
b 709 743
c 471 482
d 793 308
e 669 535
f 886 747
g 283 406
h 248 250
i 740 944
j 106 187
6
a 110 725
b 824 133
c 262 649
d 298 500
e 646 949
f 234 215
g 615 78
h 549 406
i 198 923
j 592 775
k 660 636
l 919 998
6
a 553 936
b 122 339
c 232 659
d 459 537
e 360 55
f 317 799
g 787 860
h 195 956
i 189 693
j 307 965
k 203 595
l 484 229
3
a 119 511
b 509 327
c 927 37
d 280 444
e 257 265
f 498 630
2
a 243 88
b 577 154
c 704 561
d 516 364
6
a 396 747
b 53 554
c 757 991
d 164 973
e 484 425
f 752 283
g 11 683
h 817 369
i 634 291
j 611 73
k 558 822
l 65 700
3
a 316 967
b 20 105
c 695 522
d 918 767
e 820 939
f 386 599
4
a 811 453
b 737 967
c 339 252
d 621 438
e 419 155
f 920 946
g 767 30
h 420 477
2
a 386 879
b 674 528
c 50 97
d 864 369
6
a 374 998
b 383 256
c 710 857
d 513 884
e 827 136
f 264 852
g 697 137
h 82 683
i 403 306
j 473 540
k 61 513
l 590 351
3
a 687 25
b 84 330
c 988 550
d 924 81
e 465 935
f 334 470
8
a 470 983
b 524 174
c 312 424
d 797 912
e 217 84
f 624 200
g 713 691
h 732 376
i 656 302
j 679 757
k 531 986
l 973 229
m 843 613
n 77 907
o 931 313
p 295 115
1
a 510 981
b 983 514
3
a 757 311
b 201 328
c 18 381
d 757 604
e 597 441
f 197 412
8
a 729 87
b 59 504
c 347 31
d 799 657
e 587 350
f 645 914
g 584 678
h 191 845
i 956 566
j 323 192
k 393 284
l 993 394
m 841 998
n 594 433
o 321 943
p 29 869
2
a 779 373
b 410 771
c 569 125
d 403 760
6
a 80 94
b 940 447
c 703 962
d 154 585
e 869 716
f 109 547
g 544 552
h 985 640
i 582 828
j 697 996
k 735 301
l 771 760
2
a 896 169
b 619 454
c 317 298
d 68 713
2
a 721 342
b 928 466
c 182 565
d 111 486
8
a 346 37
b 713 622
c 894 173
d 560 708
e 133 886
f 656 319
g 488 328
h 473 551
i 540 106
j 510 790
k 243 298
l 18 852
m 469 399
n 271 583
o 385 956
p 683 253
1
a 395 565
b 148 284
2
a 33 845
b 163 927
c 945 689
d 931 342
4
a 160 138
b 338 897
c 830 458
d 167 881
e 349 229
f 500 440
g 515 995
h 678 443
8
a 763 7
b 156 911
c 755 866
d 792 880
e 569 608
f 640 737
g 844 189
h 349 469
i 807 431
j 260 807
k 664 687
l 36 489
m 680 104
n 619 721
o 398 122
p 130 245
2
a 977 155
b 600 717
c 199 856
d 114 898
4
a 303 538
b 6 469
c 900 342
d 149 813
e 500 160
f 339 813
g 607 226
h 947 18
8
a 35 141
b 962 161
c 316 887
d 603 628
e 173 916
f 813 492
g 117 979
h 281 40
i 46 277
j 867 624
k 463 550
l 740 717
m 56 966
n 263 966
o 912 765
p 596 489
2
a 247 340
b 656 523
c 817 875
d 739 261
4
a 717 764
b 805 116
c 83 998
d 311 541
e 781 950
f 667 464
g 120 520
h 485 413
7
a 87 868
b 464 562
c 902 724
d 938 711
e 276 247
f 198 754
g 752 14
h 731 962
i 456 558
j 641 418
k 420 688
l 468 281
m 638 574
n 694 679
6
a 767 163
b 941 608
c 762 328
d 920 355
e 292 163
f 439 857
g 54 736
h 177 143
i 564 16
j 162 426
k 66 672
l 91 850
6
a 356 8
b 687 675
c 415 740
d 507 540
e 481 23
f 475 525
g 135 526
h 818 638
i 767 992
j 46 243
k 110 600
l 163 753
0

AC output:

Code: Select all

Case 1: 127.48
Case 2: 943.25
Case 3: 565.54
Case 4: 1071.97
Case 5: 1546.76
Case 6: 419.95
Case 7: 1473.92
Case 8: 1374.50
Case 9: 982.77
Case 10: 759.99
Case 11: 714.09
Case 12: 716.48
Case 13: 1148.46
Case 14: 1516.55
Case 15: 1249.68
Case 16: 910.58
Case 17: 548.64
Case 18: 742.48
Case 19: 1218.93
Case 20: 1221.07
Case 21: 1250.79
Case 22: 358.03
Case 23: 1609.13
Case 24: 1558.38
Case 25: 689.34
Case 26: 1301.94
Case 27: 1426.19
Case 28: 1131.35
Case 29: 959.32
Case 30: 803.19
Case 31: 1103.42
Case 32: 1209.15
Case 33: 1074.68
Case 34: 1002.03
Case 35: 682.24
Case 36: 789.45
Case 37: 693.00
Case 38: 779.29
Case 39: 1310.49
Case 40: 1116.43
Case 41: 757.68
Case 42: 1105.15
Case 43: 1219.98
Case 44: 600.37
Case 45: 1039.26
Case 46: 1393.83
Case 47: 718.46
Case 48: 1393.52
Case 49: 621.72
Case 50: 1232.84
Case 51: 1018.82
Case 52: 1369.82
Case 53: 1097.62
Case 54: 1171.64
Case 55: 685.82
Case 56: 488.50
Case 57: 1028.17
Case 58: 1309.31
Case 59: 611.01
Case 60: 891.91
Case 61: 1090.13
Case 62: 1858.23
Case 63: 1573.20
Case 64: 609.04
Case 65: 258.04
Case 66: 380.27
Case 67: 1216.78
Case 68: 1387.35
Case 69: 940.16
Case 70: 1386.57
Case 71: 1193.39
Case 72: 1077.38
Case 73: 612.77
Case 74: 1347.96
Case 75: 1365.98
Case 76: 939.97
Case 77: 1098.88
Case 78: 959.07
Case 79: 1179.48
Case 80: 1331.87
Case 81: 664.69
Case 82: 884.57
Case 83: 1719.21
Case 84: 338.01
Case 85: 1336.61
Case 86: 881.40
Case 87: 347.52
Case 88: 1493.43
Case 89: 374.13
Case 90: 500.98
Case 91: 1089.45
Case 92: 1317.59
Case 93: 771.55
Case 94: 948.02
Case 95: 1821.47
Case 96: 885.37
Case 97: 1266.51
Case 98: 1351.71
Case 99: 1424.71
Case 100: 1188.85

[@ce]

@brianfry...Why is it that I when I run only case 98, i get correct output and when i run all 100 cases together, i get a different incorrect answer for the same case. I have initialized dp array before every test case. Any help?
PS: Same with some more test cases too...

[brianfry713]

2^14=16384 not 16348

[@ce]

Thank you brianfry.

[vhua_no_name]

Hi,
I want to solve this problem using DP. But could not find the technique how to solve it using DP. please someone describe the algorithm.
thanks in advance.

[brianfry713]

Read this thread

[vhua_no_name]

Ya, my things are right. I was Guest up there, and it turns out I forget to declare hypot (otherwise it returns int on the judge). Whoops.

my code gives the same output as yours for the above test cases but still i am getting wrong ans. And i have not declared hypot. i am new to Uva and don't know how to use hypot.
it will be very helpful if you tell me how and when to use it(hypot).

thanks in advance