**** Problem: longest sub-array having sum at most k?

If all the array elements are positive then this problem is easily solvable using two pointers. for ex:

Let's say the array look like this a=[10,30,40,7,1] and k=48.

Solution: We keep two pointers l and r and we will always expand our sub-array with rth pointer and shrink from lth pointer

Iterations:

l=0,r=0 a[l---r]= 10 since 10<=48 we update our ans as 1 and we increment the rth pointer l=0,r=1 a[l---r]= [10,30] since 10+30<=48 we update our ans as 2 and we again increment the rth pointer. l=0,r=2 a[l---r]= [10,30,40] since 10+30+40>48 we will shrink our window by incrementing the lth pointer untill sum<=k. ie [10,30,40] to [30,40] still sum>k so we reduce the window to [40] l=2,r=2 a[l----r]=40

l=2,r=3 a[l---r]= [40,7] since 40+7<=48 we increment the rth pointer l=2,r=4 a[l---r]= [40,7,1] since 40+7+1<=48 we update our answer as 3.

This problem is also covered in the two pointers section in code forces edu.

But the problem with this algorithm is it does not work if the array contains negative elements because we are not assure that shrinking the window size always make our sum less positive as our lth pointer can be very big negative value as well. Thus removing the lth pointer here makes our sum more positive.

for ex: a=[-5,-4,-3,16,1,-6,-4,50] and k=3

In above example we can clearly see that the subarray[0,6]=[-5,-4,-3,16,1,-6,-4] is longest having sum<=3

But if we go by above algorithm we will not get this as our answer because when our rth pointer reaches 16 ie a=[-5,-4,-3,16] sum=4>k so we will shrink our window to [-4,-3,16] sum=9>k again we will shrink window to [-3,16] still sum>k.At the end we will be left with empty window ie l=r=3.

Now here we will not get accurate answer as l is increased to 3.

For this problem the only solution that comes into mind is O(N*N) ie trying all poss sub-arrays and checking whether sum<=k and finding largest.

If anyone have a better way of solving this please suggest.Thanks in advance.

I am learning vardiac functions and i See two different ways of writing vardiac functions.I m confused which one is best and whats the actual difference between them.

// CODE ---------------------------------------------------------------------------------------

include<bits/stdc++.h>

using namespace std;

// TYPE 1 template<typename... T> void print1(T... args) { ((cout << args << " "), ...); }

// Base empty function void print2() { cout << "\n"; return; }

// TYPE 2 template<typename Head, typename... Tail> void print2(Head H, Tail... args) { cout << H << " "; print2(args...); }

int main() { int x = 5; int y = 6; int z = 7; int r = 4; print1(x, y, z, r); print2(x, y, z, r);

}

// CODE--------------------------------------------------------------------------------------------------------------------

Print 1 and Print 2 both functions accept variable no of arguments.Both will print exact same ans.But in print2 function we are use something like a base empty function Which preserves for last call to the function in call stack.In print1 function We are not using any base function.I want to know the difference between these two functions.

PROBLEM LINK:https://codeforces.net/contest/1468/problem/C

When i am taking int to long long the verdict is :RUNTIME ERROR ON TEST 39 When i am taking int:Its getting accepted

Runtime Error submission Link:https://codeforces.net/contest/1468/submission/126266278

Accepted Solution Link:https://codeforces.net/contest/1468/submission/126266726

WHAT IS THE CAUSE OF RUNTIME WHEN I AM TAKING INT TO LONG LONG.Please explain.

I am always take my int to long long.After this incident i will be scared to take int to long long.Please Help

THANKS IN ADVANCE

PROBLEM LINK:https://codeforces.net/contest/1553/problem/B

my solution to this problem got hacked during the contest after it passes the pretests(4).I want to know is there a possibility suppose the hacker didnt hack my solution during the contest and in system testing my solution get accepted because the tests prepared for the question was not good enough or lets say it excludes the test case through which the hacker hacked.??

Also i want to know after somebody succesfully hack other solution do code forces add that particular hack test to their set of tests for system testing or code forces set of tests already has that test case covered.?? please answer

Thanks in advance

PLease explain why 2 same codes are not giving the same ans

code forces round 728 div2 Problem B :https://codeforces.net/contest/1541/problem/B

AC Submission : https://ide.codingblocks.com/s/579800

Wrong output Submission :https://ide.codingblocks.com/s/579801

Difference is using of macro (node) instead of pair<int,int>

Please help

If i am using #define node pair<int,int> it is getting accepted but when i am using typedef pair<int,int> node; it is giving wrong answer

Why this is happening ?? Is it a bug??