10930 - A-Sequence

TISARKER · Post by **TISARKER** » Sun Oct 09, 2005 12:16 pm

Thanks Jan Thanks little joey

bijon · Post by **bijon** » Sun Oct 09, 2005 7:44 pm

i followed the same procedure of guest #2 but getting worng answer.
can you please give some input output of the problem?

Thanks.

erictwpt · Post by **erictwpt** » Mon Oct 10, 2005 5:15 am

sorry for posting my code.

all the tests on the board is ok,but i got WA...

thanks for any help!

Code: Select all

AC, thanks!

SRX · Post by **SRX** » Mon Oct 10, 2005 7:31 am

your algorithm is right
but your code is wrong

for(i=0;i<=30000 && flag;i++) should be
for(i=30000;i+1 && flag;i-- ) or use additional array
the reason is
if now data is 4 and u[2] is true
then u[6] is true
but then i = 6 , your code will make u[10] is true
it means 4+4+2
sorry for my poor english
hope it helps

asif_rahman0 · Post by **asif_rahman0** » Thu Oct 13, 2005 11:51 pm

i always got WA...but didnt find anything.
Plz give me some input output.
it would be helpfull.

Timo · Post by **Timo** » Fri Oct 14, 2005 4:03 am

Try This Input :

3 4 336 34
12 218 537 196 701 950 275 445 109 699 565 42 166
25 686 765 828 960 220 427 953 840 924 811 452 605 662 600 550 721 114 407 122 672 475 492 565 345 869
10 180 424 695 164 539 646 624 4 788 269
15 387 377 582 604 280 171 806 295 334 409 241 414 55 495 984
3 410 70 74
9 975 356 405 198 198 212 250 759 890
27 736 462 532 36 131 459 484 597 254 115 702 650 887 876 43 554 511 621 772 254 218 236 336 567 133 615 32
28 213 809 630 716 733 552 572 168 333 870 825 615 954 992 983 738 510 296 719 286 640 493 176 560 384 775 389 651
6 145 337 919 655 649 710
20 662 721 998 422 563 377 984 15 943 453 238 547 495 627 708 584 790 433 4 836
22 987 458 353 940 645 565 699 224 310 899 73 958 613 82 848 728 675 926 494 286 681 310
12 756 978 921 245 411 914 420 339 886 146 146 323
7 625 950 270 101 980 246 217
5 528 878 906 266 615
27 656 84 517 823 848 739 615 548 975 983 65 367 730 98 682 339 116 380 253 505 21 997 2 83 248 543 423
8 460 147 205 416 9 465 456 182
6 421 959 60 384 20 670
18 78 86 179 204 196 267 353 27 746 155 875 21 228 858 911 725 782 871
19 299 971 590 650 574 662 311 588 210 991 65 171 538 857 117 381 189 932 490
13 92 647 350 256 953 129 590 262 790 550 471 145 631
26 651 907 965 384 449 236 31 218 693 665 557 947 989 185 23 598 758 546 59 330 886 957 54 828 328 400
18 847 510 292 782 911 872 692 104 595 406 794 839 396 511 905 695 636 30
20 717 376 809 569 66 810 601 946 781 106 696 908 92 163 81 681 404 252 508 127
17 10 284 308 230 760 154 303 804 616 101 973 562 354 413 922 35 505
26 349 869 654 346 24 31 395 812 102 428 927 844 987 530 754 716 982 83 453 294 923 516 987 594 535 131
17 372 710 667 242 570 445 337 67 962 642 930 844 859 499 68 882 197
22 220 355 868 173 555 524 628 489 242 255 429 854 279 790 519 696 446 253 153 673 486 846
10 312 94 220 910 973 820 971 916 375 466
23 435 399 87 927 889 378 178 330 62 611 141 955 718 296 636 176 574 626 895 400 987 242 608

Timo · Post by **Timo** » Fri Oct 14, 2005 4:07 am

Here is the output from my accepted code

Case #1: 4 336 34
This is an A-sequence.
Case #2: 218 537 196 701 950 275 445 109 699 565 42 166
This is not an A-sequence.
Case #3: 686 765 828 960 220 427 953 840 924 811 452 605 662 600 550 721 114 407 122 672 475 492 565 345 869
This is not an A-sequence.
Case #4: 180 424 695 164 539 646 624 4 788 269
This is not an A-sequence.
Case #5: 387 377 582 604 280 171 806 295 334 409 241 414 55 495 984
This is not an A-sequence.
Case #6: 410 70 74
This is an A-sequence.
Case #7: 975 356 405 198 198 212 250 759 890
This is not an A-sequence.
Case #8: 736 462 532 36 131 459 484 597 254 115 702 650 887 876 43 554 511 621 772 254 218 236 336 567 133 615 32
This is not an A-sequence.
Case #9: 213 809 630 716 733 552 572 168 333 870 825 615 954 992 983 738 510 296 719 286 640 493 176 560 384 775 389 651
This is not an A-sequence.
Case #10: 145 337 919 655 649 710
This is an A-sequence.
Case #11: 662 721 998 422 563 377 984 15 943 453 238 547 495 627 708 584 790 433 4 836
This is not an A-sequence.
Case #12: 987 458 353 940 645 565 699 224 310 899 73 958 613 82 848 728 675 926 494 286 681 310
This is not an A-sequence.
Case #13: 756 978 921 245 411 914 420 339 886 146 146 323
This is not an A-sequence.
Case #14: 625 950 270 101 980 246 217
This is an A-sequence.
Case #15: 528 878 906 266 615
This is an A-sequence.
Case #16: 656 84 517 823 848 739 615 548 975 983 65 367 730 98 682 339 116 380 253 505 21 997 2 83 248 543 423
This is not an A-sequence.
Case #17: 460 147 205 416 9 465 456 182
This is not an A-sequence.
Case #18: 421 959 60 384 20 670
This is an A-sequence.
Case #19: 78 86 179 204 196 267 353 27 746 155 875 21 228 858 911 725 782 871
This is not an A-sequence.
Case #20: 299 971 590 650 574 662 311 588 210 991 65 171 538 857 117 381 189 932 490
This is not an A-sequence.
Case #21: 92 647 350 256 953 129 590 262 790 550 471 145 631
This is not an A-sequence.
Case #22: 651 907 965 384 449 236 31 218 693 665 557 947 989 185 23 598 758 546 59 330 886 957 54 828 328 400
This is not an A-sequence.
Case #23: 847 510 292 782 911 872 692 104 595 406 794 839 396 511 905 695 636 30
This is not an A-sequence.
Case #24: 717 376 809 569 66 810 601 946 781 106 696 908 92 163 81 681 404 252 508 127
This is not an A-sequence.
Case #25: 10 284 308 230 760 154 303 804 616 101 973 562 354 413 922 35 505
This is not an A-sequence.
Case #26: 349 869 654 346 24 31 395 812 102 428 927 844 987 530 754 716 982 83 453 294 923 516 987 594 535 131
This is not an A-sequence.
Case #27: 372 710 667 242 570 445 337 67 962 642 930 844 859 499 68 882 197
This is not an A-sequence.
Case #28: 220 355 868 173 555 524 628 489 242 255 429 854 279 790 519 696 446 253 153 673 486 846
This is not an A-sequence.
Case #29: 312 94 220 910 973 820 971 916 375 466
This is an A-sequence.
Case #30: 435 399 87 927 889 378 178 330 62 611 141 955 718 296 636 176 574 626 895 400 987 242 608
This is not an A-sequence.

Timo · Post by **Timo** » Sat Oct 15, 2005 7:48 am

The problem says that A-sequence is a sequence of positive integers ai satisfying 1 ≤ a1 < a2 < a3 < ... and every ak of the sequence is not the sum of two or more distinct earlier terms of the sequence.

So if the sequence have two or more equal value, the sequence is not A-sequence.

Case #7: 975 356 405 198 198 212 250 759 890
This is not an A-sequence.

In above case you can see that the value 198 is appear twice.

Timo · Post by **Timo** » Sat Oct 15, 2005 9:17 am

Hi HASAN_AI

4 336 34 -> this sequence is an A-sequence because we can arrange
this sequence become 4 34 336 that satisfying 1 ≤ a1 < a2 < a3
and every ak of the sequence is not the sum of two or more distinct earlier terms of the sequence.

So if the input :

2 2 1

You should output :

Case #1: 2 1
This is an A-sequence.

Fixxxer · Post by **Fixxxer** » Sat Oct 15, 2005 11:03 pm

My AC code says "2 2 1" is not an A sequence

cypressx · Post by **cypressx** » Mon Oct 17, 2005 12:50 am

To see if some numbers make some SUM , use DP !

It is a standart algorithm - making of sum from some coins. Ask if you have any further questions:)

Timo · Post by **Timo** » Mon Oct 17, 2005 2:52 am

Hi RONI_DU,

15 387 377 582 604 280 171 806 295 334 409 241 414 55 495 984
This is not an A-sequence.

because the problem says that A-sequence is a sequence of positive integers ai satisfying 1 ≤ a1 < a2 < a3 < ... and every ak of the sequence is not the sum of two or more distinct earlier terms of the sequence.

241 + 334 + 409 = 984

Timo · Post by **Timo** » Mon Oct 17, 2005 2:59 am

Hi Fixxxer,

because both you and me can get AC with different output for the input :

2 2 1

so we can assume that there is no input like that (the input is invalid).

Dominik Michniewski · Post by **Dominik Michniewski** » Mon Oct 17, 2005 8:19 am

Yesterday I got Accepted on this problem without sorting input sequence, so I can assume, that sorting isn't necessary. It implies, that every sequence in which order of elements after sorting is different from original order isn't A-Sequence.

Best regards
DM

Towhid · Post by **Towhid** » Mon Oct 17, 2005 9:54 am

I don't think so. If sorting is allowed then 8, 4, 1, 2 is A- sequence as if sort it it becomes 1, 2, 4, 8 which meet all criteria.

But I think In case of sequence the given order matters. So you can't sort the given data. What do you think???