10131

shaharpan · Post by **shaharpan** » Thu Oct 21, 2004 7:43 pm

Hey buddy

Can u please email me or post a commented version of ur program.

Thanz

zhenh · Post by **zhenh** » Fri Dec 10, 2004 4:46 pm

After reading the problem a few times, I thought :

Let W be the sequence of elephants sorted by weight in increasing order.
Let I be the sequence of elephants sorted by IQ in decreasing order.
The solution is the LCS of W and I.

If the above is correct, then the implementation would be straitforward.
Just read all elephants, sort, DP and then output.

Right?

But I have a question, how do I break ties while sorting elephants?
( i.e: equal weights/IQs )

jackpan · Post by **jackpan** » Mon Mar 14, 2005 4:39 pm

When the input is 1 1. What will happen to the output?
0
or
1
1

mf · Post by mf » Sun Mar 20, 2005 1:40 pm

The output should be

Code: Select all

1
1

The problem asks for the sequence with largest n, so n=1 is better than n=0.

tan_Yui · Post by **tan_Yui** » Sun Apr 03, 2005 12:22 am

I got WA several times.
My algorithm is almost same as 'Methods to solve'.

I want output for following set of input, or some other I/O.
Could anyone help me ?

Of cource, I know that there may be many correct outputs for a given input, our program only needs to find one.

Case 1 :

Code: Select all

Case 2 : (777 lines)

1262 6102
9834 8112
7751 5922
6504 4347
8573 5815
5537 1275
4221 1506
1432 9440
8174 4525
3256 7347
7450 5350
6818 7367
1024 4482
3320 6294
7063 3668
2904 274
4901 4446
6540 8763
2694 6197
4693 7222
6708 902
6202 3231
3155 6784
5813 5706
8530 8021
3805 1907
9376 2724
6137 1932
7432 6366
8562 5375
1075 2842
3148 9839
9020 358
632 5996
7196 4332
7058 8872
4744 4486
8121 56
83 8340
9675 507
2953 8264
7818 8663
3413 4304
7018 3523
3695 9949
9691 7398
3874 3038
5688 8024
7279 8994
5125 4711
6595 8565
2981 8219
6576 7266
8920 9069
4326 8708
759 3937
3072 9003
5029 4858
369 4423
3064 904
6677 9524
6050 7029
5253 7885
7486 9770
9276 2694
6472 4495
7169 9325
283 3875
2034 7132
9661 2281
6148 2614
5245 5779
6454 1171
8609 2425
1989 9603
6312 2533
9178 6573
421 3621
5942 3203
3939 9701
544 987
4562 9623
6132 9226
5221 4137
6888 9158
4842 6388
6746 6969
7750 5504
6602 2892
5166 7981
958 8551
7238 6550
9937 9767
9022 1215
7608 6995
8884 2134
2556 589
2723 9058
1636 3071
2489 6992
2844 5608
2401 2775
8257 873
1326 2269
2956 9476
4748 2832
895 2164
4756 786
3627 4961
1508 8538
2857 9456
4592 1067
2723 5404
7721 6449
2770 7848
5220 112
7547 5933
3712 7514
3755 5611
7468 4919
896 3421
838 2973
6358 3525
6217 2757
863 5201
973 9007
5231 2965
1774 192
4390 6524
9758 134
9561 2735
4984 859
4578 6770
3588 1363
7250 4658
6103 1987
1737 4411
357 9084
2843 7905
7410 9667
8193 718
3947 723
9210 2090
9578 2883
6843 2227
2474 3139
2974 9098
1788 6281
3455 1946
278 9769
3692 3675
5598 1693
2732 9318
3664 6534
6784 2764
2561 8410
8107 8931
399 6478
211 3587
5589 2206
5303 7980
2947 3174
4910 488
4076 3114
9636 2474
5468 2868
8967 513
2757 1945
7073 2204
4557 5380
5550 7746
4332 5564
9029 4449
3734 3750
4590 6399
5832 911
931 6435
1692 2640
8209 2645
8732 7781
4515 6554
4284 5480
9898 5206
2823 338
3887 4316
268 364
7450 4685
3827 7396
5322 9064
796 4704
9639 1655
4765 1438
823 7436
2662 8625
6647 3497
1074 6393
5423 9575
5288 7114
4247 9980
9473 4155
8241 4088
1469 918
1730 7602
582 9862
7287 1759
1866 6194
3588 2674
5288 5914
8015 8010
3246 2904
4939 3157
4861 4748
5629 4112
478 1969
712 9245
4826 367
1139 7143
2269 1161
8573 2706
2574 8603
1161 8704
661 9759
5604 4962
8734 6150
1478 2374
4273 1938
8737 3929
2287 8333
4340 9928
5292 8927
8930 9603
9435 5630
9520 6292
214 9899
9098 8393
6218 8949
9119 3255
4338 1628
5792 6210
4878 3651
6122 1932
8 6878
4630 302
3985 2320
6699 3975
8605 1561
9475 9837
2292 6290
6264 1531
6288 626
5365 5246
6362 5918
9275 5956
3489 2716
5196 6300
1930 9604
2795 5275
8152 3562
145 8953
9024 1570
3789 390
2728 8129
3857 924
826 8380
186 47
4913 1522
369 6036
6297 4212
5679 4541
2146 8627
5794 7299
6538 4886
8280 8181
9847 2513
3746 8747
4911 632
2628 499
3411 1579
4525 6024
904 7620
6040 6210
3947 5457
8043 5722
7748 8225
8317 3927
7777 9650
504 3462
3787 60
5300 3617
9670 8945
4836 736
7592 3742
6173 2815
9841 9546
4867 487
6829 9417
4517 1583
4687 9986
3258 1449
879 2037
3117 6223
1287 765
3182 1233
7200 5379
2516 1737
5636 2757
3753 8160
1448 4822
3318 3039
4642 4350
9204 1849
1345 8867
2245 4911
1867 7352
1821 2552
4291 9414
1940 722
7020 1636
8619 9242
8738 782
4523 9883
9198 8536
1774 6447
9300 7484
8894 4058
3877 3001
2799 9834
5629 753
1790 2130
3658 4489
479 551
5022 3811
2587 3906
2757 6617
2547 8307
8798 5894
1857 2582
5245 5559
1114 3210
2406 5026
3671 5950
7045 7196
1850 6355
9299 9545
1655 6363
1670 3013
6914 9155
8550 8370
8795 9446
9715 4747
1631 1433
6216 29
989 1551
2106 7786
4924 8253
458 434
4354 5976
7083 3319
3494 5509
409 9400
6282 7920
947 9231
9747 4259
8786 5920
240 8197
2551 9755
3478 3812
8265 2190
4330 5695
1546 3869
7295 3565
1591 6382
3589 8588
365 2442
5804 3584
5450 4164
6049 4299
9975 4137
8537 3948
8083 8979
2535 8205
9358 58
6629 2826
655 1066
227 1104
8767 7144
3252 3323
2374 5229
9957 5424
6705 324
7792 9054
9352 7370
7271 183
674 3412
3778 8491
7228 9752
7230 4700
1667 8756
565 8043
7535 5031
2963 1057
2410 5636
8760 3892
7814 9025
7976 5310
9350 7412
9405 2581
5481 2237
2203 7447
8404 7425
6904 349
5449 130
1813 103
4446 3642
5703 1217
1490 2152
2763 6021
4551 2058
722 3824
1355 9505
8104 4257
4988 8840
1532 7013
5642 1673
9035 5149
1960 1231
286 4166
408 1693
9708 4021
6100 7193
3398 6291
3542 178
5784 3649
706 3809
6976 3859
4881 8093
6733 5469
3744 4430
5994 7387
76 8274
1895 9538
3578 4574
7231 6776
8206 5708
280 3248
8472 6575
5943 9397
3153 6549
4125 8783
9829 2977
6298 6925
8712 5899
6196 9332
9179 8692
5554 928
7462 4322
850 4049
8928 1886
1985 7200
3383 3129
8827 1766
6845 3640
6568 8850
8219 8392
5819 3451
4308 6337
8405 8135
1604 3721
4763 3421
8294 821
3910 7046
4918 1788
1902 9303
7119 2285
9732 6647
8913 4600
6589 744
9936 4929
9439 5158
5078 2521
4840 6870
9972 5352
3947 4793
752 2047
6639 2502
1524 4703
5698 7342
7997 2329
6993 3112
697 9578
6591 8513
6212 448
740 8539
9900 1671
9663 1013
8501 5436
1096 5443
6086 6171
4514 6387
1789 1048
1968 8523
2745 8908
6493 5601
691 7291
4002 473
5647 2257
9622 8381
5130 693
4393 696
2331 9780
3281 1296
1698 3327
435 2762
5352 9631
2632 4596
8784 586
6832 624
9269 6697
2804 7798
5430 7706
6743 3570
1389 3505
6819 4021
3954 5037
6598 9946
6260 9861
7273 3073
6319 2070
4643 9606
3911 1258
1766 3284
4245 209
3250 5129
1845 6017
2082 2095
3079 4294
4971 1778
784 1189
7116 5394
9413 2873
2343 6210
4155 7203
9558 5601
2449 7230
1439 3941
1340 1263
6319 8503
9117 9154
9178 5553
4660 9500
2712 8840
2944 7463
4377 1654
126 7866
383 4644
6668 3281
2554 6594
1922 1784
8989 322
8609 4058
4485 921
654 4548
1628 8492
2782 6342
8512 2595
5339 4470
4018 570
2765 7309
6588 6947
9150 779
7429 6106
9322 5028
4092 5392
8903 8270
5360 868
1761 7492
3378 2887
8306 698
3971 3681
3059 386
1081 4144
4944 2935
6261 2010
8723 3613
9171 8593
1027 1861
9999 6299
9412 6568
9759 4086
7880 6013
9401 3055
7303 2159
3653 9368
4186 3990
563 6681
6206 9583
2656 5276
7974 1593
641 71
5433 5847
5629 4713
2367 7728
776 3933
7416 6044
8293 1347
5072 9056
2778 4889
9071 2374
6780 7079
1621 3385
9555 2298
6919 1919
4942 8254
2365 1827
9292 3851
5951 3168
5404 618
3215 9689
3380 9904
2245 1284
4368 3030
133 6124
8097 6562
9336 2137
171 9926
7378 2534
37 7519
8328 5068
5584 2529
9494 9709
5290 4639
1767 4420
3873 8805
7056 3735
2371 7295
1252 9807
8598 2180
6157 635
8901 457
8810 5138
7172 9000
1658 9773
2035 1522
2005 6391
8163 4737
4171 5999
2645 5907
2811 8138
2352 8959
810 549
3243 1377
225 8817
7532 9029
9675 691
9669 1139
6640 4752
7067 2578
8101 8128
6514 5672
7956 2935
2199 8707
4647 6143
6305 3317
7449 2541
8095 7953
4837 5498
2429 9608
3390 5205
3658 997
655 9082
5818 5365
413 4045
5080 6128
3786 5311
5376 3522
4626 1438
3148 5450
2608 276
2158 4719
2486 5537
4293 9847
2934 8640
7301 1636
3411 5552
5402 2690
2503 3287
3705 2077
6150 5768
2370 2303
9227 3723
1460 810
8898 8321
2403 3167
3179 3219
7026 149
3164 4721
74 5888
2333 4717
6166 9292
1389 6124
7127 5904
2062 5471
621 2406
8313 2359
6034 945
8378 449
8542 5465
6091 9696
7297 7247
4921 4483
8672 1832
3161 7375
504 4513
3706 3162
8270 6598
6862 2876
9133 9619
9613 2487
4796 9670
9799 5944
9107 9082
8627 7266
1338 7600
9963 1361
1099 265
9835 8262
5793 4178
4595 470
6587 1341
1163 8092
3796 9763
7806 1451
7657 5
8874 5876
5398 9373
1944 8339
560 930
803 636
5499 9519
2708 8802
3014 1984
3357 3442
8027 3787
8019 665
5263 9186
2250 8314
3864 7183
636 7177
4875 420
7001 1866
2532 9210
4520 1044
5304 7894
9171 1708
7615 5710
4959 7193
8188 9355
4362 3595
5946 9446
2426 4303
9411 8043
7950 7321
534 9441
201 5073
8900 1407
4587 1371
7240 9060
5739 5248
4185 8566
1434 6320
5212 2851
5786 1394
7702 6516
5161 6979
1063 2129
5244 7417
7847 5098

Thank you.

jagadish · Post by **jagadish** » Thu Apr 07, 2005 7:45 pm

Code: Select all

tan_Yui · Post by **tan_Yui** » Fri Apr 08, 2005 4:17 pm

Thanks for your reply, jagadish

My code outputs wrong answer in case 2.
I'll try to debug.

Best regards.

Nemo · Post by **Nemo** » Fri Apr 15, 2005 7:08 pm

i have the same algo.

sort w increasing
sort i decreasing
find lcs of these two

but i get wa! is this algo wrong?

Kentaro · Post by **Kentaro** » Sat Apr 16, 2005 4:56 am

You need to be careful of elephants with the same weight, same IQ, or same weight and same IQ. The sequence you produce has to have strictly increasing weights and strictly decreasing IQ's. For example, the following are invalid sequences of elephants for (weight, IQ) pairs.

(1000, 4000)
(2100, 3000)
(2100, 1900)
(4000, 800)

(1000, 4000)
(2100, 3000)
(2000, 3000)
(4000, 800)

Note that in the first example, the weights are not strictly increasing since two elephants in the sequence have weight 2100. In the second example, two elephants in the sequence have an IQ of 3000.

(No, elephants aren't that smart, the IQ's are apparently given in hundredths of an IQ point.)

Ali Arman Tamal · Post by **Ali Arman Tamal** » Mon Aug 08, 2005 7:12 am

Hello

,

I am getting WA in 10131 all along. Here's my algo:

1. I sort the elephants by their IQ in decreasing order
2. Then I find the LIS of the weights of the sorted elepahnts and
that is my answer.

Is it correct

?

Please help

mohiul alam prince · Post by **mohiul alam prince** » Mon Aug 08, 2005 8:25 am

Hi Tamal
I have also solved this problem by this way. You can show your code
in the board or sent me your code. I will help you.

Thanks
MAP

Ali Arman Tamal · Post by **Ali Arman Tamal** » Tue Aug 09, 2005 3:25 pm

Here is my code :

// Got AC - deleted

Help if u can. Thanks

mohiul alam prince · Post by **mohiul alam prince** » Sat Aug 13, 2005 2:21 pm

Hi

I have send you my code you can check it.

Thanks
MAP

mohiul alam prince · Post by **mohiul alam prince** » Sat Aug 13, 2005 2:32 pm

Hi Tomal

i have found your mistake.

This is the your modified code. I have
just changed your sort process.

Code: Select all

deleted.....

Thanks
MAP

Ali Arman Tamal · Post by **Ali Arman Tamal** » Thu Aug 18, 2005 12:31 pm

Thanks Prince

, I really appreciate your help .

now I understand where my mistake is - while sorting we have to swap
element even if they have same value.

Like :

int compare(const struct data *a,const struct data *b)
{
if(a->IQ - b->IQ > 0)return -1;
else return 1;
}

OJ Board

10131 - Is Bigger Smarter?

Please Post a Commented Version of ur Program

Is this Longest Common Subsequence(LCS) ?

10131 - WA

10131 [ is bigger smarter ] WA - confirm my algo