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

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