11159 - Factors and Multiples

[sh415]

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]

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

[sh415]

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]

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]

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[110], right[110], setA[110], setB[110];
bool flag[110];

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;
}