OJ Board

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?

use mozilla

I don't get your idea.....how you avoid factoring the numbers?

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

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

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

you're right martin, i was wrong saying that, anyway those cases dont appear in the input(ohterwise i would get wrong answer)

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)

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

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

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.

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

mamun wrote:Try to get rid of function, sod(). It's all divisions and consumes a lot of time.

any hints for avoiding sod(),but still in a precalculating approach?

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?

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