10049 - Self-describing Sequence

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

Moderator: Board moderators

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

10049 - Self-describing Sequence

Post by pc5971 » Mon Jul 07, 2003 7:56 am

Who can give me some ideas to solve this problem... I foud some information about this sequance of numbers that are called "Golomb's sequence". I know that the formulas for this sequance:

"a(n) is nearest integer to (and asymptotic to)
tau^(2-tau)*n^(tau-1), where tau is the golden number
(1+sqrt(5))/2.

see http://www.research.att.com/~njas/sequences/

but this formulas doesn't go....

Here I found an recursive formulas:

a(1) = 1; a(n+1) = 1 + a(n+1-a(a(n)))

but this formula is too slow...


I tried also to memorise the values f(1) to f(15000) and for n>15000 I calculated the value without storing them... But I got WA...

Pls. help me...

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Re: 10049 algo

Post by Observer » Mon Jul 07, 2003 8:39 am

Hint:

When n = 2000000000, Output should be 673365.

So, you should use the correct formula to generate the first 700000 value of f(n) and store then in an array for future use. Then you won't get TLE.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

700000?

Post by rbuchan » Tue Oct 28, 2003 6:55 pm

Yes, but if using the correct formula, wouldn't you need to generate 2 billion elements in the array? I don't see how only the first 700,000 will help.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Tue Oct 28, 2003 11:51 pm

i didn't use formula but just a double for loop to generate the points where the sequence changes (so I store the values 1,2,4,6,9,12,16,20,24, ....). My program runs in 0.1 seconds using 3MB of memory. I think I can improve the running time a bit, but don't know about the memory. I was wondering how people can solving this problem in 0.000 seconds using only 64k of memory.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Wed Oct 29, 2003 12:07 am

I got my runtime down to 0.021 seconds and all the sudden the judge says i'm only using 64k of memory... but i'm still using 700000 int array... anyone knows how this is possible ? After all, 700000 * 4 = 2.8 million bytes isn't it ?

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

Accepted

Post by rbuchan » Wed Oct 29, 2003 8:34 am

I used a 700K array of ints and it ran in 0.217 s. So, I am happy. I like the other way with the double for loops. Not sure how you are only using 64K, though.

How to do it in time 0.000 s, don't know...seems impossible, unless there is a very quick formula. But using phi/tau, I couldn't get the precision I needed.

Niaz Morshed
New poster
Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.
Contact:

10049

Post by Niaz Morshed » Sun Nov 16, 2003 7:18 am

I am really confused with this problem. I have read the previous posts at the board but i could not find the besic thing i,e the formula :-) . Is there any one can tell me about the formula and the way to solve it (if can). Thanks in advance. :(
The Last Man Standing :-)

User avatar
deneb
New poster
Posts: 6
Joined: Mon Nov 17, 2003 3:39 pm

Post by deneb » Mon Nov 17, 2003 3:49 pm

Hi!
I use this formula to create the sequence:
a(1) = 1
a(n) = 1 + a(n - a(a(n-1)))

In other posts i've read sth i don't understand. How do you know a(2

Niaz Morshed
New poster
Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.
Contact:

Thanks friend.

Post by Niaz Morshed » Wed Nov 19, 2003 12:01 pm

Thanks friend for giving me the formula. I haven't yet tried. If i get accepted, i will informe you.

Niaz :lol:
The Last Man Standing :-)

User avatar
deneb
New poster
Posts: 6
Joined: Mon Nov 17, 2003 3:39 pm

Post by deneb » Wed Nov 19, 2003 5:30 pm

OK
but if you get an "acecpted" please post me a message here or mail to franpas@eudoramail.com

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

10049

Post by L I M O N » Mon Jul 19, 2004 10:34 am

Pls someone gime me the correct answer of the following inputs. I got several times wrong answer of this problem.
  • 500
    42
    18468
    6335
    26501
    19170
    15725
    11479
    29359
    26963
    24465
    5706
    28146
    23282
    16828
    9962
    492
    2996
    11943
    4828
    5437
    32392
    14605
    3903
    154
    293
    12383
    17422
    18717
    19719
    19896
    5448
    21727
    14772
    11539
    1870
    19913
    25668
    26300
    17036
    9895
    28704
    23812
    31323
    30334
    17674
    4665
    15142
    7712
    28254
    6869
    25548
    27645
    32663
    32758
    20038
    12860
    8724
    9742
    27530
    779
    12317
    3036
    22191
    1843
    289
    30107
    9041
    8943
    19265
    22649
    27447
    23806
    15891
    6730
    24371
    15351
    15007
    31102
    24394
    3549
    19630
    12624
    24085
    19955
    18757
    11841
    4967
    7377
    13932
    26309
    16945
    32440
    24627
    11324
    5538
    21539
    16119
    2083
    22930
    16542
    4834
    31116
    4640
    29659
    22705
    9931
    13978
    2307
    31674
    22387
    5022
    28746
    26925
    19073
    6271
    5830
    26778
    15574
    5098
    16513
    23987
    13291
    9162
    18637
    22356
    24768
    23656
    15575
    4032
    12053
    27351
    1151
    16942
    21725
    13967
    3431
    31108
    30192
    18008
    11338
    15458
    12288
    27754
    10384
    14946
    8910
    32210
    9759
    24222
    18589
    6423
    24947
    27507
    13031
    16414
    29169
    901
    32592
    18763
    1656
    17411
    6360
    27625
    20538
    21549
    6484
    27596
    4042
    3603
    24351
    10292
    30837
    9375
    11021
    4597
    24022
    27349
    23200
    19669
    24485
    8282
    4735
    54
    2000
    26419
    27939
    6901
    3789
    18128
    468
    3729
    14894
    24649
    22484
    17808
    2422
    14311
    6618
    22814
    9515
    14310
    7617
    18936
    17452
    20601
    5250
    16520
    31557
    22799
    30304
    6225
    11009
    5845
    32610
    14990
    32703
    3196
    20486
    3094
    14344
    30524
    1588
    29315
    9504
    7449
    25201
    13459
    6619
    20581
    19797
    14799
    15282
    19590
    20799
    28010
    27158
    20473
    23623
    18539
    12293
    6039
    24180
    18191
    29658
    7959
    6192
    19816
    22889
    19157
    11512
    16203
    2635
    24273
    20056
    20329
    22647
    26363
    4887
    18876
    28434
    29870
    20143
    23845
    1417
    21882
    31999
    10323
    18652
    10022
    5700
    3558
    28477
    27893
    24390
    5076
    10713
    2601
    2511
    21004
    26870
    17862
    14689
    13402
    9790
    15256
    16424
    5003
    10586
    24183
    10286
    27089
    31427
    28618
    23758
    9833
    30933
    4170
    2155
    25722
    17190
    19977
    31330
    2369
    28693
    21426
    10556
    3435
    16550
    7442
    9513
    30146
    18061
    21719
    3754
    16140
    12424
    16280
    25997
    16688
    12530
    22550
    17438
    19867
    12950
    194
    23196
    3298
    20417
    28287
    16106
    24489
    16283
    12456
    25735
    18115
    11702
    31317
    20672
    5787
    12264
    4314
    24356
    31186
    20054
    913
    10809
    1833
    20946
    4314
    27757
    28322
    19559
    23647
    27983
    482
    4145
    23197
    20223
    7130
    2162
    5536
    20451
    11174
    10467
    12045
    21660
    26293
    26440
    17254
    20025
    26155
    29511
    4746
    20650
    13187
    8314
    4475
    28023
    2169
    14019
    18788
    9906
    17959
    7392
    10203
    3626
    26478
    4415
    9315
    25825
    29335
    25875
    24373
    20160
    11834
    28071
    7488
    28298
    7519
    8178
    17774
    32271
    1764
    2669
    17193
    13986
    3103
    8481
    29214
    7628
    4803
    4100
    30528
    2626
    1544
    1925
    11024
    29973
    13062
    14182
    31004
    27433
    17506
    27594
    22726
    13032
    8493
    143
    17223
    31287
    13065
    7901
    19188
    8361
    22414
    30975
    14271
    29171
    236
    30834
    19712
    25761
    18897
    4668
    7286
    12551
    141
    13695
    2696
    21625
    28020
    2126
    26577
    21695
    22659
    26303
    17372
    22467
    4679
    22594
    23852
    25485
    1019
    28465
    21120
    23153
    2801
    18088
    31061
    1927
    9011
    4758
    32171
    20316
    9577
    30228
    12044
    22759
    7165
    5110
    7883
    17087
    29566
    3488
    29578
    14475
    2626
    25628
    5630
    31929
    25424
    28521
    6903
    14963
    124
    24597
    3738
    13262
    10196
    32526
    0
    Thanks in advance.
    L I M O N

User avatar
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

Post by szymcio2001 » Fri Sep 24, 2004 6:05 pm

If you have already solved this problem, maybe it will help somebody else. My accepted solution gives:

Code: Select all

56
12
521
269
651
533
471
388
693
658
619
252
675
601
492
356
55
169
398
227
245
737
450
199
27
40
407
502
525
542
545
245
576
454
389
126
545
638
648
495
354
684
609
722
707
507
223
461
304
677
283
636
668
740
742
548
416
328
351
666
74
405
171
583
125
40
704
335
333
534
591
665
609
474
279
618
464
458
718
618
188
541
412
613
546
526
396
231
295
437
648
494
737
622
385
247
573
479
135
595
486
227
719
222
698
591
355
438
144
727
586
233
684
657
531
267
255
655
469
235
486
612
425
338
524
586
624
607
469
203
400
664
94
494
576
438
184
718
705
513
385
466
405
670
365
457
332
734
351
616
523
271
627
666
420
484
691
81
739
526
117
502
269
668
556
573
273
667
204
190
618
363
715
343
378
221
612
664
599
541
620
317
225
14
132
650
672
283
196
515
54
194
456
622
588
509
148
445
276
593
346
445
301
529
503
557
239
486
725
593
707
266
378
256
740
458
741
176
555
173
445
710
114
693
345
297
631
428
276
557
543
454
463
540
560
673
661
555
606
522
405
261
615
516
698
310
265
544
594
533
389
480
156
616
548
552
591
649
229
528
680
701
549
610
107
578
731
363
524
357
252
188
680
672
618
234
372
155
152
564
656
510
452
427
352
463
484
232
369
615
363
660
723
682
608
353
716
208
138
639
498
547
722
146
684
571
369
184
487
297
346
705
514
575
195
479
408
482
643
489
410
589
503
545
418
31
599
180
554
678
478
620
482
408
639
514
393
721
558
254
404
212
618
720
548
81
374
125
563
212
670
678
539
607
673
55
207
599
551
289
138
247
554
382
367
400
575
648
650
499
547
646
695
225
558
423
318
217
674
139
439
526
354
512
296
361
190
650
215
341
640
693
641
618
550
396
674
298
678
299
315
508
735
122
158
498
439
173
322
691
302
227
205
710
156
112
129
379
702
420
442
717
665
504
667
592
420
322
26
499
721
420
308
533
319
587
717
444
691
35
715
542
639
528
223
293
410
26
433
159
574
674
137
652
575
591
648
501
588
223
590
610
635
87
680
566
599
162
514
718
129
334
225
734
552
347
706
400
592
290
235
308
496
696
186
696
448
156
637
250
730
634
681
283
457
24
621
194
424
361
739

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun Jul 10, 2005 11:23 pm

Hi guys

Could someone give me a hint? I got RTE several times, sadly I don

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Mon Jul 11, 2005 4:20 am

Your code crashes even for the sample input. Did you really test your code with the sample input?

Your code crashes for this input:

Input:
1000000000
0

Correct Output:
438744

from the sample test data.

And running your code with gdb in Unix points to the f() function as the culprit. I think there is a recursion stack overflow since the f() function in your code is recursive.

In fact, you don't really need a recursive function to solve this problem. I got AC using an iterative approach using the formula given in this thread, and computing something else to avoid recursion.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Tue Jul 12, 2005 4:46 am

chunyi81 wrote: In fact, you don't really need a recursive function to solve this problem. I got AC using an iterative approach using the formula given in this thread, and computing something else to avoid recursion.
Hi chunyi81, thx for your reply. Would you mind telling me what approach are you using?

Thx in advance. Please, send me your reply by PM :P

Post Reply

Return to “Volume 100 (10000-10099)”