Page 1 of 2
11246 - K-Multiple Free set
Posted: Sun Jul 29, 2007 7:03 am
by saman_saadi
Hi
I got AC this question in the contest time but when this question added in online judge problemset I got TLE. What's Wrong?
My algorithm is:
I first select the numbers that is not the factor of k then consider the factors of k. suppose x is a factor of k (x = ak) if I selected a or a is belong to non-factors of k I don't select x otherwise select it.
for example consider n = 10 an k = 2. First I select 1, 3, 5, 7, 9. Now only the factors of 2 remains we cannot select 2 because we select 1 so we don't select 2 and this cause we select 4. We cannot select 6 because we select 3. We cannot select 8 because we select 4. We cannot select 10 because we select 5.
and I use an array named select which select = (i + 1) * k It means I only keep the factors of k and select occupy only one bit
Thanks
Posted: Sun Jul 29, 2007 7:37 am
by sclo
There is a counting solution that is O(log n) time and O(1) memory
Posted: Sun Jul 29, 2007 3:11 pm
by saman_saadi
Thanks for your reply sclo. Can you give me some hint? I saw Double-Free Set recurrence that works for k = 2:
Code: Select all
f(n) = ceil(n / 2) + f(floor(n / 4))
But how above recurrence work?
Posted: Sun Jul 29, 2007 5:23 pm
by emotional blind
AFAIK
it should be like this
f(n,i) = n/(k^i) - f(n, i+1)
Result is: f(n,0)
SPOILER??
Posted: Sun Jul 29, 2007 6:11 pm
by saman_saadi
Thanks emotional blind for your nice recurrence
Thanks for your help
Posted: Sun Jul 29, 2007 6:17 pm
by emotional blind
saman_saadi,
too much spoiler.. just remove your series under Code :
wa
Posted: Wed Aug 01, 2007 10:07 pm
by adelar
hi,
always have solution for all inputs?
thanks in advance.
Posted: Wed Aug 01, 2007 10:43 pm
by saman_saadi
If you mean the output become 0, I must say "no!" Because n >= 1 and k >= 2 so we always can select at least one number
...
Posted: Thu Aug 02, 2007 8:45 pm
by adelar
Hi,
thank you.
I have a algorithm that solve this problem, but with segmentation fault. I'm implementing with BigInt. There is other way?
thank you.
Posted: Thu Aug 02, 2007 9:02 pm
by saman_saadi
You don't need BigInt. "int" is enough because n <= 1000000 < 2 ^ 31 - 1 You don't say anything about your algorithm but you can use emotional blind recurrence:
AFAIK
it should be like this
f(n,i) = n/(k^i) - f(n, i+1)
Result is: f(n,0)
SPOILER??
Think about the recurrence. why it's true and what it means?
+/-wa
Posted: Fri Aug 03, 2007 9:51 pm
by adelar
Hi saman_saadi,
thank you by the hint
here is my code. it's use emotional blind recurrence:
input:
output:
you can to see my error?
thanks.
Posted: Fri Aug 03, 2007 10:29 pm
by saman_saadi
1) Don't use float, double, long double (same as double in some compilers) as sentinel. for example:
Code: Select all
double i;
for (i = 0; i < 3; i++) //dangerous code
{
}
you declare t as long double. In my compiler your program didn't terminate so you must declare t as int.
2) I think you don't understand the recurrence correctly. Before use it try to prove it. emotional blind don't explain the recurrence too much because he wants we think about it.
3) In my computer your code only output 0
Posted: Sat Aug 04, 2007 2:02 am
by sclo
saman_saadi wrote:1) Don't use float, double, long double (same as double in some compilers) as sentinel. for example:
I thought the IEEE standard for double precision floating point numbers requires them to represent 52bit fractional digits. So it follows that they can represent every 32bit integers exactly. However, some decimal such as 0.1 don't have a finite base 2 representation, so they can't be represented exactly. As a rule of thumb, float's range and precision is so limited that I can't find any reason to use floats, unless you're really out of space.
The error above lies in that we requires only integer floor, not floating point division.
Posted: Sat Aug 04, 2007 10:43 am
by saman_saadi
I thought the IEEE standard for double precision floating point numbers requires them to represent 52bit fractional digits. So it follows that they can represent every 32bit integers exactly. However, some decimal such as 0.1 don't have a finite base 2 representation, so they can't be represented exactly. As a rule of thumb, float's range and precision is so limited that I can't find any reason to use floats, unless you're really out of space.
The error above lies in that we requires only integer floor, not floating point division.
Yes you right But I think for more clarity when we need an integer value we use int. see below code:
Code: Select all
#include <stdlib.h>
#include <stdio.h>
int main()
{
long double a;
scanf("%lf", &a);
while (a--);
return 0;
}
In VS2003 It terminates but in DevC++ and code::blocks that their default compiler is GCC don't terminate but if you declare long double as double then the program will terminate in both devc++ and code::blocks so I prefer use int not double.
AC
Posted: Sat Aug 04, 2007 7:05 pm
by adelar
Hello,
thanks saman_saadi and sclo
I got AC