## 10325 - The Lottery

Moderator: Board moderators

20571KJ
New poster
Posts: 7
Joined: Sat Jul 13, 2002 6:15 pm
Contact:

### 10325 - The Lottery

I had a solution but it's too slow.
Thank you.

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
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
New poster
Posts: 7
Joined: Sat Jul 13, 2002 6:15 pm
Contact:

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
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);
for i := 1 to n do read(s);
writeln(Max - F(S, n, Max));
close(input); close(output);
end.[/pascal]

20571KJ
New poster
Posts: 7
Joined: Sat Jul 13, 2002 6:15 pm
Contact:

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
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);
for i := 1 to n do read(s);
writeln(Max - F(S, n, Max));
close(input); close(output);
end.[/pascal]

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am
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
New poster
Posts: 7
Joined: Sat Jul 13, 2002 6:15 pm
Contact:
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
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
for i := 1 to n do read(s);
writeln(Max - F(S, n, Max));
end;
end.
[/pascal]

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
New poster
Posts: 5
Joined: Tue Aug 20, 2002 7:27 am

### 10325 Lottery - W.A.

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?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
It is probably the same mistake I did during contest.
Try this input:
20 2
4 6
Output:
13

tokei
New poster
Posts: 5
Joined: Tue Aug 20, 2002 7:27 am
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,used,num;
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;
l = save;
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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

### 10325 why WA !!!

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
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
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
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am

### Test these

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. New poster
Posts: 3
Joined: Wed Aug 04, 2010 1:17 pm

### Re: 10325 - The Lottery

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;
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
New poster
Posts: 9
Joined: Mon Jul 07, 2014 3:37 pm
Contact:

### Re: 10325 - The Lottery

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.
Abdelrahman Ali (MaTrix)