Wednesday, August 16, 2017

LightOJ 1122 - Digit Count

// Fix a position, put a letter in it. for first idx, try all of the letters, in the same manner for all possible first charcter, try out all possible second character.  Then go to next position try all of the available letters, try putting all of them by a loop inside . continue doing it until you get to the required size of string.

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define MOD 100007

int ar[30];
int dp[12][12];
int n, sz;

int solve(int i, int digit)
{
    if(i==sz+1) return 1;

    if(dp[i][digit]!=-1) return dp[i][digit];

    dp[i][digit] = 0;

    for(int j=1; j<=n; j++)
    {
        if(i==1)
        {
            dp[i][digit] += solve(i+1, ar[j]);
            continue;
        }
        if(abs(digit - ar[j]) <= 2) dp[i][digit] += solve(i+1, ar[j]);
    }
    return dp[i][digit];
}

int main()
{
    int t, cs=0;
    scanf("%d", &t);
    while(t--)
    {
        mem(dp,-1);
        scanf("%d%d", &n, &sz);
        for(int i=1; i<=n; i++) scanf("%d",&ar[i]);
        int res = solve(1,n+1);
        printf("Case %d: %d\n", ++cs, res);
    }
    return 0;
}
at 1 comment:
Labels: ,

Lightoj 1038 - Race to 1 Again

Formualte the recurrance when you have the same state repeating over and over multiple times. move the same states to one side by pokkhantor and formulate a new recurrance relation.
E(n) = 1 + 1/D * Sum( n/di )  i=2 to D  + 1/D * E(n)
Formulate and Solve it to find the recurrance of E(n). Here D is the number of divisors of n;
 
// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define MOD 100007

vector<int>divisors[MOD];

void divs()
{
    FOR(i,2,MOD)
    {
        for(int j=i; j<=MOD; j+=i) divisors[j].pb(i);
    }
}

double dp[MOD];
bool vis[MOD];

double solve(int n)
{
    if(n==1) return 0.0;

    if(vis[n]) return dp[n];
    vis[n] = 1;

    dp[n] = 0.0;

    int cnt = SZ(divisors[n])+1;

    REP(i,SZ(divisors[n]))
    {
        dp[n] += solve(n/divisors[n][i]);
    }

    return dp[n] = (cnt + dp[n]) * (double) (1.0/(cnt - 1.0));
}


int main()
{
    divs();

    int t,cs=0,n;
    scanf("%d", &t);
    while(t--)
    {
        mem(vis,0);
        scanf("%d", &n);
        double res = solve(n);
        printf("Case %d: %f\n", ++cs, res);
    }
    return 0;
}
at No comments:
Labels: ,

Tuesday, August 15, 2017

CF 839B Journey

//Explanation

After going to each leaf node, calculate xi*pi i.e. len * probability at each level. from a node, multiple branch can be selected so, 1/branches probability needs to be multiplied at each level. so from node 1, we shall get the expected len of travelling to any leaf node after summing at the same level and multiple level also. 

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912

int vis[100007];
int d[100007];
vector<int> adj[100007];

double dfs(int u)
{
    vis[u] = 1;

    double levelsum= 0;
    int adjs = 0;

    REP(i,SZ(adj[u]))
    {
        int v = adj[u][i];
        if(vis[v]==0)
        {
            adjs++;
            d[v] = d[u] + 1;
            levelsum += dfs(v);
        }
    }
    if(adjs==0) return d[u];
    else
        return levelsum *(1.0/adjs) ;
}


int main()
{
    ll u,v,n,e,st;
    cin>>n;

    FOR(i,1,n-1)
    {
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    double ans = dfs(1);

    printf("%.15f\n", ans);

    return 0;
}
at 1 comment:
Labels: ,

Sunday, June 25, 2017

CSA 34C Max Or SubArray

Unsorted Ideas::

সবচেয়ে শরটেস্ট সাব অ্যাারে টা বের করতে বলেছে, যার মধ্যে আমরা ওই অ্যাারের মোট এলিমেন্ট গুলার মধ্যের সবচেয়ে ম্যাক্সিমাম অর সাম টা পেতে পারি ।

যেহেতু সাব অ্যাারে বের করতে বলছে, সাব সিকুয়েন্স না, তাই আমরা স্টারটিং এন্ড লিনিয়ারলি এক বাড়ায়ে বাড়ায়ে চেক করতে করতে যাব । এন্ড , সাব অ্যারের ফিনিশিং এন্ডটার যেহেতু ম্যাক্সিমাম আর সাম এর লোয়ার বাউন্ড টা আমাদের লাগতেসে তাই আমরা এইখানে যতক্ষন অর সাম, ম্যাক্স এর চাইতে বড় বা সমান থাকবে ততক্ষন hi এর মান এক এক করে কমিয়ে কমিয়ে চেক করে সাব এ্যারের ফিনিশিং এন্ডের লোয়ার বাউন্ড পেতে পারি ।

এখানে কোন অ্যাারের অর সাম একটা নন ডিক্রিজিং থিং... তাই এই প্রোপারটি তে আমরা বাইনারি সার্চ চালায়ে সাব অ্যারের নেক্সট এন্ড টা ফিক্স করে নিতেই পারি ।

আর তার মানে এক পাশ ফিক্স রেখে অন্য পাশ বাইনারি সার্চ করে অপটিমাল সাব অ্যাারে ফিক্স করতে পারি। কিন্তু এখন O(logn) টাইমে  যদি আমরা ওই লিনিয়ার এন্ড আর বাইনারি সার্চ করা পরের এন্ডের অর সাম পেতে চাই , তাহলে আমাদের অবশ্যই সেগমেন্ট ট্রি অথবা স্পারস টেবিল ডেটা স্ট্রাকচার ব্যবহার করতে পারি। তাহলেই হয়ে যাবে। এইতো আর কিছু লাগবে নাহ...। ওকেই ।

Code:









// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912
#define sz 100007

ll ar[sz], tr[sz*3];

void update(int node, int nb, int ne, int id, ll val)
{
    if(nb==ne)
    {
        ar[nb] = val;
        tr[node] = val;
        return;
    }

    int mid = (nb+ne)/2;
    int lft = 2*node;
    int rgt = lft + 1;

    if(id <= mid) update(lft, nb, mid, id, val);
    else if(id > mid) update(rgt, mid+1, ne, id, val);

    tr[node] = tr[lft] | tr[rgt];
}


ll query(int node, int nb, int ne, int i, int j)
{
    if(i>ne or j<nb) return 0;

    if(i<=nb and j>=ne) return tr[node];

    int mid = (nb+ne)/2;
    int lft = 2*node;
    int rgt = lft + 1;

    ll p1 = query(lft, nb, mid, i, j);
    ll p2 = query(rgt, mid+1, ne, i, j);

    return p1 | p2;
}

int main()
{
    ll n,x,y;
    scl(n);

    ll mx = 0;

    FOR(i,1,n)
    {
        scl(ar[i]);
        update(1,1,n,i,ar[i]);

        mx |= ar[i];
    }

    ll res = INT_MAX, ans = 0;

    FOR(i,1,n)
    {
        int lo = i, hi = n;
        while( lo <= hi)
        {
            int mid = (lo + hi)/2;

            if(query(1,1,n,i,mid) >= mx)
            {
                ans = mid;
                hi = mid-1;

                res = min(res, ans-i+1);
            }
            else
            {
                lo = mid + 1;
            }
        }
    }

    printf("%lld\n", res);

    return 0;
}















at





No comments:
  


















Labels:
,
,

























Codeforces 802AB - Heidi and Libray 










Unsorted Ideas::



This is a paging/caching type problem.



Normally we see the online version of this problem, suppose while caching we have a maximum limit of web pages our cache can contain.

When a user submits query for a webpage, server first takes a look at the cache memory. if its there , server crawls the page from the cache. Hence, we dont need to undergo the cost of bringing the page from the server which is 1 chf according to the problem. :v



সেইমভাবে, আমাদের একটা লাইব্রেরি আছে, আরেকটা বুক স্টোর আছে । লাইব্রেরির নির্দিষ্ট ক্যাপাসিটি আছে। এর বেশি নিতে পারে না বই লাইব্রেরী ।

প্রতিদিন বিভিন্ন ইউজার আসবে এবং বিভিন্ন নাম্বার বইটা পড়তে চাইবে। ওই যে একটু আগের ওয়েব পেজ কোয়েরির মত, বই কোয়েরি করবে।

যদি লাইব্রেরি থাকে তাহলে লাইব্রেরিয়ান তোমাকে বইটা দিবে। এতে লাইব্রেরিয়ানের কোন খরচ পড়বে না।

আর যদি আগে থেকে লাইব্রেরি তে না থাকে বইটি, তবে পার্শ্ববর্তী দোকান থেকে বইটি কিনে আনতে হবে। এতে এক ডলার করে খরচ পড়বে।

ইনিশায়ালি লাইব্রেরি খালি থাকবে, কোন বই থাকবে। স্বাভাবিক, ইনিশিয়ালি ক্যাশ এ কোন ওয়েব পেজ ফেচ করে আনা থাকে না।



অরিজিনাল ওয়েব পেজ ক্যাশিং সিস্টেম এ, কোয়েরি থাকে অনলাইন। মানে কেউ জানে না ইউজার তারপর কি কোয়েরি করবে।

বাট নাও, লেট আস সি দ্য, অফলাইন ভারশান অফ দ্য প্রব্লবেম । মানে আমাদের একটা সিকুয়েন্স অফ নাম্বারস i.e. সিকুয়েন্স অফ কোয়েরিস অফলাইন, মানে মানে আগে থেকে দেয়া থাকবে।



তার সাথে ক্যাশের ম্যাক্স সাইজ মানে লাইব্রেরীর ম্যাক্স ধারণ ক্ষমতা দিয়ে দিবে।



আমাদের বলতে হবে, সবচেয়ে ইফশিয়েন্ট ওয়েতে কিভাবে ক্যাশিং করলে আ

মরা সবচেয়ে কম কস্টে সার্ভিস দিতে পারব।





Code ::






// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
using namespace std;

#define inf 123456789
#define sz 400007

ll ar[sz], nx[sz];
map<ll,ll> mp;

int main()
{
    ll n,k;

    scll(n,k);

    REP(i,n)
    {
        scl(ar[i]);
        mp[ ar[i] ] = INT_MAX; 
        //ধরে নিচ্ছি সবগুলা নাম্বারের কোন রিপিটিশান হয় নি , সব INT_MAX দিয়ে আপডেট করছি । 
    }

    REV(i,n) //উলটা দিক থেকে আসছি 
    {
        nx[i] = mp[ ar[i] ]; 
        //শেষ থেকে শুরুতে যাচ্ছি যেহেতু, প্রথম এপিয়ারেন্স এ তাই এর নেক্সটে আর রিপিট
        // হবার কোন পসিবিলিটি নাই , তাই ইনফিনিটি দিয়ে দিচ্ছি। মানে রিপিট নাই পরে আর। 
        
        mp[ ar[i] ] = i;        
        //mp[ar[i]] কে লেটেস্ট এপিয়ারেন্স এর পজিশান অ্যাাসাইন করে দিচ্ছি ,
        // যাতে অ্যাারের আগের দিকে কোথাও এই নাম্বার আবার আসলে এইটা ইউজ করতে পারি।   
    }


        //প্রথমে nx[] নামে একটা অ্যাারে বানাতে হবে, ক্যাশ থেকে আমরা যখন জিনিসপত্র ডিলিট করে দিব,
        //  তখন জানা দরকার , ওই ইন্ডেক্সের রিকোয়েস্টড নাম্বারটি নেক্সট কখন রিপিট করছে 
        // সেই অনুযায়ী, আমরা নেক্সট রিপিটিং টাইম অনুযায়ী , প্রত্যেক ইন্ডেক্সের জন্য
        // নেক্সট রিপিটিং টাইমটা যদি সেট এ রেখে দিই, তাহলে আমরা যখনি ক্যাশ/সেট টা ফিল হয়ে যাবে
        // তখন সবচেয়ে বেশি দূরবর্তী রিপিটিং টাইম ওয়ালা রিকুয়েস্ট টি যেটা সেটের শেষে থাকবে স্বভাবতই,
        // আপাতত সেটি ডিলিট করে দিয়ে, কারেন্ট বই এর জন্য জায়গা করে দিতে পারি লাইব্রেরিতে :p 


    set<ll> st;  //ইনিশিয়ালিজিং দা ক্যাশ, ক্যাশেও কোন রিপিট থাকবে না, সেট ও থাকবে না তাই :V
    ll cnt = 0;

    REP(i,n)
    {
       //৫ ৩ 


       // ১ ২ ১০ ২ ১০   


       // প্রথম ১০ দ্বিতীয়  ১০ , দ্বিতীয় ১০ এ যখন যাব দেখবে যে এটি আগে থেকেই আছে। 


       //তো আমাদের এইটা আর আগেরটা নেক্সট টাইম এইটা আর দরকার নাই। আমাদের দরকার , দ্বিতীয় দশ এর 


       //নেক্সট পজিশান , তাই আগের দশের নেক্সট পজিশান মানে বর্তমান ১০ এর ইন্ডেক্স i কে রিমুভ করছি


       // আমরা ক্যাশ থেকে। পরে আবার নিচে nx[i] ইনসারট করছি কিন্তু । 


     
        if(st.count( i ))
        {
             st.erase( i ); 
             //রিমুভিং দ্য কারেন্ট পজিশান 


        }
        else
        {
            cnt ++ ; 
            //এডিং কস্ট ফর বায়িং দ্য বুক ইচ টাইম, ফ্রম বুক স্টোর টু লাইব্রেরি


        }

        if(SZ(st) == k)           //লাইব্রেরি ফুল হয়ে গ্যাছে , তাই 
        {
            st.erase( --st.end() ); 
            //ডিলিটিং দ্য লেট(দেরী) মোস্ট ওয়ান , রিকুয়েস্ট 


        }

        st.insert( nx[i] ); 
        // ইনসারটিং দ্য নেক্সট রিপিটিং টাইম অফ দ্য কারেন্ট রিকুয়েস্ট  


    }

    printf("%lld\n", cnt);

    return 0;
}


Clean Code :


// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912
#define sz 400007

ll ar[sz], nx[sz];
map<ll,ll> mp;

int main()
{
    ll n,k;

    scll(n,k);

    REP(i,n)
    {
        scl(ar[i]);
        mp[ ar[i] ] = INT_MAX;
    }

    REV(i,n)
    {
        nx[i] = mp[ ar[i] ];
        mp[ ar[i] ] = i;
    }

    set<ll> st;
    ll cnt = 0;

    REP(i,n)
    {
        if(st.count( i ))
        {
             st.erase( i );
        }
        else
        {
            cnt ++ ;
        }

        if(SZ(st) == k)
        {
            st.erase( --st.end() );
        }

        st.insert( nx[i] );
    }

    printf("%lld\n", cnt);

    return 0;
}















at





No comments:
  


















Labels:
,
,

















          

        

          

        

Monday, June 12, 2017


          

        









Codechef June Long - SUMQ














https://www.codechef.com/problems/SUMQ






// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912
#define sz 100007
#define mod 1000000007

ll arx[sz];
ll cmx[sz];

ll ary[sz];

ll arz[sz];
ll cmz[sz];


ll bsrch(ll ar[], ll val, ll lo, ll hi)
{
    ll ans = 0;
    while(lo<=hi)
    {
        ll md = (lo+hi)/2;

        if(ar[md]<=val) ans = md, lo = md+1;
        else hi = md-1;
    }
    return ans;
}

int main()
{
    ll t,s,x,y,z;
    scl(t);
    while(t--)
    {
        ll smx = 0, smz = 0;

        scll(x,y);
        scl(z);

        cmx[0] = 0;
        FOR(i,1,x) scl(arx[i]);
        sort(arx+1,arx+x+1);
        FOR(i,1,x) cmx[i] = (cmx[i-1] + arx[i])%mod;

        FOR(i,1,y) scl(ary[i]);

        cmz[0] = 0;
        FOR(i,1,z) scl(arz[i]);
        sort(arz+1,arz+z+1);
        FOR(i,1,z) cmz[i] = (cmz[i-1] + arz[i])%mod;

        ll idx,idz,tmp, res = 0;

        FOR(i,1,y)
        {
            tmp = ary[i];

            //arx e tmp er che choto kon idx prjnto ase

            idx = upper_bound(arx+1,arx+x+1,tmp) - arx;
            idz = upper_bound(arz+1,arz+z+1,tmp) - arz;

            idx--; idz--;   // becoz right most index of tmp<=arx[i]

//            idx = bsrch(arx, tmp, 1, x);
//            idz = bsrch(arz, tmp, 1 , z);

            smx = cmx[idx];
            smz = cmz[idz];

            res = ( res + ( (idx*tmp)%mod + smx)%mod * ( (idz*tmp)%mod + smz)%mod ) % mod;
        }
        pri(res);
    }
    return 0;
}















at





No comments:
  


















Labels:
,
,

















          

        

          

        

Wednesday, June 7, 2017


          

        









Light OJ 1257 – Farthest Nodes in a Tree (II)










//Unsorted Ideas:



ট্রি থেকে ফারদেস্ট নোড মানে সবার দূরবর্তী দুইটা নোডের ডিসটেন্স বের করতে হবে।



ট্র ডায়ামেটার বের করা। যেহেতু ট্রি তাই  কেমিস্ট্রির শিকলের মত সবচেয়ে বড় শিকলটা বের করতে হবে! :v



যে কোন একটা র‍্যানডম নোড থেকে বিএফেস চালায়ে শিকলের এক প্রান্ত ফিক্স করতে হবে। তারপর শিকলের এই এক প্রান্ত থেকে আরেকটা বিএফেস চালিয়ে অন্য প্রান্তের নোড বের করতে হবে।



তারপর এই দুই প্রান্ত থেকে ছাড়া বিএফেস এ ক্যালকুলেট করা ডিস্টেন্স এর মধ্য থেকে প্রত্যেক নোডের জন্য ম্যাক্সিমাম ডিসটেন্স প্রিন্ট করতে হবে। এই... শেষ... !



Code: 






// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912
#define sz 30007

ll u,v,w,n,x,y,z;

vector<int> adj[sz], cst[sz];
bool vis[sz], vis1[sz];
int d[sz], d1[sz];

ll ex,src;

void init()
{
    REP(i,sz)
    {
        d[i] = -1, d1[i] = -1;
        vis[i] = 0, vis1[i] = 0;
    }
}

int BFS(int s)
{
    queue<int> Q;

    Q.push(s);
    vis[s] = 1;
    d[s] = 0;

    int u,v;
    int mx = 0;

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

        if(d[u]>mx) mx = d[u], ex = u;

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

            if(vis[v]==0)
            {
                vis[v] = 1;
                d[v] = d[u] + cst[u][i];
                Q.push(v);
            }
        }
    }
    return ex;
}

void BFS1(int s)
{
    queue<int> Q;

    Q.push(s);
    vis1[s] = 1;
    d1[s] = 0;

    int u,v;
    int mx = 0;

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

        if(d1[u]>mx) mx=d[u], ex = u;


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

            if(vis1[v]==0)
            {
                vis1[v] = 1;
                d1[v] = d1[u] + cst[u][i];
                Q.push(v);
            }
        }
    }
}

int main()
{
    ll t,cs=0;
    scl(t);
    while(t--)
    {
        scl(n);
        REP(i,n-1)
        {
            scll(x,y), scl(z);
            adj[x].pb(y);
            adj[y].pb(x);
            cst[x].pb(z);
            cst[y].pb(z);
        }

        int ekpranto, oporpranto;

        init();
        ekpranto = BFS(0);
        init();
        oporpranto = BFS(ekpranto);
        BFS1(oporpranto);

        printf("Case %lld:\n", ++cs);

        REP(i,n)  printf("%d\n", max(d[i],d1[i]));

        REP(i,sz) adj[i].clear(), cst[i].clear();
    }
    return 0;
}













at





No comments:
  


















Labels:
,
,
,
,

















          

        

          

        

Sunday, June 4, 2017


          

        









LightOJ 1066 Gathering Food 










//Unsorted Ideas: 

ফুড কালেক্ট করা লাগবে। গ্রিড আছে। গ্রিডে হ্যাশ আছে, ডট আছে , আপারকেস লেটার আছে ।

লেটার মানে ফুড । A থেকে শুরু করে বিভিন্ন লেটার পর্যন্ত থাকতে পারে তবে সব সিকুয়েনশিয়ালি একটার পর একটা থাকবে তবে বিভিন্ন পজিশানে।



এখন আমরা A থেকে শুরু করব লাস্ট ক্যারেক্টার পর্যন্ত সবগুলো ফুড কালেক্ট করব শরটেস্ট টাইমে। কিন্তু কন্সট্রেইন্টস হল - আগে ছোট ক্যারেক্টারের ফুড কালেক্ট করে তারপর বড় ক্যারেক্টার এ যেতে পারব।



এখন আমরা যদি A থেকে শুরু করে লাস্ট ডেসিটিনেশান ক্যারেক্টার পর্যন্ত একটা বিএফেস চালায়ে শরটেস্ট পাথ বের করি তাহলে লাভ নাই। কারন এখানে কোন পাথে সোর্স থেকে ডেস্টিনেশানে যাব সেটা ফিক্স করা আছে।



এখন এরকম ক্ষেত্রে যেটা করে যায় সেটা হচ্ছে, ঐ ফিক্স করা পাথ ধরে আগাতে পারি। ওই পাথের প্রতি দুইটা নোড কে একবার সোর্স আরেকবার ডেস্টিনেশান ধরে ধরে সামনে যেতে পারি।



আর যাবার সময় কস্ট যোগ করে করে রেখে যেতে পারি । প্রতিবার বিএফেস শেষে যখনি আমরা পরের লেটার পেয়ে যাচ্ছি, তখনি সেটাকে নেক্সট বিএফেস এর সোর্স বানিয়ে দিয়ে আবার নতুন বিএফস চালাব। এভাবে করে যেতে থাকব যতক্ষন লাস্ট ক্যারেক্টার পর্যন্ত পৌছাতে না পারি।



এখানে, একটা লক্ষণীয় ব্যাপার আছে, 

ইনভেলিড সেল হিসেব করার সময়... গ্রিডের বাইরে গেলে ইনভ্যালিড, # পেলে ইনভ্যালিড অ্যান্ড ঐ যে, ডেস্টিনেশান এর চাইতে বড় কোন ক্যারেক্টার পেলেও ইনভ্যালিড, তবে আমরা চাইলে পুরানো ভিজিট করে আসা ছোট কোন ক্যারেক্টার আবার ইউজ করে যেতে পারি ।



ডিরেকশান অ্যাারে তা চার পাশ চেক দিতে হবে উপরের ভ্যলিডিটি গুলা ঠিক রেখে যদি সামনে যেতে পারি, তবেই আমরা আবার কিউ তে পুশ করব নতুবা না ।



Code:




// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912
#define sz 13

ll n;
string sa[sz];
int d[sz][sz];
bool vis[sz][sz];
char destination;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

struct point
{
    int x,y;
};

point src;

void initt()
{
    REP(i,sz) REP(j,sz) vis[i][j] = 0, d[i][j] = INT_MAX;
}

int BFS(point s)
{
    initt();

    queue<point> Q;
    Q.push(s);

    vis[s.x][s.y] = 1;
    d[s.x][s.y] = 0;

    point u,v;

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

        if(sa[u.x][u.y]==destination)
        {
            src.x = u.x;
            src.y = u.y;
            
            return d[u.x][u.y];
        }
        
        REP(i,4)
        {
            v.x = u.x + dx[i];
            v.y = u.y + dy[i];

            if(v.x>=0 and v.x<n and v.y>=0 and v.y<n  and vis[v.x][v.y]==0)
            {
                 //give boundary chk first
                //then chk for xtra contraints
                
                if((sa[v.x][v.y]>destination and destination<='Z') or sa[v.x][v.y]=='#')


                {


                     continue;


                }                          


                vis[v.x][v.y] = 1;
                d[v.x][v.y] = d[u.x][u.y] + 1;
                Q.push(v);
            }
        }
    }
    return -1;
}

int main()
{
    ll t,cs=0;
    scl(t);
    while(t--)
    {
        scl(n);
        REP(i,n) cin>>sa[i];

        int cnt = 0;

        REP(i,n)
        {
            REP(j,n)
            {
                if(sa[i][j]=='A') src.x=i, src.y=j;
                if(isupper(sa[i][j])) cnt++;
            }
        }

        int cst=0, res = 0;
        destination = 'B';

        printf("Case %lld: ",++cs);

        //below used cnt-1
        //for value cnt==1,for only A is present
        //it doesnt enter loop,so print automatic 0 for this

        REP(i,cnt-1)
        {
            cst = BFS(src);
            
            if(cst==-1)
            {
                puts("Impossible");
                break;
            }
            else res += cst;

            destination++;
        }
        if(cst!=-1) printf("%d\n", res);
    }
    return 0;
}















at





No comments:
  


















Labels:
,

























SPOJ/HackerRank BITMAP 










//Unsorted Ideas: 



২ডি পিক্সেল গ্রিড। ০ মানে ব্ল্যাক আর ১ মানে হোয়াইট পিক্সলে ।

প্রত্যেকটা ০ পিক্সেল থেকে তার সবচে নিকটবর্তী ১ পিক্সেল এর ডিসটেন্স লাগবে । 







ডিসটেন্স বের করার ফরমুলা দেয়া আছে।    ->    d( p1, p2)=| i1-i2|+| j1-j2|. 







নাইভ অ্যাপ্রোচ প্রত্যেকটা জিরো কে সোর্স বানিয়ে বার বার  বিএফেস করে দেখতে হবে তার সবচে কাছাকাছি কোথায় ১ আছে। অনেকগুলা জিরোর জন্য টাইম লিমিট খাবে ।







যেহেতু এখানে ডিসট্যান্স সিমেট্রিক তাই আমরা উলটা করলেই পারি। সবগুলা ১ থেকে বিএফেস চালায়ে যতক্ষন ছোট ডিস্টেন্স দিয়ে জিরোর ডিস্টেন্স কে আপডেট করা যায় ততক্ষন করব। 



আগে থেকেই ছোট থাকলে কিছু করার দরকার নাই, কিন্তু আগের ১ থেকে করেস্পন্ডিং ০ র দূরত্ব কারেন্টটার চাইতে বড় হলে লেটেস্ট ১ থেকে ছোট ডিসটেন্স দিয়ে ওই জিরো কে আপডেট করে দিব আমরা । 







ডায়াক্সট্রা তে যেভাবে আপডেট করি আমরা নোড করে মিনিমাম কস্ট দিয়ে সেরকম অনেকটা। যাই হোক... এইত্তো আর কিছু না... অকা! 







Code:






// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 123456789
#define sz 202

string sa[sz];
ll r,c;

struct point
{
    int x,y;
};

bool vis[sz][sz];
int d[sz][sz];

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

void init()
{
    REP(i,sz) REP(j,sz) vis[i][j] = 0, d[i][j] = INT_MAX;
}

void BFS(int i, int j)
{
    mem(vis,0);

    point s;
    s.x = i, s.y = j;

    queue<point> Q;
    Q.push(s);

    vis[s.x][s.y] = 1;
    d[s.x][s.y] = 0;

    point u,v;

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


        REP(i,4)
        {
            v.x = u.x + dx[i];
            v.y = u.y + dy[i];

            if(v.x>=0 and v.x<r and v.y>=0 and v.y<c)
            {
                 // boundary satisfies then,  enter if we have unvisited 0

                if( vis[v.x][v.y]==0 and sa[v.x][v.y]=='0' )
                {
                    vis[v.x][v.y] = 1;

                    //update 0 only if it can be relaxed to lower cost than the previous distance


                    if(d[v.x][v.y] > d[u.x][u.y] + 1)
                    {
                        d[v.x][v.y] = d[u.x][u.y] + 1;
                        Q.push(v);
                    }
                }
            }
        }
    }
}

int main()
{
    ll t,cs=0;

    scl(t);
    while(t--)
    {
        scll(r,c);
        REP(i,r) cin>>sa[i];

        int cnt = 0;

        init();

        REP(i,r)
        {
            REP(j,c)
            {
                if(sa[i][j]=='1') BFS(i,j);
            }
        }

        REP(i,r)
        {
            REP(j,c)
            {
                if(j) putchar(' ');
                printf("%d", d[i][j]);
            }
            puts("");
        }
    }
        return 0;
}















at





No comments:
  


















Labels:
,
,
,

























LightOJ 1263 Equalizing Money










//Unsorted Ideas:

নোড আছে এজ আছে। নোডদের কাছে বিভিন্ন পরিমানে টাকা আছে। গ্রাফের মত বিভিন্ন এজে কানেক্টেড
লোক গুলা। তারা চাইলে এক আরেকজনকে টাকা দিতে পারবে সবার সমান টাকা করার জন্য । যদি তারা এজ 
দিয়ে কানেক্টেড থাকে।



 তার মানে সহজ কথায় এই গ্রাফে যেহেতু এক বা একাধিক ডিসজয়েন্ট গ্রুপে ভাগ হয়ে
থাকবে লোকজন। তো এজ এর কানেকশানে টাকা দিতে পারবে মানে আলাদা আলাদা গ্রুপে নিজেদের মধ্যে
টাকা দিতে নিতে পারবে। তো এখন যেহেতু প্রব্লেমে বলা আছে ফাইনালি সবার কাছে সমান পরিমান টাকা থাকবে
সো, আমরা ধরেই নিতে পারি সবার কাছে (টোটাল টাকা / মানুষ) মানে এভারেজ যেই টাকা টা আসে মোট 
টাকার সেটা সবার কাছে থাকবে। 



 এখন যেহেতু ডিসজয়েন্ট সেটে আলাদা আলাদা গ্রুপে টাকা আদান প্রদান হতে পারে। এক গ্রুপের সাথে আরেক
গ্রুপেরে রিলেশান নাই। কিন্তু তাদের প্রত্যেকের টাকা আলাদা ভাবে অবশ্যই এভরেজ হতে হবে। 

তাই আমরা চাইলে সব আলাদা গ্রুপের জন্য ওই গ্রুপের মানুষ কত, আর টাকা কত সেটা ডিএফএস অর 
ইউনিয়ন ফাইন্ড দিয়ে বের করতে পারি। 





তখন দেখব যে বের টাকা দিয়ে মানুষ এর সংখ্যা ডিভিজিবল কিনা। যদি না হয় তাহলে সম্ভব না। 

আর যদি হয় ও , তখন দেখতে হবে ওই গ্রুপের সবার কাছে আমাদের অল ইকুয়েল করার জন্য যেই এভরেজ ভেবে রেখেছিলাম তার সাথে ম্যাচ করে কিনা। যদি না করে তাহলেও সম্ভব না। 



এইতো... রাফ আইডিয়া... এটাই... :D  :/ 



Code : 








// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912
#define sz 10007

ll n,e,u,v;
ll mny[1234];
vector<int> adj[sz];
int ppl,tot,sm;
bool vis[1234];


void dfs(int u)
{
    tot += mny[u];
    ppl++;
    vis[u] = 1;

    REP(i,SZ(adj[u]))
    {
        int v = adj[u][i];
        if(vis[v]==0)
        {
            dfs(v);
        }
    }

}

int main()
{

    ll t,cs=0;
    scl(t);
    while(t--)
    {
        sm = 0;
        scll(n,e);
        REP(i,n) scl(mny[i]), sm += mny[i];

        int fl = 0;

        REP(i,e)
        {
            scll(u,v);
            u--,v--;
            adj[u].pb(v);
            adj[v].pb(u);
        }

        int avg = sm/n;     //each getting equal mny finally

        REP(i,n)
        {

            ppl = 0;
            tot = 0;
            if(vis[i]==0)
            {
                dfs(i);

                if(tot%ppl!=0)
                {
                    fl=1;
                    break;
                }
                else
                {
                    if(avg != tot/ppl)
                    {
                        fl =1;
                        break;
                    }
                }
            }

        }

        printf("Case %lld: ", ++cs);

        if(fl) puts("No");
        else puts("Yes");

        REP(i,sz) adj[i].clear();
        mem(vis,0);
    }

    return 0;
}















at





No comments:
  


















Labels:
,
,
,

















          

        

          

        

Saturday, June 3, 2017


          

        









UVa 532 - Dungeon Master













// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 123456789

ll l,r,c;
string sa[33][33];
bool vis[33][33][33];
int d[33][33][33];

struct point
{
    int x,y,z;
};

int dx[] = {1,-1,0,0,0,0};
int dy[] = {0,0,1,-1,0,0};
int dz[] = {0,0,0,0,1,-1};

void BFS(point src)
{
    mem(d,0);
    mem(vis,0);

    queue<point> Q;

    point u,v;

    vis[src.x][src.y][src.z] = 1;
    d[src.x][src.y][src.z] = 0;

    Q.push(src);

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

   //     cout << u.x << " " << u.y << " " << u.z << endl;

        REP(i,6)
        {
            v.x = u.x + dx[i];
            v.y = u.y + dy[i];
            v.z = u.z + dz[i];

            if(v.x>=0 and v.x<l  and  v.y>=0 and v.y<r  and v.z>=0 and v.z<c)
            {
                if(vis[v.x][v.y][v.z]==0 and sa[v.x][v.y][v.z]!='#')
                {
                  //  cout << " v---- "; cout << v.x << " " << v.y << " " << v.z << endl;
                    vis[v.x][v.y][v.z] = 1;
                    d[v.x][v.y][v.z] = d[u.x][u.y][u.z] + 1;
                    Q.push(v);
                }
            }
        }
    }

}

int main()
{
    ll sx,sy,sz,ex,ey,ez;

    while(scanf("%lld%lld%lld", &l, &r, &c)==3 and l+r+c)
    {
        REP(i,l)
        {
            REP(j,r) cin>>sa[i][j];
        }

        REP(i,l)
        {
            REP(j,r)
            {
                REP(k,c)
                {
                    if(sa[i][j][k]=='S') sx=i, sy=j, sz = k;
                    if(sa[i][j][k]=='E') ex=i, ey=j, ez = k;
                }
            }
        }

        point src;
        src.x = sx, src.y = sy, src.z = sz;

        BFS(src);

        if(!vis[ex][ey][ez]) printf("Trapped!\n");
        else
        {
            printf("Escaped in %d minute(s).\n",  d[ex][ey][ez]);
        }
    }

    return 0;
}















at





No comments:
  


















Labels:
,
,
,
,

















          

        

          

        

Thursday, June 1, 2017


          

        









Codejam 2017 B - Tidy Numbers













//aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912

vector <int> digs;
ll n;
ll dp[19][3];

ll go(ll i, ll issmall, ll prev, ll sum)
{
    sum = sum*10 + prev;

    if(i==SZ(digs))
    {
        return sum;
    }

    if(dp[i][issmall]!=-1) return dp[i][issmall];

    ll hi = (issmall) ? 9:digs[i];

    dp[i][issmall] = 0;

    for(int j=hi; j>=0; j--)
    {
        if(prev<=j)
            dp[i][issmall] =max(dp[i][issmall], go(i+1, issmall|j<hi,j,sum));
    }
    return dp[i][issmall];
}

ll makeandgo(ll n)
{
    digs.clear();
    if(!n) digs.pb(0);

    while(n)
    {
        digs.pb(n%10);
        n/=10;
    }
    reverse(all(digs));

    mem(dp,-1);
    ll ans = go(0,0,0,0);
    return ans;
}

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

    ll t,cs=0;
    scl(t);
    while(t--)
    {
        scl(n);

        printf("Case #%lld: %lld\n", ++cs, makeandgo(n));
    }

    return 0;
}















at





No comments:
  


















Labels:
,
,
,

























CodeJam 2017 A - Oversized Pencake Flippers















// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912

int main()
{
   // freopen("D:/gjam17/inp.txt", "r", stdin);
   // freopen("D:/gjam17/out.txt", "w", stdout);

    ll i,t,cs=0,k;
    string s,tmp;
    scl(t);
    while(t--)
    {
        cin>>s;
        scl(k);

        tmp = s;
        bool fl = 1, fl2=1;
        ll cnt=0, cnt2=0;

        i=0;
        while(i+k<=SZ(s))
        {
            if(s[i]=='-')
            {
                cnt++;
                REP(j,k)
                {
                    if(s[i+j]=='+') s[i+j]='-';
                    else s[i+j]='+';
                }
            }
            i++;
        }
        for(; i<SZ(s); i++) if(s[i]=='-') fl=0;

        reverse(all(tmp));
        i=0;

        while(i+k<=SZ(tmp))
        {
            if(tmp[i]=='-')
            {
                cnt2++;
                REP(j,k)
                {
                    if(tmp[i+j]=='+') tmp[i+j]='-';
                    else tmp[i+j]='-';
                }
            }
            i++;
        }

        for(; i<SZ(tmp); i++) if(tmp[i]=='-') fl2=0;

        printf("Case #%lld: ", ++cs);
        if(fl==0 and fl2==0) puts("IMPOSSIBLE");
        else
        {
            if(fl==1 and fl2==1)  printf("%lld\n", min(cnt,cnt2));
            else if(fl==1) printf("%lld\n", cnt);
            else printf("%lld\n", cnt2);
        }
    }
    return 0;
}















at





1 comment:
  


















Labels:
,

















        

      









Subscribe to:
Comments (Atom)