amansbhandari Guys, below is the code in O(n) time complexity and O(1) Auxiliary space
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { long int N,K,p,q,sum,i,j,max=0,x=0; cin>>N>>K; long int *a=new long int[N+1](); for(i=0;i<K;i++) { cin>>p>>q>>sum; a[p]+=sum; if((q+1)<=N) a[q+1]-=sum; } for(i=1;i<=N;i++) { x=x+a[i]; if(max<x) max=x; } cout<<max; return 0; }amitkumarjnv2 Your approach is brilliant. Hats off
yugesh can you please explain the logic behind that.?
amitkumarjnv2 see, you are adding sum to a[p] and adding negative sum at a[q+1]. which make sure that when you add element from a[p] to a[q] sum is added only once and it should be subtracted at a[q+1] as this sum span from p to q only. Rest array element are either 0 or some other input sum. max of addition will be output. refer to above code for p, q, and sum.
amansbhandari [deleted]lancerchao Instead of storing the actual values in the array, you store the difference between the current element and the previous element. So you add sum to a[p] showing that a[p] is greater than its previous element by sum. You subtract sum from a[q+1] to show that a[q+1] is less than a[q] by sum (since a[q] was the last element that was added to sum). By the end of all this, you have an array that shows the difference between every successive element. By adding all the positive differences, you get the value of the maximum element
manjiri Important points to note in this solution.
1)the first element of array a will always remain zero since 1<= a <=b <=n; 2
2)the second element of array a is the second element of the array after m operations.
vineet_ahirkar Same solution translated in python -
n, inputs = [int(n) for n in input().split(" ")] list = [0]*(n+1) for _ in range(inputs): x, y, incr = [int(n) for n in input().split(" ")] list[x-1] += incr if((y)<=len(list)): list[y] -= incr; max = x = 0 for i in list: x=x+i; if(max<x): max=x; print(max)
jbwhite And the same approach in ruby -- I claim no credit for working this out -- I wrote this after reading the comments and code posted here.
Just thought I'd add a ruby solution for anyone looking for one.
N, M = gets.chomp.split(' ').map(&:to_i) # create array of zeros of length N + 1 arr = Array.new(N + 1, 0) M.times do # cycle through and get the inputs start, finish, value = gets.chomp.split(' ').map(&:to_i) # increment value at start of sequence arr[start - 1] += value # decrement value at first position after sequence arr[finish] -= value end tmp = 0 max = 0 arr.each do |value| # step through summing array tmp += value # capture the max value of tmp max = tmp if max < tmp end puts max
kaustubh_p16 Same solution in C
int main() { long long int n,k,i,max=0,x=0; scanf("%lld %lld",&n,&k); int *a=(int *)malloc(sizeof(int)*(n+1)); for(i=0;i<n;i++){ *(a+i)=0; } for(i=0;i<k;i++){ long long int c,d,g; scanf("%lld %lld %lld",&c,&d,&g); *(a+c)+=g; if(d+1<=n){ *(a+d+1)-=g; } } for(i=1;i<=n;i++){ x+=*(a+i); if(max<x){ max=x; } } printf("%lld",max); /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }
acdevbox1 Same solution in C#
using System; using System.Collections.Generic; using System.IO; class Solution { static void Main(String[] args) { string[] inString = Console.ReadLine().Split(' '); uint[] initParams = Array.ConvertAll(inString, UInt32.Parse); uint n = initParams[0]; uint m = initParams[1]; long[] numList = new long[n+1]; for(int i=0; i<m; i++) { string[] opString = Console.ReadLine().Split(' '); uint a = UInt32.Parse(opString[0]); uint b = UInt32.Parse(opString[1]); long k = long.Parse(opString[2]); numList[a] += k; if(b+1 <= n) numList[b+1] -= k; } long tempMax = 0; long max = 0; for(int i=1; i<=n; i++) { tempMax += numList[i]; if(tempMax > max) max = tempMax; } Console.WriteLine(max.ToString()); } }
jmgallagher Same solution in Java
Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int m = scan.nextInt(); //This will be the "difference array". The entry arr[i]=k indicates that arr[i] is exactly k units larger than arr[i-1] long[] arr = new long[n]; int lower; int upper; long sum; for(int i=0;i<n;i++) arr[i]=0; for(int i=0;i<m;i++){ lower=scan.nextInt(); upper=scan.nextInt(); sum=scan.nextInt(); arr[lower-1]+=sum; if(upper<n) arr[upper]-=sum; } long max=0; long temp=0; for(int i=0;i<n;i++){ temp += arr[i]; if(temp> max) max=temp; } System.out.println(max);
Sarthak10 [deleted]jmgallagher It is the same logic as mentioned above.
archanapradeep Hi i dont understand how the difference array works. What is the logic behind adding at one index and subtracting at the other and taking its sum?
boris93 You can try to visualize the array as steps / stairs
We are just noting down the bump ups and bump downs
chikmid I still havent understood this logic.Even though i implemented this logic in java with ease,i dont understand how this logic helps us arrive at the solution.
jricaldi me netheir, I am looking for the maths here, I am pretty sure the solution has a math method. Somebody here wrote "Prefix sum".
mvanwoerkom I tried an answer in the spirit of digital signal processing here.
coolcoder001 Hi , I have a doubt.
Here the indices are starting from 1. So, we should be subtracting 1 from both lower index and upper index. Here you have done so for lower index, but haven't done for upper index.
Can you please explain the reason behind this ?
xavier630 It's because it doesn't go back down until the element after the section ends.
eg: n = 4, a = 1, b = 2 k = 3. So we have 3 3 0 0 after reading in that line. In his array he represents this as 3 0 -3 0 ie the subtraction is the element after the last element in the section.
The reason the lower value has a "-1" is because java uses 0-indexed arrays, ie they start at 0. But the input for this question only starts at 1. So he puts the values one index lower in the array. The upper value has no "-1" for the reason in the above paragraph about subtracting after the last element in the section
sergioescala You don't have to do this:
for(int i=0;i<n;i++) arr[i]=0;
because long by default is 0
harshithakamma could you please explain me the working of the code?
JStardust i think test code bigger than long int,so we need a larger data structure
lavrikilya [deleted]
apivovarov no need to init array elements to 0 in Java
sbouzel Hi, your solution works but I am not convinced!
I don't see how do you increment all elements between lower and upper!
- arr[lower-1]+=sum; This only increments the lower element by sum.
- if(upper
- arr[upper]-=sum; I don't understand why are you substructing sum!
Can you please explain? Thanks.
jasonliuxz It's a difference array. He is storing the difference/the changes that should be made in each index and then runs a loop to add up all these changes. You increment the lower bound because everything inbetween the lower and upper bound should be incremented but you dont want this change to continue for the rest of the array so you decrement at (upper+1).
harshithakamma but how can we know about the upper index of a particular increment,when we are adding all at a once in a loop?
juank_luna Using Java 8 syntaxis:
public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); long[] output = new long[n]; IntStream.range(0,m).forEach(i -> { int a = in.nextInt()-1; int b = in.nextInt(); int k = in.nextInt(); output[a] += k; if(b < n) output[b] -= k; }); AtomicLong sum = new AtomicLong(0); System.out.print(LongStream.of(output).map(sum::addAndGet) .max().getAsLong()); in.close(); }
AlexisVaBel large amount of lines will crash your solution. And map fucntion need to make Boxing methinks and this takes much time
tranhoangha94 why temp += arr[i];
DanYoo940 Array is already 0, you dont have to assign 0s to each array elements
AlexisVaBel scanner on large lines of input is not suitable solution, it reads too long
Sufiyan You don't need to loop the arr to put 0. Bydefault, it has the value zero when you initialize.
Sufiyan In java, we don't need to loop explicitly to assign zero to all the arr locations. When we create it, it has the zero as default values. I like your solution, thanks.
izambl Same solution in javascript
function main() { let n_temp = readLine().split(' '); let n = parseInt(n_temp[0]); let m = parseInt(n_temp[1]); let res = []; let sum = 0; let max = 0; for (let i = 0; i<n; i++) { res[i] = 0; } for(var a0 = 0; a0 < m; a0++){ var a_temp = readLine().split(' '); var a = parseInt(a_temp[0]); var b = parseInt(a_temp[1]); var k = parseInt(a_temp[2]); res[a-1] += k; if (b<n) res[b]-=k; } for (let i=0; i<n; i++) { sum += res[i]; if (max < sum) max = sum; } console.log(max); }
Jeff_Chung123 very smart,here is follow output to help me understand the idea
Compilation Successful Input (stdin) 5 1 1 2 100 Your Output (stdout) Slope List [ 100, 0, -100, 0, 0 ] Actual List[100,100,0,0,0] Compilation Successful Input (stdin) 5 2 1 2 100 2 5 100 Your Output (stdout) Slope List [ 100, 100, -100, 0, 0 ] Actual List[100,200,100,100,100] Compilation Successful Input (stdin) 5 3 1 2 100 2 5 100 3 4 100 Your Output (stdout) Slope List [ 100, 100, 0, 0, -100 ] Actual List[100,200,200,200,100]
Jeff_Chung123 process.stdin.resume(); process.stdin.setEncoding('ascii'); var input_stdin = ""; var input_stdin_array = ""; var input_currentline = 0; process.stdin.on('data', function (data) { input_stdin += data; }); process.stdin.on('end', function () { input_stdin_array = input_stdin.split("\n"); main(); }); function readLine() { return input_stdin_array[input_currentline++]; } /////////////// ignore above this line //////////////////// function main() { var n_temp = readLine().split(' '); var listSize = parseInt(n_temp[0]); var lineNumber = parseInt(n_temp[1]); let slopList = new Array(); for(let i = 0;i < listSize;i++){ slopList.push(0); } for(var a0 = 0; a0 < lineNumber; a0++){ var a_temp = readLine().split(' '); const beginElementPos = parseInt(a_temp[0]); const endElementPos = parseInt(a_temp[1]); const addValue = parseInt(a_temp[2]); slopList[beginElementPos-1] += addValue; if (endElementPos<listSize){ slopList[endElementPos]-=addValue; } } let actualList = new Array(); let sum = 0; for (let i=0; i<listSize; i++) { sum += slopList[i]; actualList.push(sum); } let max = actualList.reduce((acc,val)=>{ return (acc>val)?acc:val; },0); console.log(max); }
ali_sid_jobs Guys, if you look for a clear understanding of the solution, I read a pretty clear comment down the road that clarified my mind.
Basically, when you add value from a to b you just need to know that it goes up from k and goes down of k after.
What this algo does is to register the slopes only, so we just need 2 entry, with O(1) complexity.
We just need to know that we are upping from k at the beginning and decreasing at the end.
Finally, the maximum would be...
The addition of all the slopes, that is why it's max(sum) of the tables, because the tables itself registers the slopes
mvanwoerkom [deleted]mvanwoerkom [deleted]
smaaash Thanks a lot!!That really helped!
agarwal_akshara9 Can you explain the concept of just adding add subtracting at a particular index? I mean how have we arrived to this logic?
ozgur24 I didnt well understand that what will happen if b+1 is out of array bounds?
hn5624 it can't be out of bounds, it saids that b>n in the problem statement.
rohitshende16 if b+1 > n then the the addition of k from position a will continue till the last element of the array.
hn5624 Jesus christ, it all makes sense now after that graph lol, I kept wondering what drug these people were taking to arrive at this conclusion.
nashrahmeraj i have got correct output of your test cases but 3 test cases of hackerrank are getting wrong. iam not understanding whats wrong.please help me
jishangarg brilliant idea!
davidyc what about the custom input:
5 1
1 5 -100
wouldn't the output be 0? But the max would be -100 since all elements would be -100.
eellor There's a constraint: 0 <= k <= 10^9
In your case of negative k, the minimum value can be obtained by the similar approach. Imagine a valley rather than a mountain.
kunalwww1994 why are you subtracting???? "( b < n ) res [ b ] -= k;"
umutesen How is your method faster than the following?
using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Numerics; class Solution { static void Main(String[] args) { string[] tokens_n = Console.ReadLine().Split(' '); int n = Convert.ToInt32(tokens_n[0]); int m = Convert.ToInt32(tokens_n[1]); // Instantiate and populate an array of size N BigInteger[] arr = new BigInteger[n]; for(int i = 0; i < n; i++) arr[i] = 0; for(int a0 = 0; a0 < m; a0++){ string[] tokens_a = Console.ReadLine().Split(' '); int a = Convert.ToInt32(tokens_a[0]); int b = Convert.ToInt32(tokens_a[1]); int k = Convert.ToInt32(tokens_a[2]); // Apply operation for(int j = a-1; j < b; j++) arr[j] += k; } Console.WriteLine(arr.Max(i=>i)); } }
avmohan The "Apply operation part" is O(k) here. In the diff array version, apply operation is O(1)
kunalwww1994 hey did u passed all with this...i used same logic in C#..but passes till 6
JStardust your database is int? some tests data is too big
zeeshanaslamonl1 your code is only passing 3 test cases out of 10 . Don't post the code unless it pass all the test cases dude !!!!
rajesh_kashyap60 bro, this is a discussion forum. Why are you demotivating a begineers ? Anyway I have submitted that code successfully. Thanks for the advice.
fateme_hajizade I used the same logic, it passes most of the tests but I get timeout error.
intechworx if(b+1 <= n) numList[b+1] -= k;
Why we are substracting?
kashifali2005 It is failing test case 4 to 13. Not sure why
kashifali2005 It is failing test case 4 to 13. Can you please check
148W1A05B1 *(a+c)+=g; if(d+1<=n){ *(a+d+1)-=g; }
please explain what's going on here.harshithakamma could you please explain me the logic?
julie_larson This worked, but I'm still trying to understand why this was the correct answer.
mishyn Because it takes less time to execute. Otherwise solution execution got time outed
victortang_com You are not answering the question.
thatsamorais I would not suggest eclipsing
listShubhamV06 Can some one please help as to why my solution gives a segmentation fault?
include
include
include
include
int main() {
unsigned long long int n,m,l,b,k,i,val=0; scanf("%llu%llu",&n,&m); unsigned long long int a[n+1]; for(i=1;i<=n;i++) { a[i]=0; } while(m--) { scanf("%llu%llu%llu",&l,&b,&k); for(i=l;i<=b;i++) { a[i]+=k; if(a[i]>val) { val=a[i]; } } } printf("%llu",val); return 0;}
dr_cooper Maximum array size has to be 10^7 which is not possible in case of C. I tried Dynamic memory allocation (malloc) which worked but got TLE for bigger test cases
ShubhamV06 yeah it is getting a tle. We need to use a different algorithm. I wanted to know what the problem in my code was so i posted my solution.
vicky_20 use long instead of int.
PratikDreamer Hi Vineet could u explain what logic have you followed?
timkay Same solution but optimized:
from itertools import accumulate n, m = map(int, input().split(' ')) dx = [0] * (n + 1) # allow run past end for _ in range(m): a, b, c = map(int, input().split(' ')) dx[a - 1] += c dx[b] -= c print(max(accumulate(dx)))
kai_gowers That's so good! You are awesome!
ygrinevich can you explain why it's (n+1) and not (n)?
Jellofish The question asks for a 1 indexed list and the a,b values read in are read in starting from 1 not 0. If you do not use (n+1)if b happens to be the last number of your list it will go out of bounds.
The 0 index value will always be 0 so it doesn't affect your answer when you sum for max difference.
kunalwww1994 why are you subtracting dx[b] -= c ?????
vietanhtran_96 The use of accumulate is so brilliant!
tug16183 How does that bottom for list return the maximum value in the list? Could you explain the logic to me please?
sonic88bt Why are you checking if "y" is <= len(list) ? This is given by the problem, right?
AamirAnwar Really liked this solution! One question, shouldn't it be max=-float('inf')?
P.S - Talking about the python version
gg_germain Just improved your code a bit. - split() is slightly faster than split("") - an if was not needed as always true - variables names fit those used in the exercise
if __name__ == "__main__": n, m = [int(n) for n in input().split()] l = [0]*(n+1) for _ in range(m): a, b, k = [int(n) for n in input().split()] l[a-1] += k l[b] -= k; max = a = 0 for i in l: a+=i; if max<a: max=a; print(max)
Etiennera [deleted]GhostlyMowgli I took the ideas explained here to put also into python in a bit more spelled-out way to help make sense of this more abstract work-around.
def arrayManipulation(n, queries): # Big O (N) res = [0]*(n+1) # we only really need one terminal row, since we're applying each pass to all rows below # loop through all the queries and apply the increments/decrements for each # Big O (M) (size of queires) for row in range(len(queries)): a = queries[row][0] b = queries[row][1] k = queries[row][2] res[a-1] += k # increment the starting position # this is where a loop would increment everything else between a & b by k # but instead of taking b-a steps, we take a constant 2 steps, saving huge on time res[b] -= k # decrement the position AFTER the ending position # now loop through res one time - Big O (N) (size of res) sm = 0 # running sum mx = 0 # maximum value found so far for i in range(len(res)): sm += res[i] if sm > mx: mx = sm # total run time is Big O (2*N + M) >> Big O(N) return mxThe key concepts in my opinion here are:
1) we don't need to build the full aray, since it's impossible for any row but the last to have the max value. This is impossible because we apply the adjustments to every subsequent row of the resulting 2-D array.
2) we don't need to actually increment each value for indices 'a' through 'b'. While that's the most straight-forward way, that also requires x many (a minus b) steps for each pass of the loop. By noting instead where to start incrementing and where to stop incrementing (noted by decrementing after what would be the final increment), we can note the adjustments to apply without having to take every step each time. We can then run a separate single loop to go over each of the increments and keep a running sum of all the overlapping increments. The decrement allows us to know when that range where the increment applied is over by reducing the running sum by that number - in other words when that range is ended, we would have to look at overlapping increments excluding that one that just ended going forward to see if anything is bigger.
Someone else in here gave an image of a stair/hill which I found extremely helpful in visualizing and understanding this concept. The basic idea here is that instead of actually applying each increment, we can just note what the increment and range is and one by one go through each place and apply all the compounded increments at once. Loop 1 saves the increments in a different format, Loop 2 checks the overlap. And by using two separate loops we have basically Big O (N) rather than Big O (N^2) - or more specifically Big O (2N + M) instead of Big O (NM + N), where N is the size of the resulting array and M is the size of the queries array.
nivdatta88 I still have some doubt if anyone could explain it. I understand that it is making use of difference array to keep track of the difference between items rather than updating every item.
However as I understand, size of difference array is one less than total items in the actual array.
So as per the demo program given,
ARR DIFF (5,3) 0 0 0 0 0 0 0 0 0 (1,2) 100 100 0 0 0 0 -100 0 0 (2,5) 100 200 100 100 100 100 -100 0 0 (3,4) 100 200 200 200 100 100 0 0 -100
However the logic used seems to be a variant of difference array that I am not able to understand. It would be great if someone could help me connect the dots from this difference array to the actual working solution of this problem. Thanks.
zeralight Hello, I don't really get your DIFF representation, but here is the deal:
you need to keep in mind that at the end of queries to get the real value of i we need to sum the values of A[0]->A[i].
for a query (l, r, x) if we add x to A[l] then we're sure later for every k in [l, r] sums(0->k) will include x.
the problem is that every k > r will also include that x, therefore we'll decrement l[r+1] by x.
Now the sum through 0 -> k will include x only if k >= l and will exclude it only if k > r which is equivalent to:
sum(0->k) will consider x only if k is in [l, r]
d_niladri95 [deleted]
julie_larson I think the DIFF matrix should be:
0 0 0 0 0 100 0 0 -100 0 0 100 0 0 0 0 0 100 0 -100then x is 100+100+100-100-100 = 200
still don't quite get it though
cse160001033 [deleted]cyxingfa I think the Diff should like this
0 0 0 0 0 100 0 -100 0 0 <--- 1 2 100, 3rd col is 100 less than 2nd col 100 100 -100 0 0 <--- 2 5 100, 2nd col is 100 more than 1st col 100 100 0 0 -100 <--- 3 4 100, now 3rd is equal to 2nd, and 5th is 100 less than 4th col
so finally, 1st col is always the real value, and others are accumlated of previous values and it self. so actual values are 100 200 200 200 100, max is 200
marc_ponchon Thanks this helps me to understand how it works.
feynman65 @julie_larson
100+100+100-100-100 = 100 still not 200 I've been banging my head still not able to understand this solution.filipetrm The final diff array should be like this:
100 100 0 0 -100 (straight foward from the code)
So when you iterate over it to get the accumalated sum you'll get this:
iteration value of x accumulated sum 0 0 0 1 100 100 2 100 200 3 0 200 4 0 200 5 -100 100
The maximum value of the accumulated sum is 200.
nayeemnawaz93 As i have understood (5 , 3) 0 0 0 0 0 (1 , 2) 100 100 0 0 0 -> first and second places i.e a=1,b=2 , k=100, now a+k = 0+100 = 100, b+K = 0+100 = 100. (2 , 5) now from 2 to 5 i.e 2,3,4,5 are added with K i.e 100. already 2=100 now 2 becomes 100+100 =200, simialrly 3 = 0+100=100,4=0+100=100,5=0+100=100. (3 , 4) now 3 and 4 are added with 100. ie 3 value is 100 it becomes 100+100=200, 4 becomes 100+100=200.
among these 200 is max value.
cse160001033 instead of writing long int *a=long int[n+1] if I write long int a[n+1]; It shows segmentation fault after test case 7. why? Explain please.
Alex_leo yes ,the same with you, i am confused
julie_larson you aren't allocating space for a that way. He uses new to create an array on the heap. You are trying to declare it on the stack, but you can't do that with a dynamic value like 'n'
ami3443 As per my knowledge, u can create an array to size upto 10^6 in stack and for size above it we need to create in heap so we do it dynamically. https://discuss.codechef.com/questions/28604/maximum-size-of-an-array refer this
ShubhamV06 Thanks @ami3443
kousiknandi Nice explanation.
RuraDund If you have a problem understanding dynamic memory then make use of vector . It allocates memory dynamically wherein the user doesn't have to deal with pointers .
vector arr(n); declares an array of long int of length n.
nivdatta88 [deleted]
sandeep007734 Thanks for explaining the logic behind this.
tanyaangra123 Here ,I add all the positive values of the difference array to get the maximum element . But , the answer comes out to be wrong for all the test cases except sample one ...
prakash_katudia Use long int in place of int.
manishch1095 what do u mean by previous element? is it a[p-1]for a[p] or the previous state of a[p] before the current updation operation? difference is betweentwo succesive elements or in the same element before and after one query is executed?
tanyaangra123 It is a[p-1] for a[p] ie. the difference between two successive elements.
Well ,now ,i understood my mistake . I was just adding the positive differences. But the problem requires maximum element in an array , so there must be a comparison while adding the differences.
Well thanks!
tanujindal1989 wonderful explaination...Thanks a lot
chaizhongzhong Hi gabriel
chikmid how is element at b+1 the previous element?
shivamckaushik Your Explanation is wrong and misleading.Logic behind @ amansbhandari algorithm is at any index p he is storing by how much this value is more than previous value, subsequently if value from p to q is 100(to be exact 100 more than other values) q+1 should be 100 less than values between p and q.That is why we subtract 100 at q+1 index of array.
adi928 That's it. Thanks for a simpler explanation.
akashjus The solution works, but how did you came to this theory ?
guangzefrio That's what I understand this theory. We can try to understand this logic like we imagine Supermario walking on a N width horiz line. a and b is the point on the line, k is the mushroom Mario like to eat. When Mario go to the point at a,he eat the k size mushroom and become taller,after he have walked through point b, his height reverse to the origin height before he eat the mushroom. eg. 1. When Mario is walking to a, he eat a k size mushroom, and become k bigger 2. Then Mario is walking to a', he eat a k' size mush, and become k' bigger, now Mario's height is (k + k') 3. If Mario have walked to b, so he pooped out the mushroom and become k smaller, the only way that he can become larger is to meet a new (a,b) point and eat a new k size mushroom 4. The rest can be done in the same manner.
What we need to do is tracing the Mario's biggest height when walking through that muliple query's a and b point.
ayu111 awesome explanation.. btw i wanted to ask if this is what we call segment tree..and if we can use this method to solve questions with the segment tree tags.. P.S. : I have a very little knowledge about the segment trees.
Thanks in advance.
nikhiljain1222 you can refer top coder or either gog to understand the concept of segment tree. ;)
ayu111 acha bhai :D
nikhiljain1222 haha.. ;)
vventura This is literally the only reason I actually was able to understand the logic of the code. Thank you for that, seriously.
leong1568 Very nice explanation. The explanation in the question does misleading on how to implement the solution.
rawshar_bhardwaj Thanks a lot for your explanation, it really simplified the problem. :)
rhuang23 ahaha great explanation, thanks so much!
vaib95 i dont get why did you subtract from q+1th element?
gauravkochar_gk sorry dear ,I dont get it .Plz tell me, how do you think about this logicc....
sarbajitnandey Check your code with this inputs
i/p: 7 2 1 5 100 2 3 500
Anirudh_K Why is my code not working on the same approach ? Please help Can't find anything wrong !
include
include
using namespace std;
int main(){
int N,M,a,b,c; cin>>N>>M; long int *arr=new long int[N+1]; for(int i=0;i<M;i++){ cin>>a>>b>>c; arr[a]+=c; if(b+1<=N){ arr[b+1]-=c; } } int x=0,ans=0; for(int i=1;i<=N;i++){ x+=arr[i]; ans=max(ans,x); } cout<<ans;return 0; }
mtkocak keep an eye on edges.
Anirudh_K Still No Clue!
vadim_tarasov Try to change
for(int i=1;i<=N;i++){
to
for(int i=0;i<=N;i++){
guangzefrio We can try to understand this logic like we imagine Supermario walking on a N width horiz line. a and b is the point on the line, k is the mushroom Mario always like to eat. When Mario go to the point at a,he eat the k size mushroom and become taller,after he have walked through point b, his height reverse to the origin height before he eat the mushroom. eg. 1. When Mario is walking to a, he eat a k size mushroom, and become k bigger 2. Then Mario is walking to a', he eat a k' size mush, and become k' bigger, now Mario's height is (k + k') 3. If Mario have walked to b, so he pooped out the mushroom and become k smaller, the only way that he can become larger is to meet a new (a,b) point and eat a new k size mushroom 4. The rest can be done in the same manner.
What we need to do is tracing the Mario's biggest height when walking through that muliple query's a and b point.Ea9Le Best explanation, thanks.
surajkumar000787 here we are taking the difference of highest number and lowest number that is the loging has been implemented here. you could see in the peice of code to finding max value at each iteration adding the next element to the value (x=x + a[i]).
ryetika It took me a while to understand as well, but its pretty brilliant actually. First let me explain why this approach is good: You have k operations acting on a range of [a,b], for each of these k operations, a could be 1 and b = n , that makes a normal (add sum to 'a' through 'b') solution O(k * n ).
In this solution for each of the k operations, you make exactly 2 operations, so its constant time for each k operation. At the end, you go through the entire n length array and get the largest. That makes it a O(k) + O(n) operation ==> much cheaper
Now, on to the solution itself, assume the array size, n = 10 lets take operations to be(lowerIndex upperIndex sumToBeAdded): oper1: 1 5 3 oper2: 4 8 7 oper3: 6 9 1
initially your array looks like (array of size n + 1): 00000000000
after 1 5 3 : 0 3 0 0 0 0 -3 0 0 0 0
after 4 8 7 : 0 3 0 0 7 0 -3 0 0 -7 0
after 6 9 1 : 0 3 0 0 7 0 -2 0 0 -7 -1
so, that is O(k) where we processed the array, now for the magic... as we iterate through the n elements, keep adding a running sum, the running sum at each index will give you the final value that was supposed to be at that index (had you added the oper's sum to 'a' through 'b' for each of the k operations...)
on filling all elements of array[n+1] with the running sum and noting the largest, the array transforms to : 0 3 3 3 10 10 8 8 8 1 0 , and this happends in O(n) time
and the largest value at any index is 10
Hope this makes it easier to understand...
az3749 Agree. Although I used segmented tree, it was no need to know max on each step. Amansbhandari in fact used dirac delta and theta functions instead.
warrior_of_light Does using segment tree worked?
Did you get all AC?
jainy6 I usedlazy propogation , worked fine.
themast3r I too tried Lazy Propagation but got segmentation fault after 6 test cases, even the Question Setter in the editorial says that Lazy Propagation can not pass all test cases. Please show the code you wrote which passed all the test cases.
jainy6 [deleted]
siddharthp538 I got AC using Segment tree with lazy propagation. http://ideone.com/DzZlW7. Just keep on updating the tree, and at each node store the maximum of its left and right child. And after all the k updates, apply Range maximum query.
mvanwoerkom Just noticed your comment. I came to the same conclusion here
coder_a brilliant mind ....
harshahj97 thanks
harshahj97 thanks
cse160001033 instead of long int *a=long int[n+1] if we write long int a[n+1]; It shows segmentation fault.why?
tonarimochi because 'n' is too large to allocate for static array. (the maximum size of static array is different by complier). so we allocate dynamic array of size 'n+1'.
gaurav999 What a approach. Not easy to think this kind of approach.
tyagisagar79 Please explain it to me in the simplest form you can
zeralight you mean O(n+k). nice solving
kehacker any comments on to improve this pthon code to use greedy algorithm I time out for the later cases. Thanks
N, M = map(int,raw_input().split()) lst = [0]*N
for _ in range(M): a, b, k = [int(n) for n in raw_input().split(" ")]
for i in range(a-1,b): lst[i] += kprint max(lst)
jairo222 you should create a generator because when the test it have big number of queries your program delay too much.
len_array, queries = map(int, raw_input().strip().split()) array = [0]*len_array def generator_queries(queries): init = 0 index = 0 while index < queries: yield map(int, raw_input().strip().split()) index += 1 for a, b, k in generator_queries(queries): for i in xrange(a-1,b): # another generator array[i] += k # maybe use threads here print max(array)
julie_larson I tried this, but it still could not make it past Test 5, the rest timed out
cse160001033 [deleted]
tyler_christian2 A generator doesn't buy anything. Test 7 - end still fail due to timeout.
This will do the same thing and still fail due to timeout.
N, M = [ int(input) for input in raw_input().strip().split() ] arr = [0] * N for _ in range( M ): a, b, k = [ int(input) for input in raw_input().strip().split() ] for x in xrange( a-1, b ): arr[x] +=k print max( arr )
Implementing the C++ solution from the top level comment in Python 2.7 can be done as this ( changing out a few bits that don't make sense ):
N, M = [int(n) for n in raw_input().split()] arr = [0]*N for _ in range( M ): a, b, k = [int(n) for n in raw_input().split() ] arr[a-1] += k if b <= ( N - 1 ): arr[b] -= k my_max = x = 0 for i in range( N ): x += arr[i] if my_max < x: my_max = x print( my_max )
pythonmaniac Same logic (thanks!) with constraits addressed.
def algoCrush(): try: listSize, opsCount = map(int, raw_input().split()) except: return None #constraint 1 and 2 if not all([listSize >=3, listSize <= 10**7, opsCount >= 1, opsCount <= 2*10**5]): return None crushList = [0]*listSize for _ in range(opsCount): try: start, end, addnum = map(int, raw_input().split()) except: return None #constraint 3 and 4 if not all([start >= 1, start <= end, end <= listSize, addnum >= 0, addnum <= 10**9]): return None crushList[start-1] += addnum if end <= (listSize -1): crushList[end] -= addnum prev = high = 0 for i in range(listSize): prev += crushList[i] if high < prev: high = prev print high algoCrush() For instance, when list size less than 3, it should not return any thing. 2 3 1 2 3 1 2 3 1 2 3 9 -----> should have failed. Likewise, when there are strings in numbers. 2 3 1 2 3 1 2 3 1 2 str Traceback (most recent call last): File "a.py", line 4, in <module> a, b, k = [int(n) for n in raw_input().split() ] ValueError: invalid literal for int() with base 10: 'str'
thngkaiyuan pure genius!
vineet_ahirkar Truely!
sam1064max There is nothing greedy about this algorithm.
paras_gupta BTW O(n) is slower here as compared to O(MlogM). N = 1e7 (worse), M = (log(2e5)*2e5)/log(2) ~ 3.5e6 :P
hacker_am1xh53a Not exactly slower, if we look at the constants behind O-s. Say, we sort events, there are 4e5 of them, so we get log(4e5)*4e5/log(2)=7.44e6, the difference became not so drastic. And sort at any step uses conditional operations that, when incorrectely predicted, break the CPU conveyer. That costs about 10 ticks each time. And they would be incorrectely predicted in about 50% cases, that is expensive. The proposed approach is straightforward, the only conditional is "if ( max < x ) max = x" that probably would be saturated fast, that is in most cases it would not be taken, and CPU would be able to predict that.
About numbers: my sorting approach runs in 0.01-0.02s, this approach in my implementation runs in 0.03-0.04s on strong testcases. That is probably because we have to use quite a lot of (random access) memory, 80MB instead of 3.2MB in the sorting approach, and it leads to cache misses and TLB trashing. HugeTLB could help a bit, had it been turned on on the testing server.
the_pirhana [deleted]
ravi9236151 Seriously Brilliant approach. Really appreciate it.
Baradwaj_Aryasom awesome.........
Tutankhamun Great solution!
I don't think I could ever have come up with something like that!
Is this considered a greedy solution?
One thing I did change was to make the array size N+2 and skipped the bounds check.
vineet_ahirkar Yes, N+2 is required, otherwise gives an out of bounds error!
jonathan_r Surely that's O(N) space. There's no need to store the array itself. Just record the update boundaries along with the k value (-k for the end boundary), sort them by location (then by value if at the same location), then scan over them with a running total.
tomade Yes, that makes more sense and saves on memory and running time. Using a defaultdict in Python:
from collections import defaultdict sums = defaultdict(int) _, n_ranges = (int(x) for x in input().split()) for _ in range(n_ranges): start, stop, value = (int(x) for x in input().split()) sums[start] += value sums[stop+1] -= value max_val = running_val = 0 for _, val in sorted(sums.items()): running_val += val max_val = max(max_val, running_val) print(max_val)
Chainly it is great that we don't have to store every key.
rajasanwir_iitk1 n, m = input().strip().split(' ') n, m = [int(n), int(m)] l = [0] * (n+1) for a0 in range(m): a, b, k = input().strip().split(' ') a, b, k = [int(a), int(b), int(k)] l[a:b+1] = list(map(lambda x:x+k,l[a:b+1])) print(max(l))
The above code is showing runtime error for test case 7 onwards. please suggest the reason?
david_barkhuizen I experience the same issue. If I run test case 13 locally, my code passes, but if I try the same code remotely on HR, cases 7 -> 13 all fail. Out of memory ?
pulkitpahwa I too tried the same approach. Yes, It's giving runtime error.
pawan_231 [deleted]
adk96r That is awesome man!
sudip_95 Great Approach, man! :D
Wanna know something! Is there any classic name of this approach? Can anyone give some links to other problems which is similar to this problem? I think, I've seen this type of problem before, but can't remember where and couldn't solve then also!
maximshen Very elegant ! I am totally speechless. Thank you. For those who are still confused or not quite understand, please the link http://codereview.stackexchange.com/questions/95755/algorithmic-crush-problem-hitting-timeout-errors
manjiri This code finds the maximum possible subarray sum. and the maximum sum is the answer. This means that we assume that atleast 1 element in the array will be 0. Is that necessary??
pankaj_mittal372 awesome!!
xperienceshekhar Can any one explain why static allocation gives segmentation fault in some cases?
giaym Wouldnt have came up with the idea, I was using partitions..., although I didnt actually see code the explanations below were enough to make a light bulb pop!
Voldizard I tried using an integer vector with the same approach. The only difference being vector int a(n+1); instead of long int *a=new long intN+1;
It did not work. Wrong answer on TCs 5 to last. The same happened on using long int vector instead of int. Could somebody enlighten me as to why?
giaym int vs long int?, overflow then
Voldizard No, I used vectors of both int and long int and they both didn't work. The dynamic array worked.
xperienceshekhar Yeah,the same happened to me. Dint get it.
zutianluo did u figure it out?
26piyushkedia26 great one.I never comment but this code and your approach made me do so.Really was awsomely done..
caogtaa Very very nice code. I wrote a low efficient segment tree and get time limit for some test cases. Your solution just enlighten me a lot.
tmosest Simply amazing..... Your answer put the Editorial's to shame......
rajeev11430 Absolute Awesomeness.
z_axis [deleted]
piyushmishra Did it pass all test cases?
juanmf you can try it, it passes.
juanmf I came out with the same approach in java, but code is ridiculously larger :P
import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * Created by juanmf on 08/02/17. */ public class AlgorihmicCrush { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner s = new Scanner(System.in); int N = s.nextInt(); int M = s.nextInt(); //int[] operations = new int[N + 1]; List<Long>[] operations = new List[N + 1]; while (s.hasNextInt()) { int from = s.nextInt(); int to = s.nextInt(); long sum = s.nextLong(); addOperation(operations, from, to, sum); } System.out.println(copmileOperations(operations)); } private static long copmileOperations(List<Long>[] operations) { long crawler = 0; long max = Integer.MIN_VALUE; for (List<Long> ops : operations) { if (null == ops) { continue; } for (Long op : ops) { crawler += op; } if (max < crawler) { max = crawler; } } return max; } private static void addOperation(List<Long>[] operations, int from, int to, long sum) { if (null == operations[from]) { operations[from] = new ArrayList<Long>(); } operations[from].add(sum); to++; if (to >= operations.length) { return; } if (null == operations[to]) { operations[to] = new ArrayList<Long>(); } operations[to].add(-sum); } }
hl2kerg I also did it on Java. At first, it only passed up to test 3, due some precision loss, having int k instead of long k. This may be obvious to many here, but I still thought it was interesting to see how such a small detail changes it all. Here is the code (in comments, the code with int, which fails after test 3).
import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;
public class Solution {
public static void main(String[] args) { int N, M, a, b; long k; // int k; Scanner in = new Scanner(System.in); N = in.nextInt(); M = in.nextInt(); long[] differenceArray = new long[N+1]; // int[] ... for (int i=0; i<M; i++) { in.nextLine(); a = in.nextInt(); b = in.nextInt(); k = in.nextLong(); // in.nextInt(); differenceArray[a] += k; if (b+1<=N) differenceArray [b+1] -= k; } long max = 0, addedDifference = 0; // int for (int i=1; i<=N; i++) { addedDifference = addedDifference + differenceArray[i]; if (max < addedDifference) max = addedDifference; } System.out.println(max); in.close(); }}
manoranjan03 Can you explain this line
differenceArray[a] += k; if (b+1<=N) differenceArray [b+1] -= k; }
Why are you adding k to only differenceArray[a]??
hl2kerg Let's view the array as a list of histograms. Each position in the array has a histogram with a certain variable heigth. It would be cumbersome to keep track of the heigth of every single histogram. Instead, you could just keep track of how much the height of a given histogram differs from the one preceding it (in a continuous setting, this would mean to keep track of the derivative of a function, not the function itself).
Here, we know there is an increment of k for the height of the histogram in position a (a positive slope of k from a-1 to a), but then the height remains constant at positions a+1, a+2,...,b. Then again, we know that position b was the last position where histograms were incremented by k, so there is a decrement of -k at position b+1 (negative slope of -k from b to b+1).
Hope this helps.
juanmf you can check it out in the assumptions area. if int values can be more than 2**30 or you can have many accumulated in one int. etc..
mjhere Thank you so much, I too was stuck for that small reason for hours together!! Thaks allot;)
kiranTanush nice
karan_300986 same thing happened to me ..using int instead of long
TheCodeHere [deleted]
rnikhill Awesome solution, but it's worth pointing out that this is O(n) auxillary space, not O(1)
JimB6800 Nice algorithm. However I'd prefer if you described your approach, rather than posting your code. (This would also avoid people asking "can you explain your logic".) Leave the coding as an excercise for the reader :)
JimB6800 I ended up using a TreeMap. Since there can only be 400K inflection points max, it seemed wasteful to create an array of 10M values and then traverse the 10M values to compute a result. So this results in a time of O(M log M). As others have mentioned, the additional constant time is much higher than
long[], so it's hard to estimate the actual performance difference. This would really win if M was small (and N large), and is time/space independent of N. (The code reads and discards N.)
martymagaan [deleted]
rshaghoulian Your solution is O(n+m) runtime and O(n) space complexity, which is slower than what you mentioned in your post, but is still great. The O(n+m) is a result of the fact that m may be larger than n. The space complexity is due to you creating an array of size n.
I do the same in my efficient Java solution.
hsaad9119 The runtime complexity is O(N) because M upper bound (2 * 10^5) is lower than N upper bound and even if it was equal (M upper bound = N upper bound), it would be O(N+N), which is O(2N), which could be reduced to O(N).
rshaghoulian I usually analyze runtimes assuming variables are unbounded. I find it to be more useful that way since HackerRank usually creates arbitrary bounds for variables.
In the bounded case, you are correct, you can consider it to be O(N).
Potatoswatter Only O(M) space is needed. The question was tagged "sparse arrays" but this is a brute-force, dense array.
if((q+1)<=N)is unnecessary because[N+1]space is allocated.
martam Sorry, but this is just bruteforce. Your code runs in O(n), but the input is O(M). By creating the array in code (which is not part of the input) you are using exponential memory and runtime (because the length of N is logarithmic compared to the actual length of the array).
See my anwser for a better idea about the solution.
Rinkesh_G Amazing solution @amansbhandari great work.
dekoder moron we are'nt suppossed to discuss solutions!
ajenal Brilliant!
dipesh_jain Amazing! Hats off.
z_axis [deleted]rshaghoulian If the problem statement is exactly the same, and you were asked to find the minimum, you simply loop through the array using Math.min() instead of the Math.max() in the last loop in this solution.
z_axis [deleted]rshaghoulian The resulting array will have all M operations performed on it. We can find the max/min/mean/median/mode, whatever we want, since it's just an array of final values. I can take a look at your code (if you want to alter this solution to see why it didn't work.
tarun_khari great approach. i don't understand the logic but still approach is outstanding in terms of complexity.
rshaghoulian Hi. Here's a detailed explanation of the logic that I wrote. My solution uses the same concept as above. Hope this helps.
shahzad73 Excellent dear. i was F***N stuck with for loops and not getting out
mpatel25 its genius!
aviben Will this for case if range given is 1 5 500 1 3 500
phinix I could understand that we are tracking start(a) and end(b) points and in between them all are sum of K. But i couldn't understand the last loop. Can anyone please explain why summing the array will work for our solution?
majormf chapeau
taniadiasr hatts of indeed but huge spoiler :/
Alex_leo From your solution,I turely konw that I love coding! How amazing it is!
tonarimochi I hope this explanation helps you to understand algorithm.
If we draw a[]'s value into 'line graph', then the graph will looks like a mountain. (each a[n]'s value will indicate the height.)
Imagine the mountain tracking from left to right, and 'max' stores the maximum height.
starting point 'p' means go up / end point 'q+1' means go down. then, just adding p and q+1, we can know the current height(which is 'x'). and what we need to do is just find the maximum height.
(oh, this website's image upload is very bad..)
luca_guarro How do people think of this shit
vadim_tarasov My solution, O(M*log(M)):
#include <cstdint> #include <map> #include <iostream> int main() { std::uint64_t N; std::uint64_t M; std::cin >> N; std::cin >> M; std::int64_t max = 0; std::uint64_t A; std::uint64_t B; std::uint64_t k; std::map<std::uint64_t, std::int64_t> points; for (std::uint64_t i = 0; i < M; ++i) { std::cin >> A; std::cin >> B; std::cin >> k; points[A] += k; points[B + 1] -= k; } std::int64_t value = 0; for (auto it = points.begin(); it != points.end(); ++it) { value += it->second; if (value > max) { max = value; } } std::cout << max; return 0; }
It is not necessery to store full array. It is sufficient to store only begins and ends of all intervals (A and B). For example, if you have 10^7 elements and one operation, you need only 2 points, not 10^7. But in some languages (for example pure C) you will need to implement someone ordered container with fast insert operation, for example ordered List.
pbsderil Great...!!!
mtkocak Here is the PHP code of this solution. Teached me a lot. Thanks.
<?php $_fp = fopen("php://stdin", "r"); /* Enter your code here. Read input from STDIN. Print output to STDOUT */ fscanf($_fp, "%d %d", $size, $operations); $array = []; $max = PHP_INT_MIN; for($i=0; $i<$operations; $i++){ fscanf($_fp, "%d %d %d", $start, $end, $value); $negativeValue = $value * -1; if(!isset($array[$start])) $array[$start] = $value; else $array[$start] += $value; if($end+1<=$size){ if(!isset($array[$end+1])) $array[$end+1] = $negativeValue; else $array[$end+1] -= $value; } } ksort($array); $sum = 0; foreach($array as $amount){ $sum += $amount; if($sum>$max) $max=$sum; } echo $max; ?>
albertgaya New on this site and having hard time with this task. Luckily found your comment and found my mistake. here's my short version of yours
<?php $_fp = fopen("php://stdin", "r"); $_fp2 = fopen('php://stdout', 'w'); /* Enter your code here. Read input from STDIN. Print output to STDOUT */ fscanf($_fp, "%d %d", $n, $m); $r = []; for($i=0; $i<$m; $i++){ fscanf($_fp, '%d %d %d', $a, $b, $k); $r[$a] += $k; $r[$b+1] -= $k; } ksort($r); $max = $sum = 0; foreach ($r as $val) { $sum += $val; if ($sum > $max) { $max = $sum; } } fwrite($_fp2, $max); ?>
kirilangov I think a little cleaner PHP solution:
<?php fscanf(STDIN, '%d %d', $n, $m); $list = []; for ($i = 0; $i < $m; $i++) { list($a, $b, $k) = explode(' ', trim(fgets(STDIN)), 3); $list[$a-1] = ($list[$a-1] ?? 0) + $k; $list[$b] = ($list[$b] ?? 0) - $k; } ksort($list); $running_total = 0; $max = 0; foreach ($list as $value) { $running_total += $value; $max = max($max, $running_total); } print $max;
deanar My Solution is the similar, but it can not pass testcases 7-13, because "Runtime Error".
I downloaded input\output data for 7th testcase and it's pass locally.
What is wrong?
$handle = fopen ("php://stdin", "r"); fscanf($handle, "%i %i", $n, $m); $h = array_fill_keys(range(0, $n), 0); for($a0 = 0; $a0 < $m; $a0++){ fscanf($handle, "%i %i %i", $a, $b, $k); $h[$a-1] += $k; $h[$b] -=$k; } $prev = 0; $max = PHP_INT_MIN; foreach($h as $value){ $prev += $value; if($prev > $max) $max = $prev; } echo $max;
finnr_rastas You fill the whole array, probably it's not enough memory
ahmedsohailanwa1 How did u think of this!! Saying its brilliant is understating it. Its genius!
abhaynayar Unused variable j.
i_code_prime out of box thinking..hats off..
bdchambers79 While I appreciate the elegance of your solution, the fact that the solution is posted in the very first comment is rather disappointing.
The purpose of these exercises is not to copy and paste someone else's solution, but rather to get to the answer on your own. To that end, these discussions shouldn't just be code that you copy and paste.
gauranggoel_9 can you explain me please i m having problem to understand why did you do this ???
gk_dobariya Superb...... Same I implemented in JS
function processData(input) { let arr = input.split('\n'); const NM = arr[0].split(' ').map(Number); const N = NM[0]; const M = NM[1]; let obj = {}; for (let i = 1; i <= M; i++) { const abk = arr[i].split(' ').map(Number); const a = abk[0]; const b = abk[1]; const k = abk[2]; obj[a] = obj[a] ? obj[a] + k : k; obj[b+1] = obj[b+1] ? obj[b+1] - k : (k*-1); } delete(obj[N+1]); let MAX = 0; let X = 0; for (const key in obj) { X += obj[key]; if (MAX < X) MAX = X; } console.log(MAX); }
daiict_201501200 Hats of Sir... maja aa gaya
rhliyy You sir are genius . !
Quantiestein Brilliant !!
Roaneno Someone's probably mentioned, but to avoid using O(n) space, you can use a sparse data structure like a map.
import qualified Data.Map.Strict as M import Data.List (foldl') main = do getLine -- skip the first line, we won't use N or M input <- map readWords . lines <$> getContents -- lazily read operations let ops = foldl' insertOperation M.empty input print $ findMax ops readWords = map read . words insertOperation m [a, b, k] = (M.insertWith (+) a k) . (M.insertWith (+) (b+1) (-k)) $ m findMax :: M.Map Int Int -> Int -- Result is >= 0 findMax m = snd $ M.foldl' update (0, 0) m where update = \(cur, peak) x -> let next = cur + x in (next, max peak next)
gaurav999 Brilliant approach
ravi_anethama7 Awesome approach....!
surbhi_16 seriously brilliant approach!!!!!!!!
adarsh97 perfect man,you are awesome......
timkay If you make the "a" array longer by 1, you can get rid of the "if" in the inner loop.
EmberQuill Oh that is clever. Very very clever. I was brute-forcing it (running every operation in full on every element from a to b) and every test from Test 5 onward was timing out.
Here's my Python 3 implementation of your solution:
n,m = map(int, input().split())) numbers = [0] * n value, maxval = 0,0 for _ in range(m): a, b, k = map(int, input().split()) numbers[a-1] += k if b < n: numbers[b] -= k for number in numbers: value += number if value > maxval: maxval = value print(maxval)
Scipsycho Your solution is simply amazing!!! I spent an whole hour scratching my head thinking about disjoint sets!! Here I what wrote it in C++ using map better allocation.
define ll long long int
using namespace std;
int main() { ll n,m,a,b,k; cin>>n>>m; map arr; while(m--){ cin>>a>>b>>k; if(arr.find(a)==arr.end()) arr[a]=0; arr[a]+=k; if(arr.find(b)==arr.end()) arr[b]=0; arr[b+1]-=k; } ll max=0,x=0; map::iterator i; for(i=arr.begin();i!=arr.end();i++){ x+=i->second; if(x>max){ max=x; } } cout<
Thanks man!! I was thinking to quit but your answer gave me spirit to keep continuing.
manish99_ranjan1 This method is also known as "Prefix sum method"
Sayan95Roy Your solution is elegant:-In java:-
import java.util.*; public class AlgorithmicCrush { public static void main(String[] args) { int n,m,a,b,k; Scanner in=new Scanner(System.in); n=in.nextInt(); m=in.nextInt(); long arr[]=new long[n]; long max=0,x=0; for(int i=0;i<m;i++) { a=in.nextInt(); b=in.nextInt(); k=in.nextInt(); arr[a-1]+=k; if(b<=n-1) arr[b]-=k; } for(int i=0;i<n;i++) { x+=arr[i]; if(max<x) max=x; } System.out.print(max); } }
PS:-I really liked that your indexing goes from 1 to n in the array of size n+1.It's intuitive.Maybe that's a norm.Anyways,gonna learn more. :)
lahouari A java version:
public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int M = in.nextInt(); int[] arr = new int[N]; int a; int b; int k; while (M-- > 0) { a = in.nextInt() - 1; b = in.nextInt(); k = in.nextInt(); arr[a] += k; if (b < N) arr[b] -= k; } in.close(); long max = Long.MIN_VALUE; long sum = 0; for (int value : arr) { sum += value; if (sum > max) { max = sum; } } System.out.println(max); }
sreevathsagowru My machine (local) is giving me 2147473274 but the expected answer is 2497169732. Any idea why this is happening?
reasonet Interesting. For anyone who doesn't understand, let's assume that we know a maximum is at position i in the list. We know that the intervals that don't include i will not contribute to the calculation of i. If we add a spike at the start of a interval, and subtract the spike from right after the interval, then when you add the two spikes together, you will get zero, which is what we want to happen if i is not in that interval. As intervals overlap, there will be multiple positive spikes followed by multiple negative spikes. When you add the positive spikes together, you find a local maximum, and then when you add the negative spikes, you descend from that maximum. The global maximum can thus be found by traveling along the spikes and comparing local maximums. It's almost like you're adding the impulse response of each interval. This solution is not obvious.
xcourtesy10 Thank you so much
Bryan4code hats off, how did u come up with such a speachless solution, can u point out some books or fileds i can learn, thanks.
codedeepesh if((q+1)<=N) a[q+1]-=sum;
why are you doing this can someone explain this to me?
shiwanggupta [deleted]
m7md_7ssien How is it in O(1) Auxiliary space althoug you initialize array of n+1 long ints here
long int *a=new long int[N+1]();
you may use dictionary to shrink the used space.
IshanSarode brilliant approach... just used simple data structuring approach
iam_ss I think that your space complexity is not O(1) but O(n) because you are creating an array of size n which is not given in the input. So, you are basically creating an array for solving your question, so the auxilliary time complexity is O(n). Please correct me if I am wrong!
yww325 Yes, that's indeed an anwser, the test is about your observation and math. Now I understand what those company want.
rishabh_iitkgp long int *a=new long int[N+1]();
Q.1 What is the use of simple brackets? Q.2 How to intialize a all with zeroes? Q.3 How to create an empty sequence a?
alan_chen222 Actually, we can only store the edge elements to reduce memory cost from O(n) to O(m). In Java, we can use SortedMap (e.g. TreeMap) to do that (java8)
import java.io.*; import java.util.*; import java.util.Map.Entry; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); TreeMap<Integer, Integer> map = new TreeMap<>(); for (int a0 = 0; a0 < m; a0++) { int a = in.nextInt(); int b = in.nextInt(); int k = in.nextInt(); map.put(a, map.getOrDefault(a, 0) + k); if (b + 1 <= n) { map.put(b + 1, map.getOrDefault(b + 1, 0) - k); } } in.close(); long max = map.firstEntry().getValue(); long sum = 0; for (Entry<Integer, Integer> e : map.entrySet()) { sum += e.getValue(); if (sum > max) { max = sum; } } System.out.println(max); } }
mvh_tembor brilliant solution.......... bt in [if((q+1)<=N)] y "<=N" ??? shdt it be N+1 ????
ayush146235 What is the name of this algorithm?
ayush146235 Can yo please tell the name of this approach so that i can read about it in further depth?
george_jost i see. it works, although im surprised doing it the dumb way, which is what i did fails the tests. how big could their test case be?
edwardgmc What happen if q == N, will this solution still work?
george_jost Yep. F
aggarwalaakash01 awesome solution <3
JStardust [deleted]
aliakhtar49 [deleted]rajesh_kashyap60 "long int " is fine why not "int is working here ?
mvanwoerkom [del
Sort 545 Discussions, By:
Please Login in order to post a comment