We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
here is a dp solution with O(N) time complexity. Space complexity is O(1) as it uses 8 long variables for any problem size of N.
To not obscure the calcuation in the codes, all values that was supposed to be a long type is replaced by a ModValueT type. All % 1000000007 operation is then done inside the ModValueT.
/*given the city-i, which connects 4 city-(i-1) together.denote each city_{i-1} city as W,X,Y,ZW Y| |n--m| |X Zgiven theseS_{i-1}: sum of all node-pair distances in city_{i-1}N_{i-1}: number of nodes in city_{i-1}E_{i-1}: sum of all distance from every node to the exit node in city_{i-1}L_{i-1}: the diagonal path length in city_{i-1}denote W_i=sum(n<->W) is sum of all paths between W and n, which isW_i = d(0,n) + d(1, n) + d(2, n)+ ... = d(0,e)+(e,n) + d(1,e)+d(e,n) + ... = E_{i-1} + N_{i-1}*d(e,n) = E_{i-1} + N_{i-1}*A_idenote WX_i=sum(W<->X) is sum of all paths between W and X citiesWX_i = d(w0,n,x0) + d(w0,n,x1) + ... d(w1,n,x0) + d(w1,n,x1) + ... = N_{i-1}*d(w0,n) + X_i + N_{i-1}*d(w1,n) + X_i + ... = N_{i-1}*W_i + N_{i-1}*X_i = N_{i-1}*W_i + N_{i-1}*W_i // as X_{i-1} == W_{i-1} = 2*N_{i-1}*W_idenote WY_i=sum(W<->Y) similarlyWY_i = d(w0,n,m,y0) + d(w0,n,m,y1) + ... d(w1,n,m,y0) + d(w1,n,m,y1) + ... = N_{i-1}*d(w0,n,m) + Y_i + N_{i-1}*d(w1,n,m) + Y_i + ... = N_{i_1}*(W_i + N_{i_1}*A_i) + N_{i-1}*Y_i = N_{i-1}*W_i + N_{i-1}*Y_i + N_{i-1}^2*A_i = 2*N_{i-1}*W_i + N_{i-1}^2*A_idenote WZ_i=sum(W<->Z) similarlyWZ_i = 2*S_{i-1} + d(w0,n,m,z0) + d(w0,n,m,z1) + ... + d(w1,n,m,z0) + d(w1,n,m,z1) + ... = WY_isoS_i = W_i + W_i+N_{i-1}*A_i + // sum(W<->n) + sum(W<->n<->m) X_i + X_i+N_{i-1}*A_i + // sum(X<->n) + sum(X<->n<->m) Y_i + Y_i+N_{i-1}*A_i + // sum(Y<->n) + sum(Y<->n<->m) Z_i + Z_i+N_{i-1}*A_i + // sum(Z<->n) + sum(Z<->n<->m) A_i + WX_i + WY_i + WZ_i + XY_i + XZ_i + YZ_i + 4*S_{i-1} = 4*W_i + 4*(W_i + N_{i-1}*A_i) + A_i + WX_i + WY_i + WY_i + WY_i + WY_i + WX_i + 4*S_{i-1} = 8*W_i + 4*N_{i-1}*A_i + A_i + 2*WX_i + 4*WY_i + 4*S_{i-1}alsoE_i = E_{i-1} + // city-Z W_i+N_{i-1}*(d(n,m,exit)+L_{i-1}) + // city-W X_i+N_{i-1}*(d(n,m,exit)+L_{i-1}) + // city-X Y_i+N_{i_1}*(d(m,exit)+L_{i-1}) + // city-Y d(n,m,exit) + L_{i-1} + // node-n d(m,exit) + L_{i-1} // node-m = E_{i-1} + W_i+N_{i-1}*(2*A_i+L_{i-1}) + W_i+N_{i-1}*(2*A_i+L_{i-1}) + W_i+N_{i_1}*(A_i+L_{i-1}) + 2*A_i + L_{i-1} + A_i + L_{i-1} = E_{i-1} + 3*W_i + N_{i-1}*(5*A_i + 3*L_{i-1}) + 3*A_i + 2*L_{i-1}alsoL_i = 2*L_{i-1} + 3*A_iand finallyN_i = 4*N_{i-1} + 2initially for i=-1S_{-1} = 0N_{-1} = 1E_{-1} = 0L_{-1} = 0*/classModValueT{public:constexprstaticconstlongINF=1000000007;ModValueT():value(0){}ModValueT(longv):value(v%INF){while(value<0){value+=INF;}value%=INF;}ModValueToperator+(constModValueT&mv)const{returnvalue+mv.value;}ModValueToperator*(constModValueT&mv)const{returnvalue*mv.value;}explicitoperatorint()const{returnvalue;};friendostream&operator<<(ostream&os,constModValueT&mv){assert(mv.value>=0l);os<<mv.value;returnos;}friendModValueToperator*(constsignedv,constModValueT&mv){returnmv*v;}friendModValueToperator+(constsignedv,constModValueT&mv){returnmv+v;}private:longvalue;};inthackerrankCity(vector<int>A){usingvalue_t=ModValueT;constexprintLEN=2;array<value_t,LEN>S;array<value_t,LEN>N;array<value_t,LEN>E;array<value_t,LEN>L;autoIdx=[LEN](inti){return(i+LEN)%LEN;};S[Idx(-1)]=0;N[Idx(-1)]=1;E[Idx(-1)]=0;L[Idx(-1)]=0;for(inti=0;i<(signed)A.size();++i){// E_{i-1} + N_{i-1}*A_ivalue_tWi=E[Idx(i-1)]+N[Idx(i-1)]*A[i];// 2*S_{i-1} + 2*N_{i-1}*W_ivalue_tWXi=2*N[Idx(i-1)]*Wi;// 2*S_{i-1} + 2*N_{i-1}*W_i + N_{i-1}^2*A_ivalue_tWYi=2*N[Idx(i-1)]*Wi+N[Idx(i-1)]*N[Idx(i-1)]*A[i];// 8*W_i + 4*N_{i-1}*A_i + A_i + 2*WX_i + 4*WY_i + 4*S_{i-1}S[Idx(i)]=8*Wi+4*N[Idx(i-1)]*A[i]+A[i]+2*WXi+4*WYi+4*S[Idx(i-1)];// E_{i-1} + 3*W_i + N_{i-1}*(5*A_i + 3*L_{i-1}) + 3*A_i + 2*L_{i-1}E[Idx(i)]=E[Idx(i-1)]+3*Wi+N[Idx(i-1)]*(5*A[i]+3*L[Idx(i-1)])+3*A[i]+2*L[Idx(i-1)];// 2*L_{i-1} + 3*A_iL[Idx(i)]=2*L[Idx(i-1)]+3*A[i];// 4*N_{i-1} + 2N[Idx(i)]=4*N[Idx(i-1)]+2;// cout << "S[" << i << "]=" << S[Idx(i)] << endl;// cout << "L[" << i << "]=" << L[Idx(i)] << endl;// cout << "N[" << i << "]=" << N[Idx(i)] << endl;// cout << "E[" << i << "]=" << E[Idx(i)] << endl;}return(int)S[Idx(A.size()-1)];}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
HackerRank City
You are viewing a single comment's thread. Return to all comments →
here is a dp solution with
O(N)
time complexity. Space complexity isO(1)
as it uses 8long
variables for any problem size ofN
.To not obscure the calcuation in the codes, all values that was supposed to be a
long
type is replaced by aModValueT
type. All% 1000000007
operation is then done inside theModValueT
.