What is ACM? :)
Posted on 2002-03-07 22:38:40 by The Svin
Posted on 2002-03-07 22:49:37 by bitRAKE
I read first problem and found mistake in explonation:
Given an input n, it is possible to determine the number of numbers printed before the 1 is printed.


And in example there is 15 numbers BEFORE 1.
How can you solve anything if conditions is not clear?
For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.
Posted on 2002-03-08 00:51:10 by The Svin
Here is the problem explaination:
http://acm.uva.es/p/v1/100.html
Posted on 2002-03-08 00:56:32 by bitRAKE
I agree, their problems are very confusing at some point.

...and the maximum cycle length for integers between and including i and j.


They could have said: Find the largest cycle length from i to j.

Or better yet, the whole problem could be rephrase to this:

Given the input i and j, values entered can only be in the range of 1 - 9999. Find the largest cycle length between i to j using the provided pseudo code algorithm above. When done, print out first the inputs i and j separated with a space, then print out the outputs on a new line i, j and the largest cycle lengths separated by a space....

=-=-=-=-=-=-=-=-=
Maybe they made it that way as a part of the problem :) who knows?
Posted on 2002-03-08 01:06:22 by stryker
Yes, I agree that they really went out of their way
to not direct you in finding an algorithm.
Posted on 2002-03-08 01:27:27 by bitRAKE
So to print 1 is counted as cycle, isn't it?
Posted on 2002-03-08 07:50:19 by The Svin
yes, for example



the value 10

10 5 16 8 4 2 1
this has a cycle length of 7

in your case the value is 1

1
this has a cycle length of 1


:)
Posted on 2002-03-08 09:25:07 by stryker
Here's my try at it...

Enter the smaller value, then the larger value. End with a blank line. This took about 3 seconds to check all numbers from 1 to 999999 on my 400Mhz PII. Nasm source is included.

Posted on 2003-04-29 14:51:04 by Sephiroth3
I also recently noticed this thread.

A distributed project about 3x+1 exists:
http://personal.computrain.nl/eric/wondrous/index.html

One year ago, the program was perfectible.
Perhaps can it be improved ?
Posted on 2003-04-30 08:15:49 by MCoder

Don't apologize - the contest problem is almost ten times as old.
Posted on 2003-04-30 20:23:35 by bitRAKE
Wow, it's been a long time. :)

and I forgot my promise to change some stuff... :tongue:



As promised to change to richedit control...

I also modified everything from the GUI design to the algo. I removed the bloated unnecessary stuff. I modified the main algo to accept a callback function for output. Study the the callback function I made to found out how to use it on other applications.
invoke  acm100, i, j, OFFSET acmout
acmout is the callback function.

This is much simpler in design and much easier to integrate on another program.

No need to create two different programs(like I did before) for different style of outputs, Just comment some code and you're done(see source inside - inside acmout function).


p.s. Would be nice if some mod would remove the older attachments made by me(and I repeat, only mine(stryker)), to prevent "confusion". And also edit the post and add a note that my final attachment is here. Thank You. :)




added limits 1-999999 only
Posted on 2003-05-01 17:46:54 by arkane
here's my final algo.
[size=9]acm100 PROC USES ebx esi edi i:DWORD, j:DWORD, lpCallback:DWORD


xor ebx, ebx
xor edx, edx
mov esi, i
mov edi, j
mov eax, esi

__mainalgoA:

push eax
push edx

push 0
push 0
push eax
call lpCallback

pop edx
pop eax

__mainalgoB:

inc edx
cmp eax, 1
je __mainalgoC
test eax, 1
jnz __odd
shr eax, 1
jmp __mainalgoA
__odd:
mov ecx, eax
lea eax, [eax+eax]
lea eax, [eax+ecx+1]
jmp __mainalgoA

__mainalgoC:

cmp ebx, edx
jae __mainalgoD
mov ebx, edx

__mainalgoD:

push 0
push edx
push 0
call lpCallback

xor edx, edx
inc esi
mov eax, esi
cmp esi, edi
jbe __mainalgoA

push ebx
push j
push i
call lpCallback

ret

acm100 ENDP[/size]
I don't have plans to optimize this further. And no plans to use cmovCC instructions - though they will help a lot but I prefer compatibility. :)



USES ebx edi edi --- USES ebx esi edi

and

lea eax,
lea eax,
inc eax

to

lea eax,
lea eax,

You can speed up a little bit by removing the calls to the callback function and at the last step, return the value of ebx (mov eax, ebx) to get the largest cycle count.
Posted on 2003-05-01 18:28:04 by arkane