algorithm - Maximum sum in a torus -


i trying solve following dynamic programming question on uva online judge:

a grid wraps both horizontally , vertically called torus. given torus each cell contains integer, determine sub-rectangle largest sum. sum of sub-rectangle sum of elements in rectangle. grid below shows torus maximum sub-rectangle has been shaded.

image of torus

we know there exists similar , simpler problem: maximal sub-rectangle problem grid canot wrap. simpler variant, can first take cumulative of each row , apply kadane's algorithm in 2 for-loops solve problem. problem, impossible since grid can wrap around.

i have headstart on problem mirroring matrix 4 times simulate rotation of matrix. however, dynamic programming related problems, have formulate recurrence relation. not know how formulate recurrence problem. please advise me?

edit:

i tried using modified kadane's algorithm search largest rectangle of @ least size 1. however, still not getting right answer. reference, code listed below: 

#include <cstdio> #include <algorithm> #include <list> using namespace std;  int main() {     int cc,r,c,r,c,inf = 9999;     scanf("%d",&cc);     while(cc--) {         scanf("%d",&r);         c = r;         r = c = 2 * r;         int l[r][c], sum[r+1][c];         fill_n(sum[0],c,0);          for(int = 0; < r; i++) {             for(int j = 0; j < c; j++) {                 scanf("%d",&l[i][j]);                 sum[i+1][j] = l[i][j];                 sum[i+1][c+j] = l[i][j];                 sum[r+i+1][j] = l[i][j];                 sum[r+i+1][c+j] = l[i][j];             }         }         for(int = 0; < c; i++) {             for(int j = 1; j < r+1; j++) {                 sum[j][i] += sum[j-1][i];             }         }         int g_max = -inf;         for(int = 0; < r; i++) {             for(int j = i+1; j < i+r+1; j++) {                 int t_max = sum[j][0]-sum[i][0], s = sum[j][0]-sum[i][0], l = 1, lo = 0, hi = 0;                 g_max = max(g_max,t_max);                 for(int k = l; k < c; k++) {                     s += (sum[j][k]-sum[i][k])-(sum[j][k-l]-sum[i][k-l]);                     t_max = max(t_max+(sum[j][k]-sum[i][k]),s);                     if(t_max > g_max) {                         g_max = t_max;                         lo = k - l - 1;                         hi = k;                         if(hi - lo == c-1) break;                     }                 }             }         }         printf("%d\n",g_max);     }     return 0; }

given test case:

1 5 1 -1 0 0 -4 2 3 -2 -3 2 4 1 -1 5 0 3 -2 1 -3 2 -3 2 4 1 -4

the grid in test case shown above. answer should 15. getting 24. not sure wrong algorithm since implemented kadane's algo stackoverflow answer. able me?


Comments

Post a Comment

Popular posts from this blog

c# SetCompatibleTextRenderingDefault must be called before the first -

i tried search exception couldn't find solution on case i'am using code below invoke .net application : assembly assem = assembly.load(data); methodinfo method = assem.entrypoint; var o = activator.createinstance(method.declaringtype); method.invoke(o, null); the application invoked has form , in entrypoint of application : [stathread] static void main() { application.enablevisualstyles(); application.setcompatibletextrenderingdefault(false); //exception application.run(new form1()); } setcompatibletextrenderingdefault must called before first iwin32window object created in application. edit : assembly = assembly.load(data); methodinfo method = a.gettype().getmethod("start"); var o = activator.createinstance(method.declaringtype); method.invoke(o, null); you should create new method skips initialization...
Read more

C#.NET Oracle.ManagedDataAccess ConfigSchema.xsd -

i'm not able find config schema file (configschema.xsd) of oracle.manageddataaccess itellisense in application configuration file. it supposed in odp.net managed driver files cannot find it... configschema.xsd xml schema file defines configuration section odp.net, managed driver. https://docs.oracle.com/cd/e48297_01/doc/win.121/e41125/installodpmd.htm after having installed oracle developer tools visual studio 2015, seems 2 schema files have been linked app.config file : oracle.dataaccess.common.configuration.section.xsd oracle.manageddataaccess.client.configuration.section.xsd both stored in : c:\program files (x86)\microsoft visual studio 14.0\xml\schemas
Read more

c++ - Fill runtime data at compile time with templates -

i have specific situation in prepare runtime structures @ compile time without need duplicate code. i have 2 structs use register @ compile time types compiler wrote: using typeid = u8; template<typename t, typename type_id, type_id i> struct typehelper { static constexpr type_id value = std::integral_constant<type_id, i>::value; }; template<typename t> struct type : typehelper<t, u8, __counter__> { static_assert(!std::is_same<t,t>::value, "must specialize type!"); }; these used in config header macro specialize type<t> multiple types require: using type_size = unsigned char; #define get_nth_macro(_1,_2,_3, name,...) name #define register_type(...) get_nth_macro(__va_args__, register_type3, register_type2, register_type1)(__va_args__) #define register_type1(_type_) register_type2(_type_, _type_) #define register_type2(_type_,_name_) \ constexpr typeid type_##_name_ = __counter__; \ template<> struct type<_type_...
Read more