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;
}

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;
}

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;
}