11246 - K-Multiple Free set

[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

[sclo]

There is a counting solution that is O(log n) time and O(1) memory

[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?

[emotional blind]

AFAIK
it should be like this

f(n,i) = n/(k^i) - f(n, i+1)

Result is: f(n,0)

SPOILER??

[saman_saadi]

Thanks emotional blind for your nice recurrence

Code: Select all

Deleted

Thanks for your help

[emotional blind]

saman_saadi,
too much spoiler.. just remove your series under Code :

[adelar]

hi,
always have solution for all inputs?
thanks in advance.

[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

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

[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?

[adelar]

Hi saman_saadi,
thank you by the hint
here is my code. it's use emotional blind recurrence:

Code: Select all

AC

input:

Code: Select all

3
10 2
100 2
1000 2

output:

Code: Select all

6
62
625

you can to see my error?
thanks.

[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

[sclo]

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.

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

[adelar]

Hello,
thanks saman_saadi and sclo
I got AC