Search found 62 matches

by trulo17
Sun Jul 15, 2007 8:36 pm
Forum: Volume 112 (11200-11299)
Topic: 11240 - Antimonotonicity
Replies: 33
Views: 12398

Robert Gerbicz wrote:
here is a dp solution using O(n) time and O(1) memory, and it is trivial to prove that the algorithm is correct. It's a little surprising.
Find this really surprising. Always think of dp as a trade of space for time.Could someone shed some light on this?
by trulo17
Sat Jul 07, 2007 11:50 am
Forum: Other words
Topic: How to submit solution for the contest?
Replies: 2
Views: 2309

use mozilla
by trulo17
Mon Jun 11, 2007 9:12 pm
Forum: Volume 112 (11200-11299)
Topic: 11226 - Reaching the fix-point.
Replies: 23
Views: 10274

I don't get your idea.....how you avoid factoring the numbers?
by trulo17
Sun Jun 10, 2007 10:03 pm
Forum: Volume 112 (11200-11299)
Topic: 11226 - Reaching the fix-point.
Replies: 23
Views: 10274

mmm..... I submited my contest solution and it passed in 1.754, so after what you said maybe my precalc step is too expensive. This is my meoized function: int f(int x){ int &r=t[x]; if(r!=-1)return r; int s=0,x2=x; while(x%2==0){x/=2;s+=2;} for(int i=3;i*i<=x;i+=2)while(x%i==0){x/=i;s+=i;} if(x>1)s...
by trulo17
Sun Jun 10, 2007 5:48 am
Forum: Volume 112 (11200-11299)
Topic: 11226 - Reaching the fix-point.
Replies: 23
Views: 10274

11226 - Reaching the fix-point.

I pre-calculated in a reasonable time the half million values. Where I had problems was with answering the querys. I couldn't find anything better than the naive lineal search. I realized that the maximum value was 15, but couldn't use this fact at all. So.......how did you solve this task? It had a...
by trulo17
Mon Feb 19, 2007 3:00 am
Forum: Volume 3 (300-399)
Topic: 385 - DNA Translation
Replies: 11
Views: 2643

385 DNA Translation

could you help me understand the statement? It's not very clear, how can i know if the given string is the original or complemented dna, or the reversed form of them? Moreover, if more than one of them generates protein? how can i know what to output? thx in advance
by trulo17
Sun Aug 13, 2006 10:59 pm
Forum: Volume 110 (11000-11099)
Topic: 11070 - The Good Old Times
Replies: 42
Views: 15016

you're right martin, i was wrong saying that, anyway those cases dont appear in the input(ohterwise i would get wrong answer)
by trulo17
Sun Aug 13, 2006 3:00 am
Forum: Volume 110 (11000-11099)
Topic: 11070 - The Good Old Times
Replies: 42
Views: 15016

i guess most of the input given here don't appear in judge's input, i got ac withouth considering such cases(in fact, i consider unary operators will appear only at th beginning of a line, after all expresions like 5*-2 doesn't make sense)
by trulo17
Sun Jun 11, 2006 7:44 am
Forum: Off topic (General chit-chat)
Topic: Who will win the World Cup?
Replies: 53
Views: 127275

yeah, lot of surprises, like T&T, i would never have believed they could tie with Sweden.
And about Argentina, they made an impressive first time, although Ivroy Coast played very well also
by trulo17
Tue May 30, 2006 4:48 pm
Forum: Off topic (General chit-chat)
Topic: Who will win the World Cup?
Replies: 53
Views: 127275

though brazil is a really strong team, i guess this time they won't be at finals(3 consecutive finals is just too much) so my bet is on Argentina(Riquelme, Messi and Crespo are enough to make them strong candidates). Final i dream of is England against Argentina, you know, it's a different match for...
by trulo17
Mon May 15, 2006 5:11 am
Forum: Volume 110 (11000-11099)
Topic: 11032 - Function Overloading
Replies: 43
Views: 16809

i first got ac using as much as ten million sod functions(precalculating part) so maybe you are answering querys in a very slow way(for example when you read 2 values, doing a linear search is a really bad idea).Read post aboves to get an idea of what to do in each case.
by trulo17
Mon May 15, 2006 12:01 am
Forum: Volume 110 (11000-11099)
Topic: 11032 - Function Overloading
Replies: 43
Views: 16809

congratulations victor for top place :D i finally managed to get it within 1 second time limit althought with a not so good time (0.891) anyway i still think the time limit was very strict at contest(unless that input was shorter as mamun says) only thing i did to improve was this: sod(i) = i, 1<=i<...
by trulo17
Sun May 14, 2006 9:07 pm
Forum: Volume 110 (11000-11099)
Topic: 11032 - Function Overloading
Replies: 43
Views: 16809

mamun wrote:Try to get rid of function, sod(). It's all divisions and consumes a lot of time.
:P
any hints for avoiding sod(),but still in a precalculating approach?
by trulo17
Sun May 14, 2006 8:15 pm
Forum: Volume 110 (11000-11099)
Topic: 11032 - Function Overloading
Replies: 43
Views: 16809

for(i=1;i<=10000000;++i) B[i+sod(i)]=true; for(i=1;i<=10000000;++i) if(!B[i]) A[ct++]=i; This is how i'm generating my table, i see almost every one is precalculating too(huge memory use). Any better way of precalculating? Btw, don't you think time limit at contest was way too strict?
by trulo17
Sun May 14, 2006 3:15 am
Forum: Volume 110 (11000-11099)
Topic: 11032 - Function Overloading
Replies: 43
Views: 16809

i got this one ac(3.5 seconds, but not in contest time) What i'm doing is to put in an array every 1<=i<=10^7 such that i!=(j+sod(j)) for j<=i, this can be done in linear time. Let's call this "i" special numbers. after precalculating this i answer query for fun(a) with the idea you explained above ...

Go to advanced search