On Wednesday, January 28, 2015 at 7:09:55 PM UTC+5:30, Luke Pebody wrote: > The crux of this solution is in the recursive function Rec. I have rewritten > this with easier to read variable names and with commenting at > > > http://ideone.com/TNrdFO > > > Essentially it recursively goes through all ways of separating these into at > most k sets, finds the minimum square size needed for each way and then > outputs the best one it has found. > > > > On Wed, Jan 28, 2015 at 12:31 PM, sujit <[email protected]> wrote: > > > Hi, > > > > I am not able to understand the solution of Square Fields problem. > > > > Problem - https://code.google.com/codejam/contest/32004/dashboard#s=p1 > > > > Can you please explain below given solution for this problem (in detail)? > > > > -------------------------------------------------------------------------------------------------------------------------- > > Solution - > > -------------------------------------------------------------------------------------------------------------------------- > > > > #define _CRT_SECURE_NO_DEPRECATE > > #include <cstdio> > > #include <algorithm> > > #include <iostream> > > using namespace std; > > > > int N,kk,n,res,j; > > int x[100],y[100]; > > int mnx[100],mny[100],mxx[100],mxy[100]; > > > > > > void inline Rec(int i, int k, int sz) > > { > > > > if (k<=kk && sz<=res) > > { > > if (i==n) > > { > > res=min(res,sz); > > } > > else > > { > > for (int j=0; j<=k; ++j) > > { > > int omnx=mnx[j],omny=mny[j],omxx=mxx[j],omxy=mxy[j]; > > mnx[j]=min(mnx[j],x[i]); > > mny[j]=min(mny[j],y[i]); > > mxx[j]=max(mxx[j],x[i]); > > mxy[j]=max(mxy[j],y[i]); > > Rec(i+1,max(k,j+1),max(sz,max(mxx[j]-mnx[j],mxy[j]-mny[j]))); > > mnx[j]=omnx,mny[j]=omny,mxx[j]=omxx,mxy[j]=omxy; > > > > } > > } > > } > > } > > > > int main() > > { > > #ifndef ONLINE_JUDGE > > freopen("B-small-attempt0.in", "r", stdin); > > freopen("output.txt", "w", stdout); > > #endif > > scanf("%d",&N); > > for (int ii=0; ii<N; ++ii) > > { > > scanf("%d%d",&n,&kk); > > for (int i=0; i<n; ++i) > > scanf("%d%d",&x[i],&y[i]); > > for (int i=0; i<100; ++i) > > mnx[i] = mny[i] = 1000000, > > mxx[i] = mxy[i] = -1000000; > > res=1000000; > > Rec(0,0,0); > > printf("Case #%d: %d\n",ii+1,res); > > } > > return 0; > > } > > ---------------------------------------------------------------------------------------------------------------------------------------- > > > > Thanks, > > Sujit > > > > -- > > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > > To post to this group, send email to [email protected]. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/72ca9ae5-d9c9-4fab-b879-39539de73fae%40googlegroups.com. > > For more options, visit https://groups.google.com/d/optout.
Hi Luke, Thanks for your solution, can you please elaborate "Essentially it recursively goes through all ways of separating these into at most k sets, finds the minimum square size needed for each way and then outputs the best one it has found." -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/b0a71dca-9b64-439f-915b-bc294ba26bc4%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
