10325 - The Lottery

[20571KJ]

I had a solution but it's too slow.
If you don't mind, please help me....show me a better one ???
Thank you.

[Christian Schuster]

Hi,

I did it the following way:

- set the initial "result" value to n.
- compute the lcm of every subset of divisors (except the empty one)
- if the size of a subset it odd, subtract n/lcm from "result"
- if it is even, add n/lcm to "result"

Those operations can be done in an iteration loop, doing some bit manipulation and lcm(a,b)=a*b/gcd(a,b).

I got AC in 270ms, but I don't know how to reach 20ms. That seems incredible!

[20571KJ]

I try to do this problem. I found a very special DP. I think that I was right.
Here's my program. It's really short. But I get WA. I cannot find what wrong. But I did test it carefully. Anyone help me ??
(I use TP7)


[pascal]
const fi = 'lottery.in';
fo = 'lottery.out';

type
tab1 = array [1..15] of longint;


var
S: tab1;
max, n, i: longint;


function UCLN(a, b: longint): longint;
begin
if a mod b = 0 then UCLN := b
else UCLN := UCLN(b, a mod b);
end;


function F(Num: tab1; n: byte; Max: longint): longint;
var
j, i, k: longint;
S: tab1;
begin
if n = 1 then F := Max div Num[1]
else
begin
j := 0;
for i := 1 to N-1 do
begin
k := round(Num / UCLN(Num, Num[n]));
if (j = 0) or (S[j] <> k) then
begin
j := j + 1;
S[j] := k;
end;
end;
F := F(Num, n-1, Max) + Max div Num[n] - F(S, n-1, Max div Num[n]);
end;
end;


begin
assign(input, fi); reset(input);
assign(output, fo); rewrite(output);
read(max);
read(n);
for i := 1 to n do read(s);
writeln(Max - F(S, n, Max));
close(input); close(output);
end.[/pascal]

[20571KJ]

I try to do this problem. I found a very special DP. I think that I was right.
Here's my program. It's really short. But I get WA. I cannot find what wrong. But I did test it carefully. Anyone help me ??
(I use TP7)


[pascal]
const fi = 'lottery.in';
fo = 'lottery.out';

type
tab1 = array [1..15] of longint;


var
S: tab1;
max, n, i: longint;


function UCLN(a, b: longint): longint;
begin
if a mod b = 0 then UCLN := b
else UCLN := UCLN(b, a mod b);
end;


function F(Num: tab1; n: byte; Max: longint): longint;
var
j, i, k: longint;
S: tab1;
begin
if n = 1 then F := Max div Num[1]
else
begin
j := 0;
for i := 1 to N-1 do
begin
k := round(Num / UCLN(Num, Num[n]));
if (j = 0) or (S[j] <> k) then
begin
j := j + 1;
S[j] := k;
end;
end;
F := F(Num, n-1, Max) + Max div Num[n] - F(S, n-1, Max div Num[n]);
end;
end;


begin
assign(input, fi); reset(input);
assign(output, fo); rewrite(output);
read(max);
read(n);
for i := 1 to n do read(s);
writeln(Max - F(S, n, Max));
close(input); close(output);
end.[/pascal]

[Joe Smith]

A few things, dunno if these will help:

1. Shouldn't you be reading from stdin/stdout instead of those files? (I don't know, I don't use Pascal for my solutions.)

2. Your algorithm doesn't look correct to me, but I don't think I really understand what you're trying to do in it. There was a good hint above... if that doesn't help, here's the meat of my solution (in C):

[cpp]
int div(int sign, int m, long long val) {
if (val>N) return 0;
if (m==M) return sign*(N/val);
return div(sign,m+1,val) + div(-1*sign,m+1,lcm(val,nums[m]));
}
[/cpp]

3. Watch out for integer overflow (each of the numbers can be up to 2^31-1).

[20571KJ]

I did solve this problem. My program run in 0.13s.
But I see that someone can run in 0.02s.
That's great. Anyone know how ??
Ah.., here is my program.
I used Dynamic Programing. But, it's very special ???

[pascal]
type
tab1 = array [1..15] of integer;


var
S: tab1;
max, n, i: integer;


function UCLN(a, b: integer): integer;
begin
if a mod b = 0 then UCLN := b
else UCLN := UCLN(b, a mod b);
end;


function F(Num: tab1; n, Max: integer): integer;
var
j, i, k: integer;
S: tab1;
begin
if n = 1 then F := Max div Num[1]
else
begin
j := 0;
fillchar(S, sizeof(S), 0);
for i := 1 to N-1 do
begin
k := Num div UCLN(Num, Num[n]);
if (j = 0) or (S[j] <> k) then
begin
j := j + 1;
S[j] := k;
end;
end;
F := F(Num, n-1, Max) + Max div Num[n] - F(S, j, Max div Num[n]);
end;
end;


begin
while not Eof(input) do
begin
readln(max, n);
for i := 1 to n do read(s);
readln;
writeln(Max - F(S, n, Max));
end;
end.
[/pascal]

[Adrian Kuegel]

Have you thought about input like:
20 4
2 4 6 8
It is the same as
20 1
2
If you remove the numbers that are not needed you will improve your runtime.

[tokei]

I am gonna go nuts because of this problem....
I got W.A 12 times.....

Can anyone give me some test cases to help me?

Thanks in advance.

[Adrian Kuegel]

It is probably the same mistake I did during contest.
Try this input:
20 2
4 6
Output:
13

[tokei]

Actually, my program produces the correct answer for the above test case. However, I still do not understand why my program could not get accepted. >_<

Here is my code:

[cpp]
#include <stdio.h>
#include <math.h>

long long int save[100],used[100],num[100];
long long int result,m,n;

long long int gcd(long long int a,long long int b)
{
if(a%b==0) return b;
else return gcd(b,a%b);
}

void DFS(int k,int depth,int next) // find subset...
{
int i;
if(depth==k) {
long long int g,l,tmp;
int j;
g = save[0];
l = save[0];
for(j=1;j<depth;j++) {
g = gcd(g,save[j]);
}
for(j=1;j<depth;j++) {
l*=save[j];
if(l/g > n) { break; }
}
l/=g;
if(k%2)
result -= n/l;
else
result += n/l;
}
for(i=next;i<m;i++) {
if(!used) {
used=1;
save[depth] = num;
DFS(k,depth+1,i+1);
used=0;
}
}
}

void check()
{
int flag=1;
int i,j,mov;
while(flag) {
flag=0;
for(i=0;i<m;i++) {
for(j=i+1;j<m;j++) {
if(num%num[j]==0||num[j]%num==0) {
if(num>num[j])
mov = i;
else
mov = j;
flag=1;
break;
}
}
if(flag) break;
}
next:
if(flag) {
for(i=mov;i<m;i++)
num = num[i+1];
m--;
}
}
}

int main()
{
int k,i,j;
while(scanf("%lld %lld",&n,&m)!=EOF) {
for(i=0;i<m;i++) {
scanf("%lld",&num);
}

check(); // find if there exists a case such that 2,4,8,16....

for(k=0;k<=m;k++)
used[k]=0;
result = n;
for(k=0;k<m;k++)
result -= n/num[k];
for(k=2;k<=m;k++)
DFS(k,0,0);
printf("%lld\n",result);
}
return 0;
}
[/cpp]

[Dmytro Chernysh]

My program does passes all test cases in the forum and the test cases that AC program that is posted in the forum, but why WA?
Can anybody post some trick test cases?[/pascal][/code]

[Cosmin.ro]

I had a hard time with large numbers ...
Here is a input:
2000000000 14
1073741789 1073741783 1073741741 1073741723 1073741719 1073741717 1073741689 1073741671 1073741663 1073741651 1073741621 1073741567 1073741561 1073741527
Output:
1999999986

[Rajib]

Here is some test cases:

Input:

100 4
2 3 5 7
20 2
4 6
100 6
2 5 8 30 101 7
2100000000 10
12345 54123 23425 20000 12312 22222 1234 2021 111111 12344321
2147483647 3
2147483647 2 128

Output:

22
13
34
2096573927
1073741823

If the above test cases are not enough, you can make your own test case for smaller input range (<1000000) and using ceiv approach you can get the correct solution. Good luck.

[ask_1171]

using sieve approach im getting tle.. can any one give me a good algo to do it..

#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;

#define MAX 2147483647

unsigned mark[(MAX>>5)+2];

#define checkp(x,n) (x[n>>5]&(1<<(n&31)))
#define setp(x,n) (x[n>>5]|=(1<<(n&31)))
#define resetp(x,n) (x[n>>5]&=~(1<<(n&31)))

int ar[20];
int p;
int n,m;



void sieve()
{

int i,j,k;
p=0;

memset(mark,0,(m/32)*sizeof(unsigned)+2);

for(i=1;i<=m;i++)
for(j=ar,k=ar;j<=n&&j>0;j=j+k)
if(!checkp(mark,j))
{
setp(mark,j);
p++;
}





}




int main()
{

int i;
freopen("1.txt","r",stdin);

while(scanf("%d %d",&n,&m)==2)
{

for(i=1;i<=m;i++)
scanf("%d",&ar);

sieve();

printf("%d\n",n-p);



}


return 0;
}

[matrix2220]

Hint:

You are given N and M and you have M selected tickets numbered
Tickets from 1 to N should not be divisible by any of the selected tickets
for example if we have a, b, c, ... selected tickets
then any ticket that is divisible by a or b or c or .... or LCM(a,b) or LCM(a,c) or ..... or LCM(a,b,c)

Lets Assume N = 10 and M = 2
Selected = 2 3
Then our numbers from 1 to N should not be divisible by
2
3
LCM(2,3) = 6
Lets see what number those selected numbers divides
List-----------1 2 3 4 5 6 7 8 9 10
Divisible by:---2 2 2 2 2----------------We will exclude(2,4,6,8,10)
Divisible by:-----3 3 3-------------------We will exclude(3,6,9)
Divisible by:----------- 6-----------------------We will exclude(6)
Notice that we excluded "6" 3 times, we need to solve this problem

The solution for that is to determine the size of set of the selected number {2,3}
LCM(2,3) is the LCM of the set {2,3} the size = 2 which is even then we should subtract N/LCM(2,3) from
forbidden count, in case of LCM(2,3) = 6 >>> N/LCM(2,3) = 1 which is what we want to subtract.
In case of the size of the set is odd, we need to add N/LCM(a) to the forbidden count, if set is {2}
then it's size is 1 which is odd then add N/LCM(1,2) to the forbidden count.
The reason for that is, if you have an even set then the product of it's numbers is excluded previously
more than once, so we need to subtract it to avoid redundant so that we excluded it those numbers only once.