Google's hiring contest, APAC Kickstart 2017 Round E is going to held on Sunday, August 27, 2017 05:00 UTC – 08:00 UTC

Ready to get started solving fun, challenging problems? Throughout the year, Code Jam hosts online Kickstart rounds to give students the opportunity to develop their coding skills, get acquainted with Code Jam’s competition arena, and potentially get noticed by Google recruiters, too. Participate in one—or join them all!

For more visit here.

I'm trying to find efficient algorithm for finding shortest path in weighted(Positive/Negative) graph with maximum edge limit.

For example, in the graph below if we demand the shortest path from A to C with restriction the path can contain at most two edges. It would be A->B->C and total cost 5 (Which is greater than A->D->E->C)

I think when the graph is (directed or undirected) has no negative edge, we can use Dijkstra with little modification, such that we will keep the number of edges in the currently discovered shortest path from source to currently used vertex for relaxation. Is my idea OK? Or there is much better something?

And how can we solve the similar problem when the graph(directed) consists of negative edges(but no negative cycle)?

I'm trying to find an algorithm for calculating Minimum Insertion needed to make a string palindrome. My Idea is to find the length of longest palindromic sub sequence for the given string and subtract it from the string length. Will it work? Or there is any cornered case where it will not work, Please help !!!!

Recently I'm trying to solve UVa-10938. My solution has given correct answer for all available cases and also for the cases given in uDebug cases. But I still getting wrong answer :( , I don't understand why.

My approach is finding the LCA(Lowest Common Ancestor) for the given pair in the query and find the path between two node. If the path has odd number of edges than I find a(middle node in the path) and b(next of the middle node in the path), And there is an infinite lope between this two nodes.

On the other hand, if the path has even number of edges, than I find a(middle node in the path), And both flea meet in a.

Please help me to debug by providing some test cases where my solution will give wrong answer. Here's the code.

using namespace std;

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>


#define ll long long
#define MAXN 5001
#define LOGN 14


bool visit[MAXN];
ll par[MAXN][LOGN], level[MAXN];
vector<ll> v[MAXN];


void DFS(ll src, ll lev)
{
    visit[src] = true;
    level[src] = lev;

    for(ll i=0; i<v[src].size(); i++){
        ll temp = v[src][i];

        if(!visit[temp]){
            par[temp][0] = src;
            DFS(temp, lev+1);
        }
    }
}


void PreProcess(ll n)
{
    for(ll i=1; i<LOGN; i++){
        for(ll j=1; j<=n; j++){
            if(par[j][i-1]!=-1) par[j][i] = par[par[j][i-1]][i-1];
        }
    }
}

ll LCA(ll a,ll b)
{
    ll log = 0, temp;

    if(level[a]<level[b]){
        temp = a;
        a = b;
        b = temp;
    }

    while(1){
        temp = log+1;
        if((1<<temp)>level[a]) break;
        log++;
    }

    for(ll i=log; i>=0; i--){
        if(par[a][i]!=-1 && level[par[a][i]]>=level[b]) a = par[a][i];
    }

    if(a==b) return a;

    for(ll i=log; i>=0; i--){
        if(par[a][i]!=-1 && par[a][i]!=par[b][i]) a = par[a][i], b = par[b][i];
    }

    return par[a][0];
}

void Func(ll a, ll b)
{
    ll mid = LCA(a,b), k, up, log = 0;
    up = level[a] + level[b] - 2*level[mid];
    k = level[a] - up/2;
    ///cout<<mid<<" "<<k<<"\n";
    if(level[mid]>=k){
        a = b;
        k = level[a] - up/2;
    }

    while(1){
        ll temp = log + 1;
        if((1<<temp)>level[a]) break;
        log++;
    }

    for(ll i=log; i>=0; i--){
        if(par[a][i]!=-1 && level[par[a][i]]>=k) a = par[a][i];
    }

    if(up%2){
        b = par[a][0];
        cout<<"The fleas jump forever between "<<min(a,b)<<" and "<<max(a,b)<<".\n";
    }
    else cout<<"The fleas meet at "<<a<<".\n";
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ///freopen("test.txt","w",stdout);
    ll n;

    while(cin>>n && n){
        ll a, b, q;

        for(ll i=1; i<n; i++){
            cin>>a>>b;

            v[a].push_back(b);
            v[b].push_back(a);
        }

        memset(visit, false, sizeof(visit));
        par[1][0] = -1;
        DFS(1,0);
        PreProcess(n);

        cin>>q;

        for(ll i=0; i<q; i++){
            cin>>a>>b;
            Func(a,b);
        }

        for(ll i=1; i<=n; i++) v[i].clear();
    }

return 0;
}

Update 1 : The contest is over

Update 2 : Final standings can be found here

Google's hiring contest,APAC Kickstart 2017 Round D is going to held on Sunday, July 16, 2017 05:00 UTC – 08:00 UTC

Ready to get started solving fun, challenging problems? Throughout the year, Code Jam hosts online Kickstart rounds to give students the opportunity to develop their coding skills, get acquainted with Code Jam’s competition arena, and potentially get noticed by Google recruiters, too. Participate in one—or join them all!

Attention!!!!

Google's hiring contest, Kickstart 2017 Round C is going to held on Sunday, June 25, 2017 19:00 UTC – 22:00 UTC.

Ready to get started solving fun, challenging problems? Throughout the year, Code Jam hosts online Kickstart rounds to give students the opportunity to develop their coding skills, get acquainted with Code Jam’s competition arena, and potentially get noticed by Google recruiters, too. Participate in one—or join them all!

Please visit here to join and fun!!!!

From today's(14-jun-17) morning we cannot access LightOJ(Light Online Judge) anymore. Can anyone access Lightoj?

UPDATE: LightOJ is available again. It was unavailable for heavy load of Contest. You can check it Here