UVa 10616 – Divisible Group Sums

1

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1557

Solution Idea:

This is a knapsack problem where the given numbers are objects. we have to count how many set is there of size m whose sum is divisible by d.

Now here we have a three state dp. where idx indicates the current index of objects, cnt indicates how many objects we have taken till now and we can’t take more than m element and this is a base case. and 3rd parameter is sum, which indicates the sum of the objects we have taken till now.

Now the sum can be very large and we can’t store the original sum in our dp array because we can’t declare such large array. So we can store the (sum%d) in the array because (sum%d) < 20  so we can easily store that. so in every step we have two call one is by taking current object and another is without taking that object. and the base case is when we have taken m elements then the sum value is either 0 or not. if it is a zero then we can say that it is divisible by d.

Now the most tricky part in this problem is the numbers can be negative and we have to consider how to mod the negative numbers. Lets see a example-

-12 % 7 = ??

If we calculate through computer or calculator the output will be -5. but is this correct??

Normally a%b = (a-x)

Where x is the greatest element which is divisible by b and which is less than or equal to a.

So we can say that x%b==0 and x<=a.

Now lets find the number x for -12 . we can see that -14 is the greatest element which is divisible by 7 and which is less than or equal to -12.

So the correct ans for -12%7 = (-12-(-14))= -12+14=2 😛

We can calculate the modulus result easily in this way.

if the operation is a%b and a<0. then the correct modulus value will be (a%b)+b.

-12%7= (-12%7)+7=-5+7=2 😀

So in this problem we have to consider the modulus of negative numbers.


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int n, q,d,m;
int ara[300];
ll dp[210][11][22];

ll func(int idx, int cnt, int sum)
{

    if(cnt==m)
    {
        if(sum==0) return 1;
        return 0;
    }
    if(idx>=n) return 0;

    ll &ret=dp[idx][cnt][sum];

    if(ret!=-1) return ret;


    ll xx=0,yy=0;

    ll temp=sum+ara[idx];
    temp%=d;
    if(temp<0) temp+=d;

    xx=func(idx+1,cnt+1,temp);

    yy=func(idx+1,cnt,(sum)%d);

    return ret=xx+yy;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int z=0;

    while(sff(n,q)==2 && (n && q))
    {
        z++;
        pf("SET %d:\n",z);
        loop(i,n) sf(ara[i]);
        loop(i,q)
        {

            sff(d,m);
            ms(dp,-1);
            printf("QUERY %d: %lld\n",i+1,func(0,0,0));
        }
    }

    return 0;
}

Advertisements

SPOJ SUMPRO – SUM OF PRODUCT

0

/*
User ID: tanmoy_13
Link : http://www.spoj.com/problems/SUMPRO/
*/

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define CIN ios_base::sync_with_stdio(0)
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define getint2(a,b) scanf("%d%d",&a,&b)
#define getint3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define loop(i,n) for(int i=0;i<n;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define mod 1000000007
#define I int

using namespace std;

/* Bits operation */
int Set(int n,int pos)  { return n = n | 1<<pos;}
bool check(int n,int pos) { return n & 1<<pos;}
int Reset(int n, int pos) { return n=n & ~(1<<pos);}
 /*----------------*/

 ll range_sum(ll a, ll b)
 {
     ll sa=a*(a+1)>>1;
     ll sb=b*(b+1)>>1;
     return (sa-sb)%mod;
 }

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    ll n;
    getint(t);
    TEST_CASE(t)
    {
        sc("%lld",&n);
        ll root=sqrt(n);
        ll low,up;
        ll sum=0;
        for(int i=1;i<=root;i++)
        {
            up=n/i;
            low=max(n/(i+1),root);
            sum+=(range_sum(up,low)*i)%mod;
            if(sum>=mod) sum-=mod;
            sum+=(i*(n/i))%mod;
            if(sum>=mod) sum-=mod;
        }
        pf("%lld\n",sum);
    }
    return 0;
}

Editorial for this problem :

Problem:
Given a number N, find the sum of all products x*y such that N/x = y (Integer Division).

Brute-force:
The simplest brute force solution involves iterating over all possible values of x and finding the corresponding value of y, and updating the running sum by adding x * y.

Unfortunately, this does not pass as the overall time complexity is O(T * N).

The Pattern:
If you tried to simulate the brute-force, you might observe the intriguing pattern of finding a lot of 1’s (approx N / 2) at the end.
The trick is to notice that many numbers, not only 1, are going to be repeated.
Let us consider an example of N = 10:

x = 1, y = 10
x = 2, y = 5
x = 3, y = 3
x = 4, y = 2
x = 5, y = 2
x = 6, y = 1
x = 7, y = 1
x = 8, y = 1
x = 9, y = 1
x = 10, y = 1

Observation 1: Note that not only 1, but 2 is also repeated. Rather, on simulating even bigger integers, you must notice that no more than O(sqrt(N)) distinct integers will ever occur.

Observation 2: All the repetitions will always to occuring together in a sequence such that they form an interval.

Now, we are getting closer to the solution, we can create chunks for each value of y and break our sum operation as follows:

10 * 1 + 5 * 2 + 3 * 3 + 2 * (4 + 5) + 1 * (6 + 7 + 8 + 9 + 10)

So, for each value y, if we find the lowest value of x (say, lo) and highest value of x(say, hi), we can find the entire summation in O(sqrt(N)).

I’d recommend you to go back to the problem and try to solve it with this much information only.

So as to complete the solution, we must find the way to compute values of lo and hi, for y = 1, lo = 6 and hi = 10
for y = 2, lo = 4 and hi = 5
for y = 3, lo = 3 and hi = 3

The other crucial observation is to notice that each pair of values (x,y) must have at least one value in [1, sqrt(N)].

Thus, we need not process the values of y any furthur..!!

But, aren’t we missing out on the pairs (1, 10) and (2, 5) ?

Well, these are exactly the pairs that have x * y = N, so we can compute them on-the-fly when y = 1 and y = 2. You might need to pay some attention while implementating, so as to avoid counting sqrt(N) twice and also to handle MOD correctly!!

UVa 10176 – Ocean Deep! – Make it shallow!!

0

/*
User ID: turing_13
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1117
*/

#include <bits/stdc++.h>

#define ll long long
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)

using namespace std;

int main()
{
    ///freopen("input.txt","r",stdin);
    ///freopen("output.txt","w",stdout);
    char ch;
    int num=131071, n=0;
    while((ch=getchar()) !=EOF)
    {
        if(ch=='#')
        {
            if(n==0)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
            n=0;
        }
        else
        {
            if(ch!='\n')
                n=(n*2+ch-48)%num;
        }
    }
    return 0;
}

USACO : Your Ride Is Here

0

/*
Link : http://train.usaco.org/usacoprob2?a=3rv4k6xDvNx&S=ride
*/

/*
PROG: ride
LANG: C++
*/

#include <bits/stdc++.h>

#define ll long long
#define SZ(a) a.size()

using namespace std;

int main()
{
    freopen("ride.in","r",stdin);
    freopen("ride.out","w",stdout);
    string str1,str2;
    ll a=1,b=1;
    cin>>str1>>str2;
    for(int i=0;i<SZ(str1);i++)
    {
        a=((a%47)*(str1[i]-'A'+1)%47)%47;
    }

    for(int i=0;i<SZ(str2);i++)
    {
        b=((b%47)*(str2[i]-'A'+1)%47)%47;
    }

    if(a==b)
        cout<<"GO"<<endl;
    else
        cout<<"STAY"<<endl;
    return 0;
}