Programming Camp 2020 Session 3: Graph Theory

0

Programming Camp 2020 Session 2: Number Theory and Inclusion-Exclusion Part 2

1

 

ICPC 2019 Preli: G – Pairs Forming GCD

0

Problem Link: https://algo.codemarshal.org/contests/icpc-dhaka-19-preli/problems/G

Solution Idea:

  • We have to find maximum G such that there exist at least P pairs of integers (X, Y), where 1 ≤ X ≤ Y ≤ N and GCD(X, Y) = G.
  • At first, let’s try to solve a subproblem where G=1. Can we calculate the number of pairs (X, Y) where 1 ≤ X ≤ Y ≤ N and GCD(X, Y) = 1?
  • As we know Euler totient or Phi function gives us a number of X which are coprime with Y. So Phi(Y) = number of X such that GCD(X,Y) = 1.
  • So Phi(1)+Phi(2)+Phi(3)+…….+Phi(N) = number of pair (X,Y) where 1 ≤ X ≤ Y ≤ N and GCD(X, Y) = 1.
  • Now if GCD(X,Y) = 1 then GCD(GX,GY) = G.
  • So we can pre-calculate Euler totient for 1 to N and then calculate the cumulative sum of this phi[] array and store it to phiSum[] array.
  • After this, we just have to binary search for the maximum answer on the new phiSum[] array.

#include <bits/stdc++.h>

using namespace std;

#define mx 10000007
int phi[mx];
long long phiSum[mx];

void euler_totient() {
    for(int i=0; i<mx; i++) phi[i]=i;
    for(int i=2; i<mx; i++) {
        if(phi[i]==i) {
            for(int j=i; j<mx; j+=i)
                phi[j]-=(phi[j]/i);
        }
    }
}

int solve(int n, long long p) {
    int lo=1,hi=n;
    int ret=-1;
    while(lo<=hi) {
        int mid=(lo+hi)/2;
        if(phiSum[mid]>=p) {
            ret=mid;
            hi=mid-1;
        } else {
            lo=mid+1;
        }
    }
    return ret;
}

int main() {

    euler_totient();
    for(int i=1; i<mx; i++) phiSum[i]+=phiSum[i-1]+phi[i]; //cumulative sum

    int t;
    scanf("%d",&t);
    for(int z=1; z<=t; z++) {
        long long n,p;
        scanf("%lld %lld",&n,&p);
        int ans=solve(n,p);
        printf("Case %d: ",z);
        if(ans!=-1)
            ans=n/ans;
        printf("%d\n",ans);
    }
    return 0;
}

Programming Camp 2020 Session 1: Number Theory and Inclusion-Exclusion Part 1

4

Camp Video:

Handbook for Sports Programmers(Beginner)

6

I have organized this document to boost up the beginners. Most of the contents of this document are collected from various posts on the internet.

 

CF: 546-D2-E-Soldier and Traveling

0
Problem Link: http://codeforces.com/contest/546/problem/E
Solution Idea:

  • We can solve this problem by using maxflow. So at first make a source
  • Make the first group of vertices consisting of n vertices, each of them for one city.
  • Connect a source with ith vertex in the first group with an edge that has capacity ai.
  • Make a sink and second group of vertices in the same way, but use bi except for ai.
  • If there is a road between cities i and j or i = j. Make two edges, first should be connecting ith vertex from the first group, and jth vertex from the second group, and has infinity capacity. The second should be similar but connect jth from the first group and ith from the second group.
  • Then find a maxflow, in any complexity.
  • If maxflow is equal to the sum of ai and is equal to the sum of bi, then there exists an answer. How can we get it? We just have to check how many units are we pushing through edge connecting two vertices from different groups.

Using Dinitz Maxflow

Using Ford Fulkerson Maxflow

SPOJ: MKTHNUM – K-th Number

0

Problem Link: https://www.spoj.com/problems/MKTHNUM/

Solution Idea: (Merge Sort Tree)

    • At first, take input and store the input in a pair array where the first element of the ith pair is the value ai and the second element of the ith pair is i.
    • Sort the pair array with ascending order of ai
    • Build a merge sort tree using the second element of each pair of sorted pair array.
    • Now for each query i,j,k at first check how many numbers in range i to j inclusive are present in the left subtree of the current node in merge sort tree. Let the value is x. So if x<=k then it’s sure that the answer is in the left subtree. So we will go to the left subtree of the current node with k. Otherwise, we will go to right subtree of the current node with k-x;
    • In this manner when we reach a leaf node we can say that this node contains the index of our answer.

 


Light OJ: 1144 – Ray Gun

0
Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1144
Solution Idea:

    • There are many observations to make in order to get to a working solution.
    • For every lattice point (i, j), the ray that intersects it is unique and it’s identified by the pair , where g is the gcd of i and j.
    • The problem is now reduced to counting the number of irreducible fractions such that a ≤ N and b ≤ M. This is the same as counting for every i between 1 and N, the amount of numbers in the range [1, M] that are coprime with i.
    • Consider a certain number x with prime factors p1, p2. How do we know how many numbers in range [1, M] are coprime with it? That’s equal to M minus the amount of multiples of p1 minus the amount of multiples of p2 plus the amount of multiples of p1 * p2. This is inclusion-exclusion, and in general, if the amount of elements is even, we add, otherwise, we subtract.
    • So now we have a working (but slow) solution: Iterate over every i in the range [1, N] and for every i, factorize it, try out all combinations of primes and then, for every combination that results in a number k, add if the amount of primes is even or subtract if the amount of primes is odd.
    • The previous approach is very slow for two reasons: You’ll be factorizing each number every time and you’ll be doing a lot of repeated work. Every combination of primes you try out at each step will result in a certain number k. A crucial observation is that the higher exponent of that number k will be 1, because we’re trying combinations of different primes. Another crucial observation is that this number k will be seen times in total. Finally, each time we see it, it will contribute by to the final answer (or if the amount of primes is odd).
    • Knowing all this, we can precalculate a lot of stuff and then solve each test case in O(N). We should precalculate the amount of prime factors of every number in the range [1, 106] (this can be done with a simple sieve), and we should cross out numbers that have some prime with an exponent higher than 1 (in other words, multiples of some square). Once we have precalculated all that, we simply iterate from 1 to N and for every number x that we didn’t cross out, we add (or subtract) to our answer.
    • Final observations: We should add 2 to our answer (the two borders). If N = 0, the answer is 1, except M = 0 too, in which case the answer is 0.

(This solution idea is from this link )


SPOJ: GSS2 – Can you answer these queries II

0

Problem Link : http://www.spoj.com/problems/GSS2/

Solution Idea:

    Hint : https://www.quora.com/How-can-the-SPOJ-problem-GSS2-be-solved/answer/Brian-Bi?srid=29u8


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#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)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.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 stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(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 LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------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));}
/*------------------------------------------------*/

#define mx 100005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2


int ara[mx+5];
int last[2*mx+5];
ll ans[mx+5];

struct data
{
    int l,r,id;
};

vector<data>queries;

struct data1
{
    ll sum,lazy,best_lazy,ans;
    data1()
    {
        sum=lazy=best_lazy=ans=0;
    }
};

data1 tree[3*mx];

void push_down(data1 &cur, data1 &lft, data1 &rgt)
{
//    if(cur.lazy || cur.best_lazy)
//    {
        lft.best_lazy=max(lft.best_lazy,lft.lazy+cur.best_lazy);
        lft.lazy+=cur.lazy;
        lft.ans=max(lft.ans,lft.sum+cur.best_lazy);
        lft.sum=lft.sum+cur.lazy;
        rgt.best_lazy=max(rgt.best_lazy,rgt.lazy+cur.best_lazy);
        rgt.lazy+=cur.lazy;
        rgt.ans=max(rgt.ans,rgt.sum+cur.best_lazy);
        rgt.sum+=cur.lazy;
        cur.lazy=cur.best_lazy=0;
//    }
}

void push_up(data1 &cur, data1 &lft, data1 &rgt)
{
    cur.ans=max(lft.ans,rgt.ans);
    cur.sum=max(lft.sum,rgt.sum);
}


void update(int n, int b, int e, int i, int j, ll val)
{
    if(b>j || e<i) return;
    if(b>=i && e<=j)
    {
        tree[n].best_lazy=max(tree[n].best_lazy,tree[n].lazy+val);
        tree[n].lazy+=val;
        tree[n].ans=max(tree[n].ans,tree[n].sum+val);
        tree[n].sum+=val;
        return;
    }
    segment_tree;
    push_down(tree[n],tree[l],tree[r]);
    update(l,b,mid,i,j,val);
    update(r,mid+1,e,i,j,val);
    push_up(tree[n],tree[l],tree[r]);
}

data1 query(int n, int b, int e, int i, int j)
{
    if(b>j || e<i) return data1();
    if(b>=i && e<=j)
    {
        return tree[n];
    }
    segment_tree;
    push_down(tree[n],tree[l],tree[r]);
    data1 p=query(l,b,mid,i,j);
    data1 q=query(r,mid+1,e,i,j);
    data1 ret;
    push_up(ret,p,q);
    return ret;
}


int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);
    int n;
    sf(n);
    for(int i=1; i<=n; i++) sf(ara[i]);
    int m;
    sf(m);
    data a;
    for(int i=0; i<m; i++)
    {
        sff(a.l,a.r);
        a.id=i;
        queries.pb(a);
    }

    sort(all(queries),[](data a,data b)
    {
        return a.r<b.r;
    });

    int idx=0;
    for(int i=1; i<=n && idx<SZ(queries); i++)
    {
//        if(last[mx+ara[i]]!=0)
//        {
//            update(1,1,n,last[mx+ara[i]],0);
//        }
        int xx=last[mx+ara[i]]+1;
        update(1,1,n,xx,i,ara[i]);
        last[mx+ara[i]]=i;
        while(idx<SZ(queries) && queries[idx].r==i)
        {
            ans[queries[idx].id]=query(1,1,n,queries[idx].l,queries[idx].r).ans;
            idx++;
        }
    }

    for(int i=0; i<m; i++)
        printf("%lld\n",ans[i]);



    return 0;
}


SPOJ: CERC07S – Robotic Sort

0

Problem Link : http://www.spoj.com/problems/CERC07S/

Solution Idea:



#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#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)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.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 stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(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 LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------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));}
/*------------------------------------------------*/


/*-------------------------Treap Start------------------------*/
struct node
{
    int prior,size;
    pii val;//value stored in the array
    pii mini;//whatever info you want to maintain in segtree for each node
    int lazy;//whatever lazy update you want to do
    int id;
    struct node *l,*r;
};

typedef node* pnode;

int sz(pnode t)
{
    return t?t->size:0;
}

void upd_sz(pnode t)
{
    if(t)t->size=sz(t->l)+1+sz(t->r);
}

void lazy(pnode t)
{
    if(!t || !t->lazy)return;
//    t->val+=t->lazy;//operation of lazy
//    t->mini+=t->lazy*sz(t);
    swap(t->l,t->r);
    if(t->l)t->l->lazy^=t->lazy;//propagate lazy
    if(t->r)t->r->lazy^=t->lazy;
    t->lazy=0;
}

void reset(pnode t)
{
    if(t)t->mini = t->val;//no need to reset lazy coz when we call this lazy would itself be propagated
}

void combine(pnode& t,pnode l,pnode r) //combining two ranges of segtree
{
    if(!l || !r)return void(t = l?l:r);
    t->mini = min(l->mini, r->mini);
}

void operation(pnode t) //operation of segtree
{
    if(!t)return;
    reset(t);//reset the value of current node assuming it now represents a single element of the array
    lazy(t->l);
    lazy(t->r);//imp:propagate lazy before combining t->l,t->r;
    combine(t,t->l,t);
    combine(t,t,t->r);
}

void split(pnode t,pnode &l,pnode &r,int pos,int add=0)
{
    if(!t)return void(l=r=NULL);
    lazy(t);
    int curr_pos = add + sz(t->l);
    if(curr_pos<=pos)//element at pos goes to left subtree(l)
        split(t->r,t->r,r,pos,curr_pos+1),l=t;
    else
        split(t->l,l,t->l,pos,add),r=t;
    upd_sz(t);
    operation(t);
}

int find_min(pnode t, int add=0)
{
    lazy(t);
    int cur_pos=sz(t->l)+add;
    if(t->r && t->r->mini==t->mini) return find_min(t->r,cur_pos+1);
    if(t->l && t->l->mini==t->mini) return find_min(t->l,add);
    return cur_pos;
}

void merge(pnode &t,pnode l,pnode r)  //l->leftarray,r->rightarray,t->resulting array
{
    lazy(l);
    lazy(r);
    if(!l || !r) t = l?l:r;
    else if(l->prior>r->prior)merge(l->r,l->r,r),t=l;
    else    merge(r->l,l,r->l),t=r;
    upd_sz(t);
    operation(t);
}

pnode init(int val, int id)
{
    pnode ret = (pnode)malloc(sizeof(node));
    ret->prior=rand();
    ret->size=1;
    ret->val=pii(val,id);
    ret->mini=pii(val,id);
    ret->lazy=0;
    ret->l=ret->r=NULL;
    return ret;
}

//int range_query(pnode t,int l,int r) //[l,r]
//{
//    pnode L,mid,R;
//    split(t,L,mid,l-1);
//    split(mid,t,R,r-l);//note: r-l!!
//    int ans = t->mini;
//    merge(mid,L,t);
//    merge(t,mid,R);
//    return ans;
//}

//void range_update(pnode t,int l,int r,int val) //[l,r]
//{
//    pnode L,mid,R;
//    split(t,L,mid,l-1);
//    split(mid,t,R,r-l);//note: r-l!!
//    t->lazy+=val; //lazy_update
//    merge(mid,L,t);
//    merge(t,mid,R);
//}

//void split(pnode t,pnode &l,pnode &r,int key)
//{
//    if(!t) l=r=NULL;
//    else if(t->val<=key) split(t->r,t->r,r,key),l=t; //elem=key comes in l
//    else split(t->l,l,t->l,key),r=t;
//    upd_sz(t);
//}
//
//void insert(pnode &t,pnode it)
//{
//    if(!t) t=it;
//    else if(it->prior>t->prior) split(t,it->l,it->r,it->val),t=it;
//    else insert(t->val<=it->val?t->r:t->l,it);
//    upd_sz(t);
//}
//
//void erase(pnode &t,int key)
//{
//    if(!t)return;
//    else if(t->val==key)
//    {
//        pnode temp=t;
//        merge(t,t->l,t->r);
//        free(temp);
//    }
//    else erase(t->val<key?t->r:t->l,key);
//    upd_sz(t);
//}

void output(pnode t)
{
    if(!t) return;
    output(t->l);
    printf("%d ",t->val);
    output(t->r);
}

void clear_tree(pnode t)
{
    if(!t) return;
    clear_tree(t->l);
    clear_tree(t->r);
    free(t);
}

/*-------------------------Treap End--------------------------*/


int main()
{

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

    int n;
    while(sf(n) && n)
    {
        pnode root=NULL;
        for(int i=0; i<n; i++)
        {
            int a;
            sf(a);
            merge(root,root,init(a,i+1));
        }
        vector<int>ans;
        while(n)
        {
            int k=find_min(root);
            pnode l,r;
            split(root,l,r,k-1);
            split(r,root,r,0);
            if(l)
                l->lazy=1;
            merge(root,l,r);
            n--;
            ans.pb(SZ(ans)+k+1);
        }

        for(int i=0; i<SZ(ans); i++)
        {
            printf("%d",ans[i]);
            if(i!=SZ(ans)-1)
                printf(" ");
        }
        printf("\n");
//        clear_tree(root);

    }

    return 0;
}