By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,373 Members | 1,792 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,373 IT Pros & Developers. It's quick & easy.

need help understanding a c++ program

P: 3
In the program given below, i can't understand the working of the second for loop placed in the main function,especially, the first two loops inside the this loop. What is the role of "dp" and best "arrays". How are they working? This is the link of the problem:

https://www.hackerrank.com/challenges/two-subarrays


using namespace std;

//O(2/27 * (n A[i]^3))

const int sm = 18;
const int maxi = 3e5 + 5;
const int big = 1e7;
const int me = 40;
const int ms = 821;

int lg[maxi], a[maxi], st[sm], p[maxi][sm], dp[me + 1][ms], s[maxi], best[me + 1][ms];
int n;

void calc()
{
st[0] = 1;
lg[1] = 0;
for (int i = 1; i < sm; i++)
{
st[i] = st[i - 1] * 2;
lg[st[i]] = i;
}

for (int i = 2; i <= maxi; i++)
if (!lg[i])
lg[i] = lg[i - 1];
}

void update_sparse()
{

for (int i = 1; i < sm; i++)
for (int poz = 0; poz <= n; poz++)
if (s[p[poz][i - 1]] <= s[p[poz + st[i - 1]][i - 1]])
p[poz][i] = p[poz][i - 1];
else
p[poz][i] = p[poz + st[i - 1]][i - 1];

}

int get_min(int l, int r)
{
int range = (r - l) + 1;
if (s[p[l][lg[range]]] <= s[p[r - st[lg[range]] + 1][lg[range]]])
return p[l][lg[range]];
else
return p[r - st[lg[range]] + 1][lg[range]];
}

int main()
{
scanf("%d", &n);

calc();

p[0][0] = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
p[i][0] = i;
}

update_sparse();

int ans = 0;
int am = 0;
int len = 0;

for (int i = 1; i <= n; i++)
if (a[i] > 0)
{
dp[a[i]][a[i]] = i;
for (int j = a[i] + 1; j <= (a[i] * (a[i] + 1)) / 2; j++)
dp[a[i]][j] = best[a[i] - 1][j - a[i]];

for (int j = a[i]; j <= (a[i] * (a[i] + 1)) / 2; j++)
for (int k = a[i]; k <= me; k++)
best[k][j] = max(best[k - 1][j], dp[k][j]);

int lef = 0;
for (int k = ms - 1; k >= 0; k--)
if (best[me][k] > lef)
{
int idx = get_min(lef, best[me][k] - 1);
if (ans < s[i] - s[idx] - k)
{
ans = s[i] - s[idx] - k;
am = 1;
len = i - idx + 1;
}
else if (ans == s[i] - s[idx] - k && len > i - idx + 1)
{
len = i - idx + 1;
am = 1;
}
else if (ans == s[i] - s[idx] - k && len == i - idx + 1)
am++;

lef = best[me][k];
}
}
if (ans == 0)
am = n;
printf("%d %d\n", ans, am);

return 0;
}
Apr 14 '17 #1
Share this Question
Share on Google+
4 Replies


weaknessforcats
Expert Mod 5K+
P: 9,197
This code:
Expand|Select|Wrap|Line Numbers
  1.  
  2. const*int*maxi*=*3e5*+*5;
  3. const*int*big*=*1e7;
  4. *
  5.  
has problems before anything happens. 3e5+5 and 1e7 are in fact big numbers but the problem is they are big floating point numbers which are used to initialize ints which are very small in comparision. There will be truncation and loss of data so the values of maxi and big are indeterminate. Not good.

That means that the lg[maxi] array has indeterminate size as does any other array using maxi as a subscript.

Also, since the value of big is indeterminate you have no idea what will happens when the code runs and big is used in a comparison.

Your compiler should be producing warnings on these lines of code.

Next, all the arrays are on the stack and the size of stack frames is often limited so that your program may crash at run time for lack of stack memory.

The code does not compile.

BTW: the code is strict C code with no C++ used at all.
Apr 14 '17 #2

P: 3
no, the program is compiling just fine and there are no errors. I just need to understand the algorithmic steps taken in the second for loop. How are "dp" and "best" arrays working together and what kind of values they are producing. Like, i can tell the both dp and best are storing index positions and the subscripts of both array denote an integer in first dimension and the sum of all integers upto that integer in second dimension. But how are they calculating sum of increasing sub-sequence between an interval of array required to be subtracted from the sum of all elements in that interval to produce a maximum answer. The link of the problem statement is given. May be it will help if you go through the problem this code is used to solve. The code is written by the problem-setter itself.
Apr 15 '17 #3

weaknessforcats
Expert Mod 5K+
P: 9,197
I get these warnings:
Expand|Select|Wrap|Line Numbers
  1. 1>c:\scratch\bytes projects\question 2016-04-08\app.cpp(11): warning C4244: 'initializing' : conversion from 'double' to 'const int', possible loss of data
  2. 1>c:\scratch\bytes projects\question 2016-04-08\app.cpp(12): warning C4244: 'initializing' : conversion from 'double' to 'const int', possible loss of data
  3.  
They just confirm my previous post. The variables maxi and big have indeterminate values.

I suggest you include <limits> and call numeric_limits to get your max value then assign this value to your ints.

As to the rest of the code, since there are no comments describing what is going on, you are left with a step through debugging session(s) to figure out what the original programmer was doing. Unfortunately, I do not have time for this exercise.

I suspect the entire business of array handling is a duplication of the code in <vector>.
Apr 15 '17 #4

P: 3
I'm using the compiler, that came with dev c++, from the command line.It's not giving any warnings or errors. The executable is being produced just fine and is working as well.Anyways, thanks for the response.I really appreciate it. I'll see what else i can do.
Apr 16 '17 #5

Post your reply

Sign in to post your reply or Sign up for a free account.