10820 - Send a Table

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

Moderator: Board moderators

AndyGee
New poster
Posts: 8
Joined: Sat Nov 13, 2004 3:11 pm
Location: KG
Contact:

Post by AndyGee » Wed Mar 16, 2005 12:22 pm

Thanks a lot!

mikeblas
New poster
Posts: 6
Joined: Sat Mar 19, 2005 1:21 am

Post by mikeblas » Sun Mar 20, 2005 1:12 am

Which version of VC++ are you using? In vC++ 2003, you can set your projects to use the strict rules for for variable scoping.

.B ekiM

AndyGee
New poster
Posts: 8
Joined: Sat Nov 13, 2004 3:11 pm
Location: KG
Contact:

Post by AndyGee » Sun Mar 20, 2005 8:10 am

Now I use GCC 3.3.3 (cygwin special) and have no more problems...

User avatar
ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

10820 Send a Table

Post by ibrahim » Fri Aug 19, 2005 1:04 pm

Critical I/O please.

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

Re: 10820 Send a Table

Post by Martin Macko » Fri Aug 19, 2005 1:13 pm

An input:

Code: Select all

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
49950
49951
49952
49953
49954
49955
49956
49957
49958
49959
49960
49961
49962
49963
49964
49965
49966
49967
49968
49969
49970
49971
49972
49973
49974
49975
49976
49977
49978
49979
49980
49981
49982
49983
49984
49985
49986
49987
49988
49989
49990
49991
49992
49993
49994
49995
49996
49997
49998
49999
50000
0
My AC's output:

Code: Select all

1
3
7
11
19
23
35
43
55
63
83
91
115
127
143
159
191
203
239
255
279
299
343
359
399
423
459
483
539
555
615
647
687
719
767
791
863
899
947
979
1059
1083
1167
1207
1255
1299
1391
1423
1507
1547
1611
1659
1763
1799
1879
1927
1999
2055
2171
2203
2323
2383
2455
2519
2615
2655
2787
2851
2939
2987
3127
3175
3319
3391
3471
3543
3663
3711
3867
3931
4039
4119
4283
4331
4459
4543
4655
4735
4911
4959
5103
5191
5311
5403
5547
5611
5803
5887
6007
6087
1516799635
1516885315
1516927939
1516994539
1517044491
1517122827
1517154507
1517254419
1517304375
1517356215
1517396151
1517493855
1517524095
1517618111
1517668071
1517721351
1517762679
1517859111
1517892327
1517991119
1518028847
1518095471
1518140111
1518216671
1518249983
1518329903
1518379871
1518446399
1518496375
1518587895
1518609399
1518708399
1518757503
1518824143
1518868943
1518942671
1518975983
1519058927
1519108911
1519171983
1519211967
1519311947
1519345259
1519445243
1519488083
1519536083
1519584243
1519677811
1519708531
1519808527
1519848527

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

I need to know how to deal with this ...

Post by nymo » Sun Sep 18, 2005 4:49 pm

I 've tried to solve this problem, but i am never passing time limit.

I tried something like this :

i. for 1 ... Jimmy had to precalculate 1 value namely (1, 1)
ii. for i = 2 .. N, number of precalculated value = precalculated value for (i-1) + (2*(no. of j(= 1..i-1) that are relatively prime to i))

I use prime factoring to find those j's.

Is there anything wrong with my algo.? or, else how can i make it faster(it is not passing the limit )? :-?

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Sun Sep 18, 2005 5:29 pm

The slow part is probably your factoring. If you are iterating up to the square root of i and using the totient function then I would think that would be fast enough.

You could always try to use a faster factoring method.
I'm always willing to help, if you do the same.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Sun Sep 18, 2005 8:16 pm

Dear Ryan pai,
Thanks a lot, I just got ACC :D , now it takes 0.096sec(Now, i 've passed the limit...).

I use Euler's phi function just as you 've mentioned, my factoring was a bit okay, but to factor out the multiples of factors, I used something like sieve ... and for marking and unmarking, I use loops and memset() everytime ... I guess that was the bottleneck. Anyway, thanks a lot ...

xlvector
New poster
Posts: 11
Joined: Thu Dec 29, 2005 8:30 am
Contact:

I also have time problem

Post by xlvector » Thu Dec 29, 2005 2:42 pm

I use totient function , but it still needs factoring,

I use this : if (m,n)=1, f(mn)=f(m)f(n)
but I find it cost time when I divide a numer m*n into m,n

can someone help me

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

Hint

Post by medv » Wed Jan 04, 2006 2:05 pm

To xlvector:
I think it's enough to evaluate f(n):

int f(int n)
{
int result = n;
for(int i=2;i*i <= n;i++)
{
if (n % i == 0) result -= result / i;
while (n % i == 0) n /= i;
}
if (n > 1) result -= result / n;
return result;
}

Then precompute all f(n), n=1,50000. And will get ACC.
Still wa - write me, I got acc.

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

Post by Observer » Thu Jan 05, 2006 7:59 am

Hi,

If I remember correctly, I also used something like sieve...

I'm currently ranked #2 for this task. But I have no idea how 0.00.002 can be achieved.... Faster I/O? :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Jan 05, 2006 1:29 pm

Observer wrote:I'm currently ranked #2 for this task. But I have no idea how 0.00.002 can be achieved.... Faster I/O? :wink:
Now you're third ;-) Faster I/O doesn't help here as the input is very small.

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

Post by Observer » Thu Jan 05, 2006 2:13 pm

Krzysztof Duleba wrote:Now you're third ;-)
Good for you~ Don't want to improve my code, since I think it is now short (14 lines) and beautiful. (And the other reason is of course I don't know what I can improve :wink:)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Jan 05, 2006 4:48 pm

14 lines - that's pretty impressive. The sieve loop alone took me 21 lines.

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

Post by Observer » Thu Jan 05, 2006 5:15 pm

okay, maybe not that impressive... One of the lines read:

Code: Select all

for (i=3;i<=223;i+=2) if (!fac[i]) for (s=i*i;s<=50000;s+=i<<1) fac[s]=i;
which is long, though I find no reason to break it into several lines.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Post Reply

Return to “Volume 108 (10800-10899)”