t3rminated's blog

By t3rminated, history, 8 years ago, In English

In this question isn't it enough to check the gcd(A,B) divisibility with each number? i am getting wrong answer!

code--

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//utility function to find the GCD of two numbers
ll gcd(ll a, ll b)
{
    return (a%b == 0)? abs(b) : gcd(b,a%b);
}
 
int main() {
	// your code goes here
	int t;
	cin >> t;
	while(t--)
	{
	    ll n, x, y;
	    cin >> n >> x >> y;
	    ll gdc = gcd(x,y);
	    ll a[n+1];
            ll c  =0;
	    for(int i = 0; i < n; i++)
	    {
	        cin >> a[i];
	        if((a[i]%gdc == 0))
	        c++;
	        
	        
	    }
	    cout << c << " " << n-c << "\n";
	    
	}
	return 0;
}

  • Vote: I like it
  • -8
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If we have an equation ax+by = c and if gcd(a,b) divides c, it means the equation will have integral solution however it doesn't state x,y will be positive, We want only positive x,y in this question. For instance 7x+5y = 2 doesn't have a solution where x,y are >= 0 whereas your code will count it as a valid cash payment.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    so what is the proposed solution?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We can formulate this question as reachability problem. Initially push 0 in the queue, each time you pop an element from the queue push, (val+a,val+b) in the queue till val+a,val+b are <= 1e5,

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but wouldn't the time complexity be too high! like for each element iterating till val+a<=100000

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          NO, we don't iterate for all val+a < 1e5 rather we incrementally see what all values can be reached.

          Spoiler
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah this looks good!

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              So it's complexity will be O(n*t*logn) because for each element we can binary search in the queue whether it's found

              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Binary Search? No, We run this as a pre-processing step and then answer in O(1) using 'ok' array.

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

the symbol ll is it for container ?