## 10742 - The New Rule in Euphomia

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 10742 - The New Rule in Euphomia

I've been thinking about this one for days now, but I cannot see the light at the end of the tunnel. I have a program that gives the correct results, but it burns away almost 4 minutes of my machine's processor time

This is my method:

1. Use a sieve to produce all the 78k+ primes upto 1M. This takes just a split second.

2. Calculate the array pairs[1M+1], where pairs[n] is the number of ways n can be the sum of two different primes. I use the obvious O(N^2) for this by double looping through all primes and incrementing pairs[prime1+prime2]. This, however takes way too long (roughly 78k*78k/2 = 3G iterations).

3. Recursively fill the array ways[1M+1], where ways[n] is the number of ways the amount n can be paid: ways[1]=0; ways=ways[i-1]+pairs. This step also takes a split second.

Can someone push me into the right direction?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

### Re: 10742 The New Rule in Euphonia - I need a big hint :(

little joey wrote:2. Calculate the array pairs[1M+1], where pairs[n] is the number of ways n can be the sum of two different primes. I use the obvious O(N^2) for this by double looping through all primes and incrementing pairs[prime1+prime2]. This, however takes way too long (roughly 78k*78k/2 = 3G iterations).
Suppose you already have the primes and know the value N. Instead of trying all pairs of primes, you can count the number of good prime pairs by using two pointers into the array of primes. (At the beginning, the first pointer is set to 2, the second to the largest prime <=N-2. Each time you move the first pointer to the right... I think you get the idea ) This works in time linear in the number of primes.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Thanks man!
That was exactly the kind of hint I needed.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
I need to thanks misof also.
I am in the same situation as little joey........
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

truckDriver
New poster
Posts: 5
Joined: Thu Oct 21, 2004 6:58 am

### Plz Check my result ...

I got several times WA..
below result right?
or any trick in this problem?
or have you any test data ? plz .. help..

1
2
3
4
5
6
7
8
9
10
123456
987654
111111
999999
1000000
0
Case 1: 0
Case 2: 0
Case 3: 0
Case 4: 0
Case 5: 1
Case 6: 1
Case 7: 2
Case 8: 3
Case 9: 4
Case 10: 5
Case 11: 37077728
Case 12: 1634254959
Case 13: 30670682
Case 14: 1671911340
Case 15: 1671916742

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
I get the same output and I'm not aware of any special cases. Some random input:
463529
131742
296587
670354
244441
298855
554013
866077
567537
708196
334295
355923
339320
684379
910936
750177
218812
298880
888620
99807
968171
730970
294932
904967
129980
677418
245604
689848
916723
413112
559127
394497
330608
905258
204669
113113
797657
662831
734064
394073
550613
402219
308552
277557
760652
786625
721806
991097
956002
373686
33239
150958
612689
921413
353815
968014
322795
561002
717357
261501
581445
266095
274174
613793
755468
17018
663788
216277
53230
76324
966170
462888
483045
625323
155845
137152
621784
442273
252973
744426
98949
379545
96173
687859
695426
682698
772065
239413
849989
18214
598606
671847
727383
783294
248280
190023
225374
471029
141521
999979
0
Output:
Case 1: 409115182
Case 2: 41689498
Case 3: 181363813
Case 4: 803076886
Case 5: 127637608
Case 6: 183888162
Case 7: 566669174
Case 8: 1284137969
Case 9: 592199707
Case 10: 887992917
Case 11: 225472237
Case 12: 252771426
Case 13: 231690813
Case 14: 834086234
Case 15: 1408849417
Case 16: 986786637
Case 17: 104397125
Case 18: 183917202
Case 19: 1346150941
Case 20: 25282813
Case 21: 1575582593
Case 22: 941004494
Case 23: 179532099
Case 24: 1391945625
Case 25: 40688037
Case 26: 818629143
Case 27: 128742492
Case 28: 846327643
Case 29: 1425324415
Case 30: 331614150
Case 31: 576261238
Case 32: 304889272
Case 33: 220959761
Case 34: 1392770932
Case 35: 92483446
Case 36: 31672399
Case 37: 1104224217
Case 38: 786664271
Case 39: 948314693
Case 40: 304292056
Case 41: 560327151
Case 42: 315859703
Case 43: 194869298
Case 44: 160773731
Case 45: 1012160464
Case 46: 1076387006
Case 47: 919504598
Case 48: 1644712096
Case 49: 1539438464
Case 50: 276231677
Case 51: 3536663
Case 52: 53315399
Case 53: 681215885
Case 54: 1438733295
Case 55: 250045862
Case 56: 1575116065
Case 57: 211536533
Case 58: 579804222
Case 59: 909150335
Case 60: 144274607
Case 61: 618996504
Case 62: 148907149
Case 63: 157229562
Case 64: 683465532
Case 65: 999567594
Case 66: 1082971
Case 67: 788744853
Case 68: 102216196
Case 69: 8186867
Case 70: 15610884
Case 71: 1569617090
Case 72: 408088500
Case 73: 441098637
Case 74: 707161944
Case 75: 56482646
Case 76: 44830472
Case 77: 699852665
Case 78: 375534113
Case 79: 135844487
Case 80: 972988005
Case 81: 24892655
Case 82: 284168636
Case 83: 23648811
Case 84: 841865638
Case 85: 858896937
Case 86: 830343493
Case 87: 1040156264
Case 88: 122914932
Case 89: 1240722847
Case 90: 1220634
Case 91: 652834705
Case 92: 806350908
Case 93: 932559426
Case 94: 1068049231
Case 95: 131301095
Case 96: 80841065
Case 97: 110146895
Case 98: 421265459
Case 99: 47445497
Case 100: 1671852103

truckDriver
New poster
Posts: 5
Joined: Thu Oct 21, 2004 6:58 am

### thax ^^

Thnak you very very much.... Krzysztof Duleba

your test data very helpful for me to catch the BBUG !!!

At last , I got ACC.

thanx Again...

Have a nice day always .......... ^ ^

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

### Re: 10742 The New Rule in Euphonia - I need a big hint :(

misof wrote: Suppose you already have the primes and know the value N. Instead of trying all pairs of primes, you can count the number of good prime pairs by using two pointers into the array of primes. (At the beginning, the first pointer is set to 2, the second to the largest prime <=N-2. Each time you move the first pointer to the right... I think you get the idea ) This works in time linear in the number of primes.
ny pseudo code is like this
for N:=1 to 1M
let the first pointer to 2, the second pointer to the largest primes <=N-2
move the two pointer
The time complexity looks like O(n^2).
if something I missed.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: 10742 The New Rule in Euphonia - I need a big hint :(

windows2k wrote: for N:=1 to 1M
...
You don't have to count the answer for every N in 1..1M, it is sufficient to count the answer just for (at most 600) Ns given on the input.

numan947
New poster
Posts: 3
Joined: Mon Nov 03, 2014 9:46 am

### Re: 10742 The New Rule in Euphonia - I need a big hint :(

I need to thank misof too The solution I made before was of O(n^2) complexities. Now I think I can make it fast enough to get AC IsA