10911 - Forming Quiz Teams

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Bunda001
New poster
Posts: 6
Joined: Wed Jan 02, 2008 12:45 pm

please

Post by Bunda001 » Sun Jan 06, 2008 12:04 pm

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

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 10911 - Forming Quiz Teams

Post by andysoft » Sun May 04, 2008 2:05 pm

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
Now I lay me down to sleep...
my profile

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10911 - Forming Quiz Teams

Post by Jan » Sun May 04, 2008 2:28 pm

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

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 10911 - Forming Quiz Teams

Post by andysoft » Sun May 04, 2008 5:30 pm

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
Now I lay me down to sleep...
my profile

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10911 - Forming Quiz Teams

Post by Shafaet_du » Wed Jun 29, 2011 6:24 pm

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

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10911 - Forming Quiz Teams

Post by DD » Fri Feb 22, 2013 9:48 am

I think branch-and-bound with proper tuning is sufficient to solve this problem :D
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

DuDuCt
New poster
Posts: 1
Joined: Wed Jun 05, 2013 7:43 am

Re:

Post by DuDuCt » Wed Jun 05, 2013 7:51 am

Sanny wrote:
Anonymous wrote: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. :D

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 10911 - Forming Quiz Teams

Post by @ce » Wed Jun 05, 2013 10:22 am

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

Code: Select all

AC :)
Last edited by @ce on Thu Jun 13, 2013 6:26 am, edited 1 time in total.
-@ce

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10911 - Forming Quiz Teams

Post by brianfry713 » Tue Jun 11, 2013 11:33 pm

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
Check input and AC output for thousands of problems on uDebug!

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 10911 - Forming Quiz Teams

Post by @ce » Wed Jun 12, 2013 5:57 am

@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...
-@ce

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10911 - Forming Quiz Teams

Post by brianfry713 » Thu Jun 13, 2013 1:07 am

2^14=16384 not 16348
Check input and AC output for thousands of problems on uDebug!

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 10911 - Forming Quiz Teams

Post by @ce » Thu Jun 13, 2013 6:26 am

Thank you brianfry.
-@ce

vhua_no_name
New poster
Posts: 8
Joined: Sat Dec 21, 2013 8:48 pm

Re: 10911 - Forming Quiz Teams

Post by vhua_no_name » Thu Feb 13, 2014 7:31 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10911 - Forming Quiz Teams

Post by brianfry713 » Fri Feb 14, 2014 12:35 am

Read this thread
Check input and AC output for thousands of problems on uDebug!

vhua_no_name
New poster
Posts: 8
Joined: Sat Dec 21, 2013 8:48 pm

Re:

Post by vhua_no_name » Sun Feb 16, 2014 10:59 am

Larry wrote: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

Post Reply

Return to “Volume 109 (10900-10999)”