11159 - Factors and Multiples

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sh415
New poster
Posts: 13
Joined: Fri Nov 13, 2009 9:31 am
Location: JU

Re:

mmonish wrote:jan >>

Thanks. I found my bugs and got AC.
i have found for which input my output is not correct ; but I cant find its solution..............

IS MY ALGORITHM OKEY::::
1: take input; if '0' is in set A ; then it will not enter in set A; if '0' is in set B then it should be eliminated from
B ;
2: if set A element has a multiple in set B ; then degree of element A and element B will increase;
3: now find the highest deg of any element; as it is highest it should be eliminated;
if it is in A[x]; then for each element in B if (B%A[x]==0 ) then deg B decrease .deg A[x]=0;
else for each element of A if B[x]%A==0 then degree A decrease'; deg B[x]=0;
thus we eliminate one element;
4. repeat if while degree of all element is not zero.

shovon

sh415
New poster
Posts: 13
Joined: Fri Nov 13, 2009 9:31 am
Location: JU

Re: 11159 - Factors and Multiples

i have found for which input my output is not correct ; but I cant find its solution..............

IS MY ALGORITHM OKEY::::
1: take input; if '0' is in set A ; then it will not enter in set A; if '0' is in set B then it should be eliminated from
B ;
2: if set A element has a multiple in set B ; then degree of element A and element B will increase;
3: now find the highest deg of any element; as it is highest it should be eliminated;
if it is in A[x]; then for each element in B if (B[i]%A[x]==0 ) then deg B[i] decrease .deg A[x]=0;
else for each element of A[i] if B[x]%A[i]==0 then degree A[i] decrease'; degree B[x]=0;
thus we eliminate one element;
4. repeat if while degree of all element is not zero.

shovon
Last edited by sh415 on Sun Oct 31, 2010 5:26 pm, edited 1 time in total.

sh415
New poster
Posts: 13
Joined: Fri Nov 13, 2009 9:31 am
Location: JU

Re: 11159 - Factors and Multiples

sh415 wrote:i have found for which input my output is not correct ; but I cant find its solution..............
shovon
for some given sample input given by StatujaLeha
I found my code has +1 or +2 diffenence is some cases...................................
but the input are so long that i cant determinte where is the problem. need your help badly.................
Any advice or solution...............

shovon

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 11159 - Factors and Multiples

Don't use ford-fulkerson/edmond-karp in its direct form to solve this problem or else you will get TLE. That's because these two are n^5. You can either use relabel to front or the algorithm explained here. Both of these are n^3.

http://www.geeksforgeeks.org/maximum-bi ... -matching/.

The later one is much easier to implement but is only valid for maximum cardinality bipartite matching. Relabel to front is n^3 and can solve any max-flow problem in general. Also remember that there can be zeros in the input. 0 is multiple of every number including 0 but no number (except for 0) is multiple of 0.

So if the input is
1
2 0 0
2 1 2

Answer will be 0.

but for input

1
2 1 2
2 0 0

answer will be 2.

Tahanima
New poster
Posts: 8
Joined: Thu Dec 25, 2014 4:50 pm

Re: 11159 - Factors and Multiples

What is wrong with my code?

Code: Select all

#include <stdio.h>
#include <map>
#include <cstring>
#include <vector>

using namespace std;
int t,l,r;
map<int, vector<int> > graph;
int left, right, setA, setB;
bool flag;

bool matching(int u){
for(int i = 0; i<graph[u].size(); i++){
int v = graph[u][i];
if(flag[v]) continue;
flag[v] = true;
if(right[v] == -1 || matching(right[v])){
right[v] = u;
left[u] = v;
return true;
}
}
return false;
}

int bip_match(){
memset(left, 0, sizeof(left));
memset(right,-1,sizeof(right));
int cnt = 0;
for(int i = 0; i<l; i++){
memset(flag, 0, sizeof(flag));
if(matching(setA[i])) cnt++;
}
return cnt;
}

int main()
{
scanf("%d",&t);
for(int i = 1; i<=t; i++){
scanf("%d", &l);
for(int j = 0; j<l; j++){
scanf("%d", &setA[j]);
}
scanf("%d", &r);
for(int j = 0; j<r; j++){
scanf("%d", &setB[j]);
}
graph.clear();

for(int j = 0; j<l; j++){
for(int k = 0; k<r; k++){
if((setA[j]!=0 && setB[k]%setA[j] == 0) || setB[k] == 0){
graph[setA[j]].push_back(setB[k]);
}
}
}
printf("Case %d: %d\n", i, bip_match());
}
return 0;
}