(LighOj) 1026 – Critical Links

Posted on July 15, 2015 by Hasib Al Muhaimin

//link: http://lightoj.com/volume_showproblem.php?problem=1026
//tuto: http://www.geeksforgeeks.org/bridge-in-a-graph/
/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here

#define MAXX 10007


int n;
vector<int>adj[MAXX];

int tyme;

bool visited[MAXX];
int parent[MAXX];

int low[MAXX];
int disc[MAXX];

vector<paii>bridges;



void dfs_bridge(int u)
{
	visited[u] = true;

	disc[u] = low[u] = ++tyme;

	int child = 0;

	loop(i, SZ(adj[u]))
	{
		int v = adj[u][i];

		if( ! visited[v])
		{
			parent[v] = u;

			dfs_bridge(v);

			low[u] = min(low[u], low[v]);

			if( low[v] > disc[u] )
			{
				bridges.pb(min(MP(u, v), MP(v, u)));
			}
			
		}
		else if( v != parent[u] )
		{
			low[u] = min(low[u], disc[v]);
		}
	}

	


}



int main()
{
	int kases, kaseno = 0;

	sf("%d", &kases);

	while(kases--)
	{
		sf("%d", &n);

		int u, k, v;
		char ch;

		loop(i, n)
		{
			adj[i].clear();
			parent[i] = -1;
			visited[i] = false;
		}

		bridges.clear();

		loop(i, n)
		{

			sf("%d %c%d%c", &u, &ch, &k, &ch);

			loop(j, k)
			{
				sf("%d", &v);

				adj[u].pb(v);
			}
		}

		loop(i, n)
		{
			if( ! visited[i] )
			{
				dfs_bridge(i);
			}
		}
		
		pf("Case %d:\n", ++kaseno);
		pf("%d critical links\n", SZ(bridges));
		
		sort(all(bridges));

		loop(i, SZ(bridges))
		{
			pf("%d - %d\n", bridges[i].fr, bridges[i].sc);
		}



	}





}

(CodeChef) MasterChef

Posted on July 6, 2015 by Hasib Al Muhaimin

A nice idea with memory optimization for Knapsack dp


// Link: http://www.codechef.com/JULY15/problems/MCHEF/


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here


#define MAXX 100007

#define INF 16843009


int N, M;
int K;
ll ara[MAXX];

int L, R, C;

int sum[4*MAXX];

ll dp[507];


void update(int idx, int st, int ed, int i, int j, int val)
{
	if(st == i && ed == j)
	{
		sum[idx] = min(sum[idx], val);
		return;
	}


	int l = idx*2;
	int r = l + 1;
	int mid = (st + ed)/2;


	sum[l] = min(sum[l], sum[idx]);
	sum[r] = min(sum[r], sum[idx]);

	sum[idx] = INF;

	if(j <= mid)
	{
		update(l, st, mid, i, j, val);
	}
	else if(mid < i)
	{
		update(r, mid+1, ed, i, j, val);
	}
	else
	{
		update(l, st, mid, i, mid, val);
		update(r, mid+1, ed, mid+1, j, val);
	}
}



int get(int idx, int st, int ed, int pos)
{
	if(st == ed)
	{
		return sum[idx];
	}


	int l = idx*2;
	int r = l + 1;
	int mid = (st + ed)/2;

	if(sum[idx] != INF)
	{
		sum[l] = min(sum[l], sum[idx]);
		sum[r] = min(sum[r], sum[idx]);
		sum[idx] = INF;
	}


	if(pos <= mid)
	{
		return get(l, st, mid, pos);
	}
	else
	{
		return get(r, mid+1, ed, pos);
	}
}



void init()
{
	mem(sum, 1);

	mem(dp, 0);
}



int main()
{
	//init(); cout<<sum[0];
	int kases;


	take(kases);

	while(kases--)
	{
		init();
		take(N, K, M);

		ll s = 0;

		loop(i, N)
		{
			take(ara[i]);

			s += ara[i];
		}

		loop(i, M)
		{
			take(L, R, C);

			update(1, 0, N-1, L-1, R-1, C);
		}

		//cerr<<"DONE"<<endl;

		loop(i, N)
		{
			if(ara[i] < 0)
			{
				ll tmp = -ara[i];

				//dump(tmp);

				C = get(1, 0, N-1, i);

				//dump(C);

				for(int pos=K; pos>=0; pos--)
				{
					if(pos + C <= K)
					{
						dp[pos + C] = max(dp[pos + C], dp[pos] + tmp );
					}
				}
			}
		}


		cout<< s + dp[K]<<endl;
	}

}

(CodeForces) B. New York Hotel

Posted on April 4, 2015 by Hasib Al Muhaimin


// link: http://codeforces.com/contest/491/problem/B

/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here
#define INF (1LL<<34)

ll N, M;
ll C, R;
ll x, y;

ll maxA = -INF, maxB = -INF, maxC = -INF, minD = INF;

ll minDist = INF;
int minID = -1;

ll dist(ll x, ll y)
{
	ll ret = -INF;
	ret = max(ret, maxA - (x+y));
	ret = max(ret, maxB - (x-y));
	ret = max(ret, maxC - (y-x));
	ret = max(ret, (x+y) - minD);
	return ret;
}

void init()
{

}


int main()
{
	//dump(minDist);
	init();
	sf("%lld %lld", &N, &M);
	sf("%d", &C);
	loop(i, C)
	{
		sf("%lld %lld", &x, &y);
		maxA = max(maxA, x+y);
		maxB = max(maxB, x-y);
		maxC = max(maxC, y-x);
		minD = min(minD, x+y);
	}
	sf("%d", &C);
	loop(i, C)
	{
		sf("%lld %lld", &x, &y);
		ll d = dist(x, y);
		//dump(d);
		if(d < minDist)
		{
			minDist = d;
			minID = i + 1;
		}
	}
	pf("%lld\n%d", minDist, minID);
    return 0;
}

(LightOj) 1141 – Number Transformation

Posted on March 30, 2015 by Hasib Al Muhaimin


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here



#define MAXX 1007

vector<int>factors[MAXX];

vector<int>primes;

void generatePrimes()
{
    bool isPrime[MAXX];

    mem(isPrime, 1);

    int root = sqrt(MAXX) + 7;

    for(int i=3; i<root; i++)
    {
        if(isPrime[i])
        {
            for(int j=i*i; j<MAXX; j+=(2*i))
            {
                isPrime[j] = false;
            }
        }
    }

    for(int i=2; i<MAXX;)
    {
        if(isPrime[i])
        {
            for(int j=2; i*j < MAXX; j++)
            {
                factors[i*j].pb(i);
            }
        }

        if(i == 2)
        {
            i++;
        }
        else
        {
            i += 2;
        }
    }
}


void init()
{
    generatePrimes();
}




int bfs(int source, int target)
{
    bool visited[MAXX];

    int dist[MAXX];

    mem(dist, -1);

    mem(visited, 0);


    queue<int>Q;

    Q.push(source);

    visited = true;
    dist = 0;

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();

        loop(i, SZ(factors[u]))
        {
            int v = u + factors[u][i];

            if( (v <= target) && !visited[v] )
            {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                if(v == target)
                {
                    break;
                }
                Q.push(v);
            }
        }
    }

    return dist[target];
}


int main()
{
    init();


    int kases, kaseno = 0;

    int s, t;

    sf("%d", &kases);

    while(kases--)
    {
        sf("%d %d", &s, &t);
        pf("Case %d: %d\n", ++kaseno, bfs(s, t));
    }

    return 0;
}

(LighOj) 1307 – Counting Triangles

Posted on March 22, 2015 by Hasib Al Muhaimin


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here

#define MAXX 2007


int N;
ll ara[MAXX];



ll solve()
{
    ll cnt = 0;

    sort(ara, ara+N);

    for(int i=N-1; i>-1; i--)
    {
        for(int j=i-1; j>-1; j--)
        {
            int low = 0, high = j - 1, mid;

            while(low <= high)
            {
                mid = (low+high)/2;

                if( ara[mid] + ara[j] > ara[i] )
                {
                    //possible
                    high = mid - 1;
                }
                else
                {
                    low = mid + 1;
                }
            }

            cnt += (j - low);


        }
    }

    return cnt;


}



void init()
{

}


int main()
{
    init();

    int kases, kaseno = 0;

    sf("%d", &kases);

    while(kases--)
    {
        sf("%d", &N);

        loop(i, N)
        {
            sf("%lld", &ara[i]);
        }

        pf("Case %d: %lld\n", ++kaseno, solve());
    }



    return 0;
}

(LightOj) 1154 – Penguins

Posted on March 22, 2015 by Hasib Al Muhaimin


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here

#define MAXX 208

#define INF (1<<29)





int capacity[MAXX][MAXX], tmpCapacity[MAXX][MAXX];
int N;
double D;
pair<double, double>points[MAXX/2];
vector<int>graph[MAXX];
int source, sink;
int total;

double sq(double x)
{
    return x*x;
}

double dist(pair<double, double>A, pair<double, double>B)
{
    return sqrt( sq(A.fr - B.fr) + sq(A.sc - B.sc) );
}


int findPath()
{
    bool visited[MAXX];

    bool found = false;

    int parent[MAXX];

    mem(parent, -1);
    mem(visited, 0);

    queue<int>Q;

    Q.push(source);
    visited = true;

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();

        loop(i, SZ(graph[u]))
        {
            int v = graph[u][i];

            if(!visited[v] && tmpCapacity[u][v] > 0)
            {
                visited[v] = true;
                parent[v] = u;
                Q.push(v);

                if(v == sink)
                {
                    found = true;
                    break;
                }
            }
        }

        if(found)
        {
            break;
        }
    }

    int pathCapacity = INF;
    int u, v = sink;

    while(parent[v] != -1)
    {
        u = parent[v];

        pathCapacity = min(pathCapacity, tmpCapacity[u][v]);

        v = u;

    }


    v = sink;

    while(parent[v] != -1)
    {
        u = parent[v];

        tmpCapacity[u][v] -= pathCapacity;
        tmpCapacity[v][u] += pathCapacity;

        v = u;
    }

    return found?pathCapacity:0;
}






int FLOW()
{
    loop(i, MAXX)
    {
        loop(j, MAXX)
        {
            tmpCapacity[i][j] = capacity[i][j];
        }
    }

    int ret = 0;

    int pathCapacity;

    while(pathCapacity = findPath())
    {
        ret += pathCapacity;
    }
    return ret;
}





void init()
{

}


int main()
{
    init();

    int kases, kaseno = 0;

    int n, c;

    int u, v;

    sf("%d", &kases);

    while(kases--)
    {

        mem(capacity, 0);
        loop(i, MAXX) graph[i].clear();
        total = 0;

        sf("%d %lf", &N, &D);


        source = 0;


        for(int i=1; i<=N; i++)
        {
            sf("%lf %lf %d %d", &points[i].fr, &points[i].sc, &n, &c);

            total += n;

            v = 2*i;
            u = v - 1;


            graph[u].pb(v);
            graph[v].pb(u);

            capacity[u][v] = c;

            graph.pb(u);
            graph[u].pb(source);

            capacity[u] = n;
        }


        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=N; j++)
            {
                if(i == j) continue;

                if(dist(points[i], points[j]) <= D)
                {
                    u = 2*i;
                    v = 2*j - 1;

                    capacity[u][v] = INF;

                    graph[u].pb(v);
                    graph[v].pb(u);
                }
            }
        }


        vector<int>vv;
        for(int i=1; i<=N; i++)
        {
            sink = 2*i - 1;

            if(FLOW() == total)
            {
                vv.pb(i);
            }
        }

        printf("Case %d:", ++kaseno);

        if(SZ(vv) == 0)
        {
            printf(" -1");
        }
        else
        {
            loop(i, SZ(vv))
            {
                printf(" %d", vv[i] - 1);
            }
        }

        pf("\n");











    }



    return 0;
}

(LightOj) 1155 – Power Transmission

Posted on March 20, 2015 by Hasib Al Muhaimin


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here

#define MAXX 207

#define INF (1<<29)

int source, sink;

int N;
int M;

int capacity[MAXX][MAXX];

vector<int>graph[MAXX];

int findPath()
{
    bool visited[MAXX];

    int parent[MAXX];

    mem(parent, -1);

    mem(visited, 0);

    queue<int>Q;

    Q.push(source);

    visited = true;

    bool found = false;

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();

        loop(i, SZ(graph[u]))
        {
            int v = graph[u][i];

            if(!visited[v] && capacity[u][v] > 0)
            {
                visited[v] = true;
                Q.push(v);

                parent[v] = u;

                if(v == sink)
                {
                    found = true;
                    break;
                }
            }
        }

        if(found)
        {
            break;
        }
    }



    int v = sink;

    int pathCapacity = INF;

    while(parent[v] != -1)
    {
        int u = parent[v];
        pathCapacity = min(pathCapacity, capacity[u][v] );

        v = u;
    }

    v = sink;

    while(parent[v] != -1)
    {
        int u = parent[v];

        capacity[u][v] -= pathCapacity;
        capacity[v][u] += pathCapacity;

        v = u;
    }

    if(found)
    {
        return pathCapacity;
    }
    else
    {
        return 0;
    }

}





int FLOW()
{
    int result = 0;

    int pathCapacity;

    while(true)
    {
        pathCapacity = findPath();

        if(pathCapacity == 0)
        {
            break;
        }
        else
        {
            result += pathCapacity;
        }
    }

    return result;
}





int solve()
{
    return FLOW();
}






void init()
{

}


int main()
{
    init();

    int kases, kaseno = 0;

    int B, D;

    int u, v, c;

    sf("%d", &kases);

    while(kases--)
    {
        mem(capacity, 0);


        sf("%d", &N);

        source = 0;

        sink = 2*(N + 1); // A number out of the range of node id.

        for(int i=0; i<=sink; i++)
        {
            graph[i].clear();
        }


        for(int i=1; i<=N; i++)
        {
            u = 2*i - 1;
            v = u + 1;

            graph[u].pb(v);
            graph[v].pb(u);

            sf("%d", &capacity[u][v]);
        }

        sf("%d", &M);

        loop(i, M)
        {
            sf("%d %d %d", &u, &v, &c);

            u = 2*u;
            v = 2*v - 1;

            graph[u].pb(v);
            graph[v].pb(u);

            capacity[u][v] = c;
        }

        sf("%d %d", &B, &D);

        loop(i, B)
        {
            sf("%d", &u);
            u = 2*u  - 1;

            graph.pb(u);
            graph[u].pb(source);

            capacity[ source ][u] = INF;
        }

        loop(i, D)
        {
            sf("%d", &v);
            {
                v = 2*v;

                graph[v].pb(sink);
                graph[sink].pb(v);

                capacity[v][sink] = INF;

            }
        }

        pf("Case %d: %d\n", ++kaseno, solve());

    }



    return 0;
}

(LightOj) 1153 – Internet Bandwidth

Posted on March 18, 2015 by Hasib Al Muhaimin


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here

#define MAXX 107
#define INF (1<<29)



int capacity[MAXX][MAXX];

int parent[MAXX];

vector<int>graph[MAXX];

int source, sink, N, m;


int findPath()    // BFS
{
    bool visited[MAXX];

    mem(visited, 0);

    queue<int>Q;

    Q.push(source);

    visited = true;

    mem(parent, -1);

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();

        loop(i, SZ(graph[u]))
        {
            int v = graph[u][i];

            if(!visited[v] && capacity[u][v] > 0)
            {
                Q.push(v);
                visited[v] = true;
                parent[v] = u;

                if(v == sink)
                {
                    break;
                }
            }
        }
    }


    int v = sink, path_capacity = INF;

    while(parent[v] != -1)
    {
        int u = parent[v];

        path_capacity = min(path_capacity, capacity[u][v] );

        v = u;
    }




    v = sink;

    while(parent[v] != -1)
    {
        int u = parent[v];

        capacity[u][v] -= path_capacity;

        capacity[v][u] += path_capacity;

        v = u;
    }

    if(path_capacity == INF)
        return 0;
    else
        return path_capacity;
}




int FLOW()
{
    int result = 0;

    while(true)
    {
        int pathCapacity = findPath();

        if(pathCapacity == 0)
        {
            break;
        }
        else
        {
            result += pathCapacity;
        }
    }

    return result;
}



int solve()
{
    return FLOW();
}



void init()
{

}


int main()
{
    init();


    int kases, kaseno = 0;

    int u, v, c;

    sf("%d", &kases);

    while(kases--)
    {
        sf("%d", &N);
        sf("%d %d %d", &source, &sink, &m);

        for(int i=0; i<=N; i++)
        {
            graph[i].clear();
        }

        mem(capacity, 0);

        loop(i, m)
        {
            sf("%d %d %d", &u, &v, &c);

            graph[u].pb(v);

            graph[v].pb(u);

            capacity[u][v] = capacity[v][u] = capacity[u][v] + c;
        }

        pf("Case %d: %d\n", ++kaseno, solve());

    }



    return 0;
}

(LightOj) 1129 – Consistency Checker

Posted on March 14, 2015 by Hasib Al Muhaimin


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here


int N;
string str;

bool isPossible;

struct DATA {
    bool endHere;
    bool hasTrace;
    DATA *child[10];

    DATA()
    {
        endHere = false;
        hasTrace = false;
        loop(i, 10) child[i] = NULL;
    }
    ~DATA()
    {
        loop(i, 10)
        {
            if(child[i] != NULL)
                delete child[i];
        }
    }
};

void addString(string &str, DATA *curNode)
{
    if(!isPossible) return;

    loop(i, SZ(str))
    {
        curNode->hasTrace = true;

        str[i] = str[i] - '0';
        if(curNode->child[ str[i] ] == NULL)
            curNode->child[ str[i] ] = new DATA();
        curNode = curNode->child[ str[i] ];


        if(curNode->endHere)
        {
            isPossible = false;
            return;
        }
    }

    if(curNode->hasTrace)
        isPossible = false;

    curNode->endHere = true;
}



void init()
{

}




int main()
{


    init();

    int kases, kaseno = 0;

    sf("%d", &kases);

    while(kases--)
    {
        sf("%d", &N);

        DATA *head = new DATA();

        isPossible = true;

        loop(i, N)
        {
            cin>>str;
            addString(str, head);
            //dump(head);
        }

        delete head;
        if(isPossible)
        {
            pf("Case %d: YES\n", ++kaseno);
        }
        else
        {
            pf("Case %d: NO\n", ++kaseno);
        }
    }



    return 0;
}

(LightOj) 1334 – Genes in DNA

Posted on March 14, 2015 by Hasib Al Muhaimin


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here

#define MAXX 50007






void calculatePrefixFunction(string &pattern, int pi[], int occur[])
{
    int m = SZ(pattern);
    pi[0] = -1;
    int k = -1;

    occur[0] = 1;

    for(int i=1; i<m; i++)
    {
        while(k > -1 && pattern[k+1] != pattern[i])
            k = pi[k];
        if(pattern[k+1] == pattern[i])
            k++;
        pi[i] = k;

        occur[i] = 1;

        if(k > -1)
            occur[i] += occur[k];
    }
}



void KMP(string &str, string &pattern, int pi[], int occur[], int dp[])
{
    int n = SZ(str);
    int m = SZ(pattern);

    int q = -1;
    loop(i, n)
    {
        while(q>-1 && pattern[q+1] != str[i])
            q = pi[q];
        if(pattern[q+1] == str[i])
            q++;
        if(q == m-1)
            q = pi[q];

        //as the problem says proper
        dp[i] = occur[q];

    }
}







ll solve()
{
    string str, pattern;
    int pi[MAXX];
    int occur[MAXX];

    string revStr, revPattern;
    int revPi[MAXX];
    int revOccur[MAXX];


    cin>>str>>pattern;

    revStr = str;
    revPattern = pattern;

    reverse(all(revStr));
    reverse(all(revPattern));

    calculatePrefixFunction(pattern, pi, occur);
    calculatePrefixFunction(revPattern, revPi, revOccur);

    int dp[2][MAXX];

    KMP(str, pattern, pi, occur, dp[0]);
    KMP(revStr, revPattern, revPi, revOccur, dp[1]);

    //dump(dp[0][9]);
    //dump(dp[1][3]);

    ll res = 0;

    for(int i=0, j=SZ(str)-2; j>-1; i++, j--)
    {
        res += (ll)dp[0][i]*(ll)dp[1][j];
        //pf("[%d] = %lld\n",i, dp[0][i]*dp[1][j]);
    }

    return res;

}




int main()
{
    //read("input");
    int kases, kaseno = 0;

    sf("%d", &kases);

    while(kases--)
    {
        pf("Case %d: %lld\n", ++kaseno, solve());
    }



    return 0;
}

UnLucky Codes

Focus Not On Your Past, But On Your Present!

(LighOj) 1026 – Critical Links

(CodeChef) MasterChef

A nice idea with memory optimization for Knapsack dp

(CodeForces) B. New York Hotel

(LightOj) 1141 – Number Transformation

(LighOj) 1307 – Counting Triangles

(LightOj) 1154 – Penguins

(LightOj) 1155 – Power Transmission

(LightOj) 1153 – Internet Bandwidth

(LightOj) 1129 – Consistency Checker

(LightOj) 1334 – Genes in DNA