COVID-19 and corresponding lockdowns have severely impacted millions of customers of ABC bank. There are 100,000 customers who always used to pay their credit card payments on time. However, this year they have been unable to make their payments in time due to financial stress during the pandemic.
ABC bank would like to proactively offer financial help to a select set of “Best Customers” amongst these 100,000 customers. They have curated a list of 500 ‘Best Customers’ from their database. You are required to build an efficient algorithm to identify similar ‘Best Customers’ out of the base of 100,000 customers.
Data
You have been provided with two datasets:
- Best Customers: This dataset contains the list of best customers as identified by the ABC Bank, along with some relevant attributes such as ‘income’ and ‘annual spend on the card’.
The variables are in the following order, separated by a space:
Customer ID(String), Income(Float), Annual Spend(Float)
An example record is as follows:
69458744 865000 1245600
- Customer Universe: This dataset contains the list of all other customers in the database of ABC Bank card holders, with the same attributes such as ‘income’ and ‘annual spend on the card’.
The variables are in the following order, separated by a space:
Customer ID(String), Income(Float), Annual Spend(Float)
An example record is as follows:
856120297952 378000 170335
*Please note that Income and Annual spend should not be negative or missing for a record to be considered for the algorithm. All the customers with negative or missing field values should be excluded.
Approach
For data point p in Customer Universe table, find the Nearest Neighbor q (Using Euclidean Distance) in the Best Customer table with the least distance. Lets call the distance between p and q as d.
Next find the Nearest Neighbor of q within the Best Customer table (r). Lets call the distance between q and r as D.
If d/D < 1 then flag q as Best Customer.
*Please note that the all distances should be rounded off to at least 6 decimal places.
Format
The input file is as follows:
First line contains an integer N (N >= 0), which is the number of records in the Best Customer Dataset. The next N rows constitute the Best Customer data.
The line just below the best customer data contains an integer M (M >= 0), which is the number of records in the Customer Universe Dataset. Thereafter, the next M rows constitute the Customer Universe data.
The output file is as follows:
Each line should contain one Customer ID. Please note that the sequence of output matters. The output should be sorted in the ascending order (or alphabetical order) of Customer ID.
Please refer to the sample data below:
SAMPLE INPUT
500
69458744 865000 1245600
37019350 886000 1255312
20164932 607000 843730
23499616 664000 916320
37546903 689000 946407
32263462 1437000 1896840
36113297 645000 815128
78594944 880000 1108800
15163374 698000 872625
49221219 970000 1185328
48032937 566000 690520
90571652 840000 934272
50763551 915000 1012932
3441059 557000 616357
12994701 732000 809701
1941426 1072000 1185357
55095218 799000 876088
70372107 1325000 1444250
65458012 804000 860280
80532537 506000 541420
50761474 705000 753896
24417338 964000 1027149
40092698 1643000 1746106
38429965 1906000 2009129
41047273 917000 964169
8038695 865000 899600
438974 599000 621017
66637773 1058000 1096852
46661868 839000 864170
35156115 921000 945175
67149123 932000 954387
83909053 709000 723161
75037967 2102000 1998292
21651886 1221000 1150890
589074 787000 740850
88749684 1384000 1298648
36074258 965000 900719
38932633 1181000 1101612
9025398 920000 857090
82019835 1292000 1196417
44547453 717000 662528
89407218 911000 837326
86362121 907000 825939
27881111 1459000 1327812
5465293 833000 757880
2978807 521000 473443
2294544 1420000 1290364
72509414 703000 634721
97341015 1172000 1056557
98429211 1190000 1059479
4247737 1212000 1075400
90109125 607000 538067
86392091 1312000 1162287
1892093 844000 745027
39924996 1125000 990039
15304443 618000 538816
32569608 984000 852970
7594202 1235000 1067038
65121655 944000 811773
86392904 656000 563809
53107379 634000 543422
99678411 1130000 965406
56269838 882000 749645
10539895 609000 516970
10814702 874000 739602
43977877 939000 791973
39332988 1306000 1098907
55854343 1441000 1211942
1211898 802000 672971
8367742 547000 458703
9489916 1393000 1162468
8546441 833000 687956
695638 973000 802914
30691432 911000 750567
26822299 664000 546423
8116969 1506000 1238031
16445844 1124000 923287
14266985 720000 591010
36413351 773000 626823
21802367 756000 610769
6590690 713000 572494
33646975 994000 794896
55003742 962000 767853
67083899 930000 738426
52507895 701000 553096
3122775 754000 592354
4196630 945000 742400
72579890 1295000 1013207
32075174 860000 670612
81674600 645000 502599
64202569 690000 536199
50354621 828000 640129
73981185 1327000 1020412
81705032 791000 607593
83021866 849000 651855
31527587 957000 734481
67185891 734000 563223
37341934 869000 664451
29545437 637000 487022
8649340 1015000 771816
85762145 860000 652140
7562668 645000 487354
95122232 1262000 948501
84392284 1833000 1371356
39403088 663000 495641
59629472 755000 563755
77022459 505000 376959
38974449 860000 641394
15298300 1354000 1009495
96804517 1087000 805988
11758670 823000 610021
65251936 1462000 1075701
831418 768000 560753
96856944 826000 601308
17911856 655000 476158
71092111 525000 378303
98578078 1417000 1005277
85574649 892000 631038
58987216 772000 545134
43125444 883000 623335
47188534 634000 446167
13351596 1515000 1065340
72704115 1530000 1075758
13459599 871000 611295
3702930 1874000 1307158
23789141 723000 504223
81123744 1301000 906703
97818278 712000 495154
68407305 695000 483005
447701 661000 457308
41218650 799000 552569
9058944 984000 672425
41864583 573000 390787
5986241 589000 400251
93744881 734000 497441
70213207 966000 654515
47332461 530000 358262
51188445 740000 496677
58291059 850000 568279
63308353 650000 434416
46956656 583000 389421
54842774 2234000 1490857
51248581 1383000 919665
25014633 1116000 741907
72807000 2711000 1801793
36961552 819000 539308
51786784 543000 356483
70234182 1128000 739589
56012820 1189000 775742
3430857 836000 544850
454757 1740000 1133034
88402729 879000 571882
90313451 667000 430714
54001117 813000 521821
6136180 590000 376633
1217365 1709000 1090692
6282336 1513000 965438
47422777 747000 475830
28089289 724000 460862
56114900 533000 338617
21351251 952000 604395
15314245 689000 433747
49091401 908000 570904
70062091 846000 530446
14974562 989000 619882
58322400 549000 343820
23517675 1355000 845888
6362022 769000 479784
74188163 944000 583949
63512674 1147000 709451
59453437 1112000 685285
92747714 511000 313234
98394413 586000 358884
24056465 1082000 662454
7613690 880000 537218
93887391 870000 530701
78705715 598000 363130
69843896 1011000 608782
24579619 800000 480606
82186462 956000 573661
53758082 555000 332924
7810154 714000 427662
41808607 760000 453365
53686345 752000 448460
1120187 848000 505484
13194745 1123000 669147
95291602 823000 489540
37793067 839000 495290
35731105 937000 552962
78081713 778000 458889
71739298 689000 405741
67343858 1277000 751551
59563867 1623000 953171
24084076 1640000 963109
72453146 883000 518191
5724797 821000 480175
81757914 889000 518375
85214378 686000 399895
83134203 660000 383958
43106578 615000 357035
53438517 924000 536324
13315 730000 423200
9997573 756000 437346
29684344 732000 422813
43731966 757000 437175
60803332 643000 370188
61102018 1213000 694101
55686455 1075000 614403
3395262 926000 525509
99787002 619000 350889
22309046 1187000 670866
55992754 526000 297236
67924898 646000 364554
6728220 722000 406236
84974340 562000 315971
20618533 804000 451280
41246708 662000 371000
6151263 703000 393241
29688721 1133000 632848
52265688 1131000 627374
8156519 1042000 577560
7695334 704000 389226
44977980 918000 507158
38435034 1684000 930253
25076795 964000 530689
86873920 656000 360659
65906715 914000 501148
88524041 1656000 905897
6963643 617000 337004
49962982 508000 275792
834513 848000 459394
55495097 819000 443673
49457719 1327000 717246
44569651 901000 486782
36251468 1149000 620662
46999023 916000 494660
96116164 921000 495040
5042922 1094000 585143
12849416 976000 519200
68461975 793000 420940
57391771 528000 279456
69112169 1484000 783915
56601845 567000 298785
52015890 621000 323312
9618637 1489000 772988
68636365 1171000 606820
88698354 1215000 628408
31618150 1542000 791451
84649582 1067000 547623
33417830 1538000 788693
88168015 613000 312685
95024445 638000 324876
63869941 856000 435588
35721769 880000 447289
96289337 785000 398200
92374583 543000 275208
92497658 548000 277694
60924041 1718000 869192
67372150 683000 344656
9252689 776000 390105
10024488 891000 447545
64507 840000 420633
32527331 886000 442018
31855571 1466000 728014
67122647 611000 303072
26416303 813000 402920
24355515 1072000 530475
83842278 786000 388054
10172599 688000 339243
4706655 1226000 603292
56378839 1574000 771828
2893844 936000 458791
77376891 848000 414741
218341 668000 325829
53851009 760000 369851
92392865 668000 324825
28754114 1069000 509963
65271230 924000 437658
98461293 1650000 779763
12163683 606000 285988
15181980 660000 310763
4348749 571000 268644
87618466 603000 283062
52499861 1073000 500749
2922447 821000 380963
30975828 970000 447072
89707647 982000 450929
46174152 948000 435131
58036208 1393000 638316
47292604 602000 275700
93905744 690000 315640
61721951 1494000 681939
79994804 973000 443681
66906 532000 241878
95692060 982000 446283
24905037 686000 311393
48036161 1499000 680029
9600344 1005000 454423
87453056 630000 284460
84979080 1303000 587868
73448662 545000 244428
35213927 1525000 682686
58459442 915000 408073
4361983 547000 243744
88552738 743000 328861
66385059 903000 399374
34176710 527000 232565
84319905 914000 401682
10182570 1638000 718573
85264864 1495000 653217
37512282 889000 387643
6084239 1000000 432737
83738218 811000 350742
77393251 525000 226220
63167146 708000 303763
80763831 556000 238544
72108129 940000 402028
32085733 715000 305778
37278026 740000 316311
59286766 1636000 693934
8911704 629000 266398
96001370 1357000 572821
37776573 563000 237247
45586899 927000 389590
15016488 554000 232680
6167177 834000 350230
23472553 1230000 513010
94183949 967000 403161
87339767 819000 340660
46771809 992000 411495
9610958 959000 395853
54597529 714000 293756
52576572 883000 361613
79804656 1240000 507448
12508891 837000 340965
44418139 702000 284859
25039185 911000 369591
73719809 1083000 437989
49343920 625000 251037
63532749 1308000 525084
57504405 1245000 498123
15897113 708000 281992
31304439 581000 231133
76661756 1427000 565358
64316546 1847000 730299
39274078 1840000 721374
87057577 559000 218484
27275687 1181000 458692
8713249 526000 204121
74669705 944000 366026
10615457 1086000 420244
26354027 1517000 580443
95325547 1048000 400457
65471579 1358000 518494
83049383 902000 343784
72493750 820000 312328
8525165 1199000 455667
44048022 704000 267541
19732614 2217000 838158
54847284 864000 324351
52047549 928000 346514
32231339 923000 341903
21756406 1215000 448996
14107064 739000 271912
27415335 912000 332207
61367925 1636000 592303
56092791 626000 225179
4580371 653000 233606
78963081 660000 234439
29882016 1482000 525310
18654396 1515000 536673
39923055 633000 221744
51984753 682000 238668
42722339 1588000 551426
9017853 871000 301916
77424744 972000 336356
42714303 929000 320202
58464260 902000 308628
51165209 968000 330833
90072873 550000 185975
21667471 934000 312914
77436652 1822000 609337
35424620 757000 253001
61855483 637000 209807
98035656 610000 199713
60784674 582000 189577
4906230 1362000 440702
53332134 954000 306571
1566760 714000 228046
89591014 1174000 374798
17944150 894000 283538
81138037 1141000 360710
68364003 877000 276856
91304239 504000 157456
39428109 555000 172237
10908280 867000 268629
5062284 534000 165130
2434908 622000 191876
736087 1311000 399819
72374941 554000 168766
8156616 722000 218243
84736183 1597000 481777
42909660 945000 284977
55972846 648000 195286
6854773 839000 251111
64154812 1303000 389712
39442414 868000 259083
73087256 708000 207453
36765179 607000 177584
52522067 1050000 303536
2887815 834000 239374
243643 1559000 442041
57317544 1271000 360233
18945925 1172000 332141
7887925 678000 190047
95097498 754000 210283
62585072 1750000 487658
76249837 648000 178277
18693647 909000 249148
2439145 894000 244218
67069308 582000 158247
17898009 737000 199711
99694029 831000 223860
33337288 1324000 348252
18654249 1709000 447334
70947162 610000 159110
74946190 815000 211308
56103905 916000 236733
23416434 1105000 285432
91573436 684000 176029
5698223 530000 134947
57949795 729000 184763
5535683 889000 224878
3142033 991000 250395
12959322 1752000 439476
67439094 832000 207426
97616880 906000 223204
26854042 842000 206101
49466401 1526000 372328
88974533 627000 151989
81659714 571000 138395
82078443 817000 197890
73829420 1010000 243858
70536120 1073000 256551
71747917 922000 218241
35141811 1830000 430901
81522876 721000 168785
6398743 1442000 334959
27449924 766000 175068
4149057 714000 162637
8392213 981000 222678
42401977 1509000 340252
11552210 1826000 410623
57373053 965000 216973
66263502 1211000 269563
50003059 1131000 248332
59711484 784000 171575
89443138 1490000 325177
50976027 846000 183243
9584193 911000 196893
80411153 1783000 383846
21661445 1168000 248254
43234203 709000 149195
73423071 1959000 396798
8678647 550000 110302
9495113 1118000 223849
57214633 696000 139209
38905812 673000 134582
25221944 872000 168438
67664595 734000 139320
61188261 906000 169061
28183736 814000 147875
48663668 1448000 258630
1013724 976000 172099
89319876 928000 160853
43049890 1249000 216156
8785808 589000 101459
9911905 1338000 225017
77185217 995000 166855
67412099 1460000 243658
33905082 1199000 192986
6780279 1891000 300460
40267973 850000 132110
82312931 699000 107766
40702719 1204000 184768
25931647 1048000 148705
60051959 1338000 181791
7172634 919000 124315
62518384 1534000 207507
41486505 873000 113602
77994212 1509000 195834
2587718 1366000 176898
330187 1225000 157860
17285922 1239000 151443
12044231 1535000 187001
87158855 993000 120387
50782996 1448000 168535
68454337 987000 110519
87539735 1552000 170250
6915165 1026000 108176
18
856120297952 378000 170335
393432700404 301000 73480
470885573649 447000
832749318166 63000 87570
820174740587 316000 3595
391373129590 411000 213684
234381927747 25850
913720817851 288000
967421217659 1277000 875803
812489889441 484000 174343
751507723466 877000 233939
775473163615 450000 508500
553495221986 852000 144826
871278463941 219733
547226386936 1518000 949812
160534786607 721000 887252
419484433413 1032000 95954
744826522260 171615
SAMPLE OUTPUT
160534786607
419484433413
547226386936
553495221986
751507723466
775473163615
812489889441
967421217659
Time Limit: 10.0 sec(s) for each input file.
Memory Limit: 1024 MB
Source Limit: 1024 KB
Marking Scheme: Score is assigned if any testcase passes.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic