Page 1 of 1

10325 - The Lottery

Posted: Sat Jul 13, 2002 6:31 pm
by 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.

Posted: Sun Jul 14, 2002 2:52 pm
by 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!

WA...help me please !!!!!

Posted: Sun Jul 14, 2002 6:32 pm
by 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]

WA...help me please !!!!!

Posted: Sun Jul 14, 2002 6:33 pm
by 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]

Posted: Tue Jul 16, 2002 9:37 pm
by 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).

Posted: Wed Jul 17, 2002 4:41 am
by 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]

Posted: Wed Jul 17, 2002 9:47 am
by 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.

10325 Lottery - W.A.

Posted: Tue Aug 20, 2002 7:33 am
by 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.

Posted: Tue Aug 20, 2002 12:21 pm
by Adrian Kuegel
It is probably the same mistake I did during contest.
Try this input:
20 2
4 6
Output:
13

Posted: Tue Aug 20, 2002 8:14 pm
by 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]

10325 why WA !!!

Posted: Fri May 09, 2003 2:36 am
by 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]

Posted: Mon Apr 05, 2004 12:11 am
by 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

Test these

Posted: Mon Mar 28, 2005 11:56 am
by 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. :lol:

Re: 10325 - The Lottery

Posted: Wed Nov 24, 2010 1:20 am
by 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;
}

Re: 10325 - The Lottery

Posted: Mon Sep 08, 2014 5:11 pm
by 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.