## 10049 - Self-describing Sequence

Moderator: Board moderators

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

### 10049 - Self-describing Sequence

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

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?

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
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
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

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

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

deneb
New poster
Posts: 6
Joined: Mon Nov 17, 2003 3:39 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.

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

Niaz
The Last Man Standing

deneb
New poster
Posts: 6
Joined: Mon Nov 17, 2003 3:39 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
Contact:

### 10049

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
L I M O N

szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland
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
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
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
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?