Search found 24 matches

by Pupirev Sergei
Mon Aug 08, 2005 8:13 pm
Forum: Volume 108 (10800-10899)
Topic: 10887 - Concatenation of Languages
Replies: 49
Views: 18798

Someone who got AC, how fast does your program run on the input produced by this program? My program (currently the fastest on the ranklist) takes 6.5 sec on my Pentium-II 400. My program is currently the second on the ranklist ;) And it runs < 0.1 sec. on this test. My program's complexity is abou...
by Pupirev Sergei
Sat May 21, 2005 7:33 pm
Forum: Volume 108 (10800-10899)
Topic: 10845 - The crusades
Replies: 4
Views: 2204

- Do a brute force for the first king's path
But isn't it O(2^30) ?
by Pupirev Sergei
Fri May 20, 2005 8:22 am
Forum: Volume 108 (10800-10899)
Topic: 10845 - The crusades
Replies: 4
Views: 2204

10845 - The crusades

Can somebody help to solve this problem? I don't know algorithm faster than O(2^30)...
by Pupirev Sergei
Mon Oct 18, 2004 4:15 pm
Forum: Volume 107 (10700-10799)
Topic: 10748 - Knights Roaming
Replies: 16
Views: 5853

I don't know how you can come up with 100 000000 such a big number. Consider we have 50 knights where every one can walk 50 steps. Maximum number of covered square < 50 x 35000 = 1750000 Even you sort all the 1750000 squares in a qsort, the number of operation should be < 1 0000000 (although this i...
by Pupirev Sergei
Mon Oct 18, 2004 4:50 am
Forum: Volume 107 (10700-10799)
Topic: 10748 - Knights Roaming
Replies: 16
Views: 5853

I used hash, but my program is too slow. I think a best algorithm should has about 100 000000 operations, isn't it? If you've done this problem can you send me solution? pserega@r66.ru
by Pupirev Sergei
Sun Oct 17, 2004 8:15 pm
Forum: Volume 107 (10700-10799)
Topic: 10748 - Knights Roaming
Replies: 16
Views: 5853

10748 - Knights Roaming

Hi, everyone!
Can you give me some hints how to solve the problem. My algo is too slow. How can it be done?
Thx
by Pupirev Sergei
Sat May 22, 2004 4:14 pm
Forum: Volume 106 (10600-10699)
Topic: 10655 - Contemplation - Algebra
Replies: 42
Views: 10633

10655 - Contemplation - Algebra

Dear Jury!
What is the tricky input tests of this problem?
Only 5 AC of almost 1000 submits!!!
by Pupirev Sergei
Thu Oct 30, 2003 3:52 pm
Forum: Other words
Topic: Contest!!!
Replies: 2
Views: 1101

Oops...
Sorry, it will be on 08.11.2003
by Pupirev Sergei
Thu Oct 30, 2003 3:01 pm
Forum: Other words
Topic: Contest!!!
Replies: 2
Views: 1101

Contest!!!

Don't miss contest of Ural server on 01.11.2003 !!!
Visit this link : http://acm.timus.ru/schedule.aspx
by Pupirev Sergei
Wed Sep 10, 2003 9:51 am
Forum: Volume 101 (10100-10199)
Topic: 10185 - Phylogenetic Trees Inherited
Replies: 0
Views: 1396

10185 - Phylogenetic Trees Inherited

I' ve solved this problem, but my algorithm works too slow.
My result is the worst in statistics.
But some people got AC faster than 1 sec/ Can somebody explain me how to solve it faster?
Thanks!
by Pupirev Sergei
Wed Sep 03, 2003 5:05 am
Forum: Volume 105 (10500-10599)
Topic: 10542 - Hyper-drive
Replies: 9
Views: 5255

I used the following algorithm: ans(a,b)=a+b-gcd(a,b); ans(a,b,c)=a+b+c-gcd(a,b)-gcd(a,c)-gcd(b,c)-gcd(b,c)+gcd(a,b,c) ans(a,b,c,d)=a+b+c+d-gcd(a,b)-...-gcd(c,d)+gcd(a,b,c)+gcd(a,c,d)+gcd(a,b,d)+gcd(b,c,d)-gcd(a,b,c,d) I cant proove it for dimension higher than 3, but for dimensions 1,2 or 3 a proof...
by Pupirev Sergei
Tue Sep 02, 2003 6:53 pm
Forum: Volume 105 (10500-10599)
Topic: 10542 - Hyper-drive
Replies: 9
Views: 5255

Some tests:
1
3
3 6 2
0 0 0
answer is: 6

1
5
1 2 3 4 5
0 0 0 0 0
answer is: 10

1
4
10 13 11 5
-4 -2 4 8
answer is: 28

1
452 467 18 454 28 70 43 152 56 24
345 544 5645 78 455 5666 789 764 53 3
answer is: 13544
by Pupirev Sergei
Tue Aug 26, 2003 5:28 pm
Forum: Volume 105 (10500-10599)
Topic: 10546 - The Eagle's Nest
Replies: 23
Views: 10848

Hm, i do the same thing, but still WA.
Can somebody prove that greedy method give the correct answer?
by Pupirev Sergei
Tue Aug 26, 2003 10:49 am
Forum: Volume 105 (10500-10599)
Topic: 10546 - The Eagle's Nest
Replies: 23
Views: 10848

10546 - The Eagle's Nest

I can't understand, why my algorythm is wrong. I've checked it many times. Can somebody give me test cases.

I used the following algo:
Let K-the maximum number of mission for one game. I find first increasing subsequense of length K, delete it from original sequense. Then repeat it.
by Pupirev Sergei
Mon Jun 23, 2003 1:09 pm
Forum: Volume 3 (300-399)
Topic: 300 - Maya Calendar
Replies: 69
Views: 9923

Both codes got AC.
How did you got PE?

Go to advanced search