Lightoj Problem-Sum of Consecutive Integers

Problem Link: Here

Explanation:
Let, k be the number of consecutive integers starting
from x whose sum equals N.So we can write,
x+(x+1)+……..+(x+k-1)=N ——–(1)
or, kx+k*(k-1)/2=N
or, 2kx+k^2-k=2N
or, k(2x+k-1)=2N ———-(2)
From equation (2) we can say, k is a divisor of 2N.
Now, from (2)
k(2x+k-1)=2N
or, 2x+k-1=2N/k
or, 2x+k-1=R [Let R=2N/k]
or, 2x=(R-k)+1 ————(3)
From, equation (3) we can say, (R-k) has to be odd number.
Again, since R=2N/k and 2N is even, so R is always even and hence
k must be odd to be (R-k) odd.

From the requirement of problem, x must be positive integers,
so from equation (3) we can write,
R>=k
or, 2N/k>=k
or, 2N>=k^2
or, k<=sqrt(2N) ————(4)

From the above explanation, we can say,
1) k must be a divisor of 2N
2) k must be odd
3) k is less than or equals to the sqaure-root of 2N.

Code

/*
    Problem Tags: Number Theory
    Explanation: Let, k be the number of consecutive integers starting
                from x whose sum equals N.So we can write,
                x+(x+1)+........+(x+k-1)=N --------(1)
                or, kx+k*(k-1)/2=N
                or, 2kx+k^2-k=2N
                or, k(2x+k-1)=2N ----------(2)
                From equation (2) we can say, k is a divisor of 2N.
                Now, from (2)
                k(2x+k-1)=2N
                or, 2x+k-1=2N/k
                or, 2x+k-1=R  [Let R=2N/k]
                or, 2x=(R-k)+1 ------------(3)
                From, equation (3) we can say, (R-k) has to be odd number.
                Again, since R=2N/k and 2N is even, so R is always even and hence
                k must be odd to be (R-k) odd.

                From the requirement of problem, x must be positive integers,
                so from equation (3) we can write,
                R>=k
                or, 2N/k>=k
                or, 2N>=k^2
                or, k<=sqrt(2N) ------------(4)

                From the above explanation, we can say,
                1) k must be a divisor of 2N
                2) k must be odd
                3) k is less than or equals to the sqaure-root of 2N.
*/

#include<bits/stdc++.h>
using namespace std;
#define LL long long

bool a[10000009];
int p[500009];
void sieve()
{
    LL i,j,k=0; a[0]=1; a[1]=1; p[0]=2;
    for(i=3;i<=10000006;i=i+2)
    {
        if(a[i]==0)
        {
            p[++k]=i;
            for(j=i*i;j<=10000006;j=j+2*i)
                a[j]=1;
        }
    }
}


int main()
{
    LL i,j,k,n,m,d,test,t=0;
    sieve();
    scanf("%lld",&test);
    while(test--)
    {
        scanf("%lld",&n);
        LL sq=sqrt(n);
        while(n%2==0) n=n/2;
        LL ans=1;
        for(i=1;p[i]<=sq;i++)
        {
            if(n%p[i]==0)
            {
                LL co=0;
                while(n%p[i]==0)
                {
                    co++;
                    n=n/p[i];
                }
                ans=ans*(co+1);
            }
            sq=sqrt(n);
        }
        if(n!=1) ans=ans*2;
        printf("Case %lld: %lld\n",++t,ans-1);
    }
    return 0;
}

Posted in Lightoj, Math, Number Theory

SPOJ Inversion Count

Problem Summary:

Let A[0…n – 1] be an array of n distinct positive integers. If i A[j] then the pair (i, j) is called an inversion of A. Given n and an array A your task is to find the number of inversions of A.

Full Problem Description is here.

A Very Nice Analysis is Here

Merge Sort Solution


/*
Algorithm: Solution with Merge Sort. This problem can also be solved
            with BST and BIT.
*/
 
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL a[200009];
LL ans=0;
void Merge(LL left_begin,LL left_end,LL right_begin,LL right_end)
{
    LL pos=0,pp=left_begin;
    LL temp[right_end-left_begin+3];
    while(left_begin<=left_end&&right_begin<=right_end)
    {
        if(a[left_begin]<=a[right_begin])
            temp[pos++]=a[left_begin++];
        else
        {
            ans=ans+(left_end-left_begin+1);
            temp[pos++]=a[right_begin++];
        }
    }
    while(left_begin<=left_end) temp[pos++]=a[left_begin++];
    while(right_begin<=right_end) temp[pos++]=a[right_begin++];
    for(LL i=0;i<pos;i++)
        a[pp+i]=temp[i];
    return;
}
 
void MergeSort(LL left,LL right)
{
    LL mid=(left+right)>>1;
    if(left<right)
    {
        MergeSort(left,mid);
        MergeSort(mid+1,right);
        Merge(left,mid,mid+1,right);
    }
}
 
int main()
{
    LL i,j,k,n,m,d,test,t=0;
    scanf("%lld",&test);
    while(test--)
    {
        ans=0;
        scanf("%lld",&n);
        for(i=0;i<n;i++)
            scanf("%lld",&a[i]);
        MergeSort(0,n-1);
        printf("%lld\n",ans);
    }
    return 0;
}

BIT Solution

/*
Algorithm: Binary Indexed Tree
*/
 
#include<bits/stdc++.h>
using namespace std;
#define LL long long
 
LL a[200009];
LL b[200009];
LL tree[200009];
LL n;
 
void update(LL idx,LL val)
{
    while(idx<=n)
    {
        tree[idx]+=val;
        idx+=idx&-idx;
    }
}
 
LL query(LL idx)
{
    LL ret=0;
    while(idx>0)
    {
        ret+=tree[idx];
        idx-=idx&-idx;
    }
    return ret;
}
 
int main()
{
    LL i,j,k,m,d,test,t=0;
    scanf("%lld",&test);
    while(test--)
    {
        scanf("%lld",&n);
        memset(tree,0,sizeof(tree));
        for(i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            b[i]=a[i];
        }
        sort(b,b+n);
        for(i=0;i<n;i++)
        {
            d=lower_bound(b,b+n,a[i])-b;
            a[i]=d+1;
        }
        LL ans=0;
        for(i=n-1;i>=0;i--)
        {
            ans=ans+query(a[i]-1);
            update(a[i],1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
 

This Problem UVA-10810 – Ultra-QuickSort can also be solved with these above two solutions.

Posted in Binary Indexed Tree, SPOJ, UVA

Nim

Proof of the winning formula

The soundness of the optimal strategy described above was demonstrated by C. Bouton.

Theorem. In a normal Nim game, the player making the first move has a winning strategy if and only if the nim-sum of the sizes of the heaps is nonzero. Otherwise, the second player has a winning strategy.

Proof: Notice that the nim-sum (⊕) obeys the usual associative and commutative laws of addition (+), and also satisfies an additional property, x ⊕ x = 0 (technically speaking, the nonnegative integers under ⊕ form an Abelian group of exponent 2).

Let x1, …, xn be the sizes of the heaps before a move, and y1, …, yn the corresponding sizes after a move. Let s = x1 ⊕ … ⊕ xn and t = y1 ⊕ … ⊕ yn. If the move was in heap k, we have xi = yi for all i ≠ k, and xk > yk. By the properties of ⊕ mentioned above, we have

    t = 0 ⊕ t
      = sst
      = s ⊕ (x1 ⊕ ... ⊕ xn) ⊕ (y1 ⊕ ... ⊕ yn)
      = s ⊕ (x1y1) ⊕ ... ⊕ (xnyn)
      = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (xkyk) ⊕ 0 ⊕ ... ⊕ 0
      = sxkyk
 
(*) t = sxkyk.

The theorem follows by induction on the length of the game from these two lemmas.

Lemma 1. If s = 0, then t ≠ 0 no matter what move is made.

Proof: If there is no possible move, then the lemma is vacuously true (and the first player loses the normal play game by definition). Otherwise, any move in heap k will produce t = xk ⊕ yk from (*). This number is nonzero, since xk ≠ yk.

Lemma 2. If s ≠ 0, it is possible to make a move so that t = 0.

Proof: Let d be the position of the leftmost (most significant) nonzero bit in the binary representation of s, and choose k such that the dth bit of xk is also nonzero. (Such a k must exist, since otherwise the dth bit of s would be 0.) Then letting yk = s ⊕ xk, we claim that yk < xk: all bits to the left of d are the same in xk and yk, bit d decreases from 1 to 0 (decreasing the value by 2d), and any change in the remaining bits will amount to at most 2d−1. The first player can thus make a move by taking xk − yk objects from heap k, then

t = sxkyk           (by (*))
  = sxk ⊕ (sxk)
  = 0.

The modification for misère play is demonstrated by noting that the modification first arises in a position that has only one heap of size 2 or more. Notice that in such a position s ≠ 0, therefore this situation has to arise when it is the turn of the player following the winning strategy. The normal play strategy is for the player to reduce this to size 0 or 1, leaving an even number of heaps with size 1, and the misère strategy is to do the opposite. From that point on, all moves are forced.

Useful Links:

1)Wikipedia
2)On a Blog

Posted in Game Theory

SRM-613(Div-2) 1000

Problem Statement

Solution Analysis

Code:

#include<bits/stdc++.h>

using namespace std;
#define LL long long

vector<int>ff,ss;
LL n,k;

LL dp[59][1050][45];

LL f(LL i,LL mask,LL r)
{
    if(dp[i][mask][r]!=-1) return dp[i][mask][r];
    if(i==n)
    {
        LL p=__builtin_popcount(mask);
        if(p+r<=k) return 1;
        else return 0;
    }
    // not using i-th card
    LL res=f(i+1,mask,r);
    // using i-th card
    LL nmask=mask;
    LL nr=r;
    if(ff[i]>10) nr++;
    else nmask=nmask|(1<<(ff[i]-1));
    nmask=nmask|(1<<(ss[i]-1));
    res=res+f(i+1,nmask,nr);
    return dp[i][mask][r]=res;
}


class TaroCards
{
public:
	long long getNumber(vector <int> first, vector <int> second, int K)
	{
	    ff=first;
	    ss=second;
	    k=K;
	    n=ff.size();
	    memset(dp,-1,sizeof(dp));
	    return f(0,0,0);
	}
};

Posted in Favorite Problems, TopCoder

An Easy DP Problem-2 with Bitmask

Given N integers. Let Total subsets T=2N. How many subsets are available from T where the distinct integers are less than or equal to K.

Sample Input:

4 2 (N,K)

1 2 3 4(A[i])

Sample Output:

11

Sample Input:

4 2 (N,K)

5 5 5 5(A[i])

Sample Output:

16

Related Problem

Solution:

#include<bits/stdc++.h>
using namespace std;
#define LL long long

LL dp[59][1055];
LL a[59],n,k;

LL f(LL i,LL mask)
{
    if(dp[i][mask]!=-1) return dp[i][mask];
    if(i==n)
    {
        LL p=__builtin_popcount(mask);
        if(p<=k) return 1;
        else return 0;
    }
    LL res=f(i+1,mask); //not using i-th integer
    LL nmask=mask;
    nmask=nmask|(1<<a[i]);
    res=res+f(i+1,nmask); //using i-th integer
    return dp[i][mask]=res;
}


int main()
{
    LL i,j,m,d;
    while(cin>>n>>k)
    {
        memset(dp,-1,sizeof(dp));
        for(i=0;i<n;i++)
            cin>>a[i];
        LL ans=f(0,0);
        cout<<ans<<endl;
    }
    return 0;
}

Posted in Dynamic Programming

Project Euler 16

What is the sum of the digits of the number 2^1000?

//the sum of digits for b^p, in this problem b=2,p=1000
//https://projecteuler.net/problem=16

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int digit[4000];

int main()
{
    int i,j,k,n,m,d,b,p;
    while(cin>>b>>p)
    {
        n=(int)(p*ceil(log(b))); //number of digit in b^p
        memset(digit,0,sizeof(digit));
        digit[0]=1;
        for(i=0;i<p;i++)
        {
            int carry=0;
            for(j=0;j<n;j++)
            {
                int num=digit[j]*b+carry;
                digit[j]=num%10;
                carry=num/10;
            }
        }
        int sum=0;
        for(i=0;i<n;i++)
            sum=sum+digit[i];
        cout<<sum<<endl;
    }
    return 0;
}
Posted in Number Theory, Project Euler

An Easy DP Problem-1

You are given an array a[] of length N. You have to output P such that

p=summation of some array elements. An condition must be hold that is
if you choose the i-th element of the array, then you mustn’t choose the i+1 and i-1 th element. That is you choose the i-th element, then you must not choose the neighbor element of the array.

Sample Input:
7
1 7 2 9 4 6 13
10
1 2 3 4 5 1 2 3 4 5
Sample Output:
29
17

Code:

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int a[100];
int dp[100];
int n;
int f(int pos)
{
    if(dp[pos]) return dp[pos];
    if(pos==n-1) return dp[pos]=a[n-1];
    if(pos>n-1) return dp[pos]=0;
    int p1=a[pos]+f(pos+2); //pos-th nibo
    int p2=f(pos+1);        //pos-th nibo na
    return dp[pos]=max(p1,p2);
}

int main()
{
    int i,j,k,m,d;
    while(cin>>n)
    {
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
            cin>>a[i];
        cout<<f(0)<<endl;
    }
    return 0;
}

Now if an condition is added, that is, first element is neighbor to last element, then, an state is also added which is

int f(int pos,bool first)
pos=position of the array element.
first= 1, if first element is taken
0, if first element is not taken

Code:

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int a[100];
int dp[100][100];
int n;
int f(int pos,bool first)
{
    if(dp[pos][first]) return dp[pos][first];
    if(pos==n-1&&first==0) return dp[pos][first]=a[n-1];
    if(pos==n-1&&first==1) return dp[pos][first]=0;
    if(pos>n-1) return dp[pos][first]=0;
    int p1,p2;
    if(pos==0)
    {
        p1=a[pos]+f(pos+2,1);
        p2=f(pos+1,0);
    }
    else
    {
        if(first==0)
        {
            p1=a[pos]+f(pos+2,0);
            p2=f(pos+1,0);
        }
        else
        {
            p1=a[pos]+f(pos+2,1);
            p2=f(pos+1,1);
        }
    }
    return dp[pos][first]=max(p1,p2);
}
int main()
{
    int i,j,k,m,d;
    while(cin>>n)
    {
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
            cin>>a[i];
        cout<<f(0,0)<<endl;
    }
    return 0;
}
Tagged with:
Posted in Dynamic Programming
Blog Stats
Recent Posts
Recent Comments
Larry Page on An Easy DP Problem-2 with…
Anonymous on An Easy DP Problem-2 with…
Kaiser on An Easy DP Problem-1
Categories
Archives

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 9 other followers