11026 - A Grouping Problem

[QulinXao]

(x-1)*(x-2)*(x-3) = x^3-6x^2+11x-6
a + b + c =6
ab+ac+bc= 11
abc=6
it got ac in 1.2 seconds during contest
Time complexity O(n^2)
Space Complexity O(n)

in contest my prog with same algo as yours writed in pascal get me
tle 2. sec
now I send it , and get acc with 0:02.830 sec (by the way i only one who
get acc used pascal all other use c/c++, who can get acc on JAVA and with what time?)
1.in how many times pascal slow c/c++ on same algo???
2. piple in top in http://acm.uva.es/cgi-bin/OnlineJudge?P ... :11026:100
1 0:00.365 412 30863 C++ 2006/04/02-13:11:26.707 4469427 (H0)
2 0:00.381 400 53387 C++ 2006/04/01-18:42:29.579 4467376 (H0)
3 0:00.430 4492 33201 C 2006/04/01-18:32:02.999 4467342 (H0)
4 0:00.439 420 26795 C 2006/04/02-07:59:27.140 4468861 (H0)
5 0:00.443 404 30631 C++ 2006/04/01-18:14:31.753
...
less 0.5 seconds
maybe they use some hint's? anybody know?can somebody exlpain why they sol so fast???

[little joey]

Yes, that is a problem. I made a literal translation of my C program to Pascal, and the execution was almost 7 times slower (C program 0.44 sec, Pascal program 2.79 sec).
I think most of the time spent by the Pascal program is range checking during array access.

This site doesn't like Pascal and Java programmers, that's why I switched to C some time ago. Looks like I'll need to switch to C++ shortly, because the problems increasingly rely on the presence of STL if you want to solve them in reasonable time. It's how things go....

[sclo]

There are some problems where STL is too slow for uva. I guess they should fix it.

[Darko]

I've been submitting my problems in Java (well, probably 95% of them) but I'm not giving up!

Why don't they use the lowest common denominator (be it Java or PASCAL) when they set the time limits? Disgusts me to see those "you should use scanf(), otherwise we couldn't set a reasonable time limit". WTH?

I mentioned this before somewhere else, the only problem I can see is that n^2 solution in C might be accepted instead of intended nlogn one or something like that - even I used it in couple of places (submitting C instead of Java).

While we are at it, when they change limits from 1-2 secs to 10 it is fine, but when they change them from 60 secs to 10 it is kind of painful (some Live Archive problems)

Darko

[C]

I got WA in 0.6s.
I think it is because that product of two very large integers is larger than MAXINT. And i tried use a double and then change to integer, it seems not enough precise.

Can anyone give any hints for that ? How i can save that big number correctly or avoid saving such big number?? Thanks in advance!

[Martin Macko]

I got WA in 0.6s.
I think it is because that product of two very large integers is larger than MAXINT. And i tried use a double and than change to integer, it seems not enough precise.

Try to use 64bit integers like long long int in C.

[C]

Try to use 64bit integers like long long int in C.

I have tried with long long int, but got still WA, and my code passes the input above, maybe I miss some tricky cases(if any?). Can someone give me the output for following input?

Code: Select all

2 2147483647
2147483646 2147483646
3 2147483647
2147483646 2147483646 2147483646
4 2147483647
2147483646 2147483646 2147483646 2147483646
5 2147483647
2147483646 2147483646 2147483646 2147483646 2147483646
6 2147483647
2147483646 2147483646 2147483646 2147483646 2147483646 2147483646
7 2147483647
2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646
8 2147483647
2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646
0 0

And my code outputs

Code: Select all

2147483645
2147483646
2147483643
2147483646
2147483641
2147483646
2147483639

Is that right ??
or I will be appreciate for any more i/os!

[ayon]

my AC program gives same outputs as yours, i did %m everytime

[C]

i did %m everytime

So did I!
To make sure that each element saved in my table is smaller than MAXINT and so that product of two 4B integers cannot exceed a 8B integer and this product %m is once again smaller MAXINT and so on.

my dp algo is following:

Code: Select all

f[n][k] is the fitness of k numbers from a[1..n]

k=0, f[i][0]= 1,i=1,..,n;
k=1, f[i][1]= sum(a[1],..,a[i])%m, i=1,..,n;
        and f[i][j]=0 if i<j
for all i>1
f[i][k]= (a[k]*f[i][k-1]+f[i-1][k])%m;
//either all k numbers from a[1..i-1] or k-1 number from a[1..i-1] and with kth number is a[i]
print max(f[n][i]), i=0,..,n

and i don't know if there was two common numbers in the array a, that means if for some i<>j , a=a[j], how will be the different group defined??
for example n=3, and say a1,b,a2,among which a1=a2=a, and for k=2, all the groups are ab and aa, or a1b,a2b,a1a2 ?? And I used of course the latter.

[Martin Macko]

and i don't know if there was two common numbers in the array a, that means if for some i<>j , a=a[j], how will be the different group defined??
for example n=3, and say a1,b,a2,among which a1=a2=a, and for k=2, all the groups are ab and aa, or a1b,a2b,a1a2 ?? And I used of course the latter.

I used the latter, too, and got accepted... thus probably the latter is the correct one, or the are no such inputs.

[C]

Thanks Martin Macko!

I used the latter too and got finally AC, I had made a careless mistake by reading input.

Thanks!

[Grazyna]

I can not understand something in this problem.

the problem states that
" You can take K different elements from them to make a group " and
"Two groups will be different if there is at least one element which is not common to both" ,
so, I assume that when I find for 2nd time some number I will throw it away, since I can not use it second time in the same group and from the other side it produces the same groups with its first apearence.

so, for example, how can I have result 17 with the input:
4 20
1 1 2 3

thanks in advance for any explanation.

[mak(cse_DU)]

Some case which I faced WA.
Input:

Code: Select all

42 18468
335 501 170 725 479 359 963 465 706 146 282 828 962 492 996 943 828 437 392 605 903 154 293 383 422 717 719 896 448 727 772 539 870 913 668 300 36 895 704 812 323 334 

757 20808
279 490 436 366 76 587 387 834 361 331 49 929 493 434 841 767 736 811 600 838 893 983 329 353 370 245 795 609 253 648 433 536 209 265 498 244 650 16 842 190 101 813 649 524 852 475 634 892 201 855 991 698 920 781 579 932 545 341 488 900 526 484 539 493 194 253 12 561 835 841 498 786 530 541 806 792 393 211 550 579 980 972 278 74 194 621 498 827 277 791 583 579 160 419 490 160 450 925 73 381 9 968 209 478 504 371 608 197 75 723 612 20 762 57 891 164 684 717 933 453 742 955 814 863 397 461 616 905 600 137 681 199 33 388 585 241 518 7 671 242 883 250 524 759 106 622 96 297 917 679 179 580 59 578 751 8 730 82 996 679 677 754 900 785 566 94 609 173 244 930 515 169 56 192 974 923 749 652 987 145 447 578 518 630 917 875 792 470 913 147 694 92 816 950 858 641 53 237 552 488 227 163 956 184 395 181 98 66 66 514 262 579 79 879 141 612 948 446 171 976 490 751 150 334 866 215 283 8 433 897 368 523 883 811 642 232 188 706 480 322 539 352 448 209 647 277 760 190 423 667 487 456 29 615 861 254 778 349 504 862 432 83 456 198 107 753 822 297 282 22 456 948 125 319 136 377 775 860 999 75 254 923 636 644 889 154 233 748 681 927 679 451 802 962 200 856 364 717 574 562 246 474 275 551 354 182 288 700 111 644 466 173 530 982 113 477 382 248 891 672 806 373 33 990 321 166 432 659 294 207 579 949 207 172 167 397 698 21 695 530 789 110 985 970 979 618 16 627 685 169 907 929 98 119 391 200 786 487 200 421 711 272 814 416 86 319 581 332 268 388 445 187 508 361 828 75 432 153 272 269 694 886 338 312 605 678 407 769 23 414 1 543 538 39 389 356 290 648 182 94 585 988 762 494 218 502 483 448 666 754 105 85 96 526 222 965 782 873 107 657 344 594 81 81 869 412 714 969 252 217 80 769 41 532 934 780 664 260 654 937 96 366 875 721 836 681 977 456 726 72 809 560 157 603 833 906 441 376 563 886 963 81 837 798 203 509 81 341 77 59 494 741 547 475 774 98 881 336 73 401 708 956 667 142 589 482 169 316 397 226 10 13 137 456 763 44 743 22 923 513 249 19 369 718 715 651 291 336 760 170 896 304 641 980 200 106 792 662 682 653 754 34 30 988 43 254 84 421 815 719 245 64 230 653 865 770 471 6 48 595 488 327 277 324 541 680 991 589 711 272 946 222 471 184 590 956 979 780 7 263 136 488 197 34 89 936 780 994 791 963 966 2 106 808 568 670 135 672 458 999 546 598 219 839 845 373 564 29 265 802 724 491 605 602 228 198 693 772 364 302 364 722 566 422 446 611 496 742 23 813 152 16 56 394 739 280 883 609 655 823 708 246 339 145 291 340 155 605 624 226 79 725 982 331 734 224 595 131 847 988 446 806 617 751 490 339 964 136 698 210 631 225 909 738 475 921 373 294 856 735 562 57 607 185 76 383 120 742 433 685 780 280 284 668 837 126 119 738 29 120 578 738 92 557 796 61 902 794 433 137 581 876 908 185 75 720 791 477 42 352 330 291 975 73 592 190 788 491 240 894 54 64 682 904 6 177 480 696 140 469 999 84 640 516 622 994 827 723 839 829 582 400 979 892 24 944 835 244 350 703 708 503 142 688 347 892 638 414 401 817 691 163 936 127 411 878 383 


859 20830
646 395 200 646 273 676 863 73 774 481 239 898 543 609 204 278 126 135 402 79 383 170 737 479 940 139 722 427 664 678 576 725 982 701 962 863 3 449 96 685 17 138 508 994 285 945 260 822 59 644 669 678 120 858 42 892 265 624 916 73 930 842 716 616 537 958 760 701 453 94 242 830 449 228 799 225 325 275 134 886 39 171 863 630 85 910 879 924 86 401 25 194 106 413 766 768 408 678 785 705 791 835 892 622 86 735 191 543 999 87 19 622 425 598 377 255 670 109 928 494 69 367 103 439 601 820 319 291 985 340 557 809 633 479 815 788 240 75 21 828 555 989 442 799 643 3 322 105 947 57 510 834 709 762 534 687 805 386 143 843 261 162 621 344 579 188 114 64 592 935 416 657 762 13 412 960 252 739 371 125 508 8 585 952 102 490 959 442 791 14 413 856 61 94 473 403 677 544 374 267 652 276 529 533 762 470 504 730 108 893 452 954 393 571 520 473 408 495 506 441 384 263 410 608 39 361 472 172 655 948 515 524 230 490 767 888 757 633 471 740 667 523 284 161 554 706 92 260 387 688 630 43 318 46 357 389 453 155 467 834 761 920 632 739 268 777 99 315 321 54 8 470 217 723 843 8 464 261 948 794 631 718 44 377 315 627 118 335 621 172 793 965 155 867 694 665 776 1 213 101 552 477 380 944 878 790 362 386 273 435 145 562 564 505 947 889 309 158 431 124 465 75 347 838 982 319 612 293 592 833 124 462 992 462 331 499 370 292 401 180 118 318 915 596 442 937 868 29 454 910 974 982 504 570 817 884 368 386 403 231 158 682 568 311 867 688 172 478 246 765 239 672 48 116 593 312 658 406 54 172 581 741 531 676 321 791 378 999 587 605 490 632 745 389 611 719 920 260 928 610 120 480 717 301 397 854 459 831 594 807 850 855 273 161 295 55 334 147 230 472 429 560 242 422 689 367 34 686 271 330 262 861 209 983 163 507 879 980 898 888 539 470 784 541 796 267 634 510 558 318 135 54 136 259 594 844 694 467 952 141 95 938 175 513 98 552 696 818 493 293 238 531 614 297 711 390 629 810 787 745 841 183 570 121 394 293 963 215 528 808 195 706 714 12 914 694 665 204 996 763 382 947 910 49 769 625 512 955 236 128 634 241 863 128 578 818 341 143 101 401 559 477 155 936 431 832 296 538 624 923 928 30 212 212 755 881 254 294 322 786 529 444 1 556 672 271 453 376 632 641 935 41 987 835 249 540 766 797 313 263 53 732 988 465 558 249 557 171 451 183 302 294 100 333 45 332 76 5 51 27 67 739 802 624 844 442 381 696 919 660 364 629 330 89 855 614 980 570 667 680 578 838 403 116 293 724 873 449 324 154 949 396 198 509 909 412 994 666 782 203 611 829 257 706 966 24 770 716 254 806 685 479 146 841 834 286 901 969 995 634 886 349 282 33 257 911 873 983 902 307 636 861 472 528 138 344 769 234 996 172 604 943 12 880 35 513 594 531 162 235 259 927 907 192 444 189 228 720 485 225 94 436 225 95 583 868 628 6 147 687 590 541 238 851 760 579 957 678 404 43 301 812 226 144 596 17 616 805 7 369 642 336 699 326 314 24 313 619 458 397 340 87 95 847 44 523 912 281 456 359 848 871 991 874 328 414 455 897 473 451 242 642 647 526 214 825 930 696 404 595 994 68 188 641 80 42 126 535 861 1 908 622 693 294 118 718 404 944 894 640 12 926 29 979 749 851 893 445 655 624 354 37 548 347 827 62 905 239 572 887 406 300 57 729 268 752 20 992 167 718 847 94 188 422 913 868 300 445 898 202 329 943 105 769 769 642 297 263 721 245 919 626 220 585 175 985 460 150 15 696 504 33 852 538 815 364 652 220 291 918 684 919 585 253 587 270 249 138 398 425 169 28 149 994 383 272 670 894 878 

AC Output:

Code: Select all

18176
20745
20732

[tobacco5648]

This is my code,firstly I used int,I got WA,then changed to long long and got AC
#include<iostream>
#define maxn 1001
using namespace std;
long long p[maxn][maxn];
int main()
{
long long n,m,num[maxn];
while(cin>>n>>m&&(n!=0||m!=0))
{
long long i,j,max=-1;
for(i=1;i<=n;i++)
{
cin>>num;
num%=m;
}
p[1][0]=1;
p[1][1]=num[1];
p[1][2]=0;
for(i=2;i<=n;i++)
{
p[0]=1;
for(j=1;j<=i;j++)
{
p[j]=(p[i-1][j-1]*num+p[i-1][j])%m;
}
p[j+1]=0;
}
for(i=1;i<=n;i++)
{
if(p[n]>max)
max=p[n];
}
cout<<max<<endl;
}
return 0;
}