10049

pc5971 · 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 · 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.

rbuchan · 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 · 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 · 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 · 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 · 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.

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

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

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

Antonio Ocampo · 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 · 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 · 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

OJ Board

10049 - Self-describing Sequence

10049 - Self-describing Sequence

Re: 10049 algo

700000?

Accepted

Thanks friend.

10049