Welcome, Guest: Join Nairaland / LOGIN! / Trending / Recent / NewStats: 2,549,677 members, 5,874,345 topics. Date: Wednesday, 23 September 2020 at 07:39 PM

## Competitive Programming - Programming - Nairaland

(1) (2) (3) (Reply) (Go Down)

 Competitive Programming by pseudonomer: 12:35am On Jul 28 Lately, I’ve been involved in lots programming interviews which involves a lot of data structures and algorithm questions. I discovered practice and practice and practice is all I need. I’m using this thread to challenge myself to solve at least two problems per day. Others can join me too.Key to Success: Strong Background in Data Structure and Algorithm, and Logic Mathematics. Languages: C++, and sometimes Java. Others can use Python. Re: Competitive Programming by Deicide: 7:33pm On Jul 28 Never knew Nigerians were interested in Competitive programming. 1 Like Re: Competitive Programming by Nobody: 2:06am On Jul 29 Following Re: Competitive Programming by Karleb(m): 3:30am On Jul 29 Let's start with this 1 Like Re: Competitive Programming by tensazangetsu20(m): 5:47am On Jul 29 Karleb:Let's start with this The question looks weird. Why 5 and not 6. 11-5. Isn't the goal of selling stocks to get profit. Why not gain more profit. If I had this question the first thing I will do is to sort the array. Then I would loop through the array twice for every loop I will subtract the preceding number from the oncoming number and place that in a constant and return the highest number. The only problem with loops is the time complexity o(n). Re: Competitive Programming by Karleb(m): 7:29am On Jul 29 tensazangetsu20:The question looks weird. Why 5 and not 6. 11-5. Isn't the goal of selling stocks to get profit. Why not gain more profit. If I had this question the first thing I will do is to sort the array. Then I would loop through the array twice for every loop I will subtract the preceding number from the oncoming number and place that in a constant and return the highest number. The only problem with loops is the time complexity o(n).I believe your brute force approach will increase the time complexity to O(n2) since you are looping twice. 1 Like Re: Competitive Programming by Karleb(m): 7:40am On Jul 29 For those that love the challenge. Re: Competitive Programming by tensazangetsu20(m): 9:17am On Jul 29 Karleb:I believe your brute force approach will increase the time complexity to O(n2) since you are looping twice. Oh yes. Thanks for the correction on that. Re: Competitive Programming by clockwisereport: 10:33am On Jul 29 Karleb:Let's start with this This is clearly a DP problem.i will post the solution when i charge my laptop Re: Competitive Programming by clockwisereport: 10:40am On Jul 29 tensazangetsu20:The question looks weird. Why 5 and not 6. 11-5. Isn't the goal of selling stocks to get profit. Why not gain more profit. If I had this question the first thing I will do is to sort the array. Then I would loop through the array twice for every loop I will subtract the preceding number from the oncoming number and place that in a constant and return the highest number. The only problem with loops is the time complexity o(n).The aim of the problem is to make maximise profit.You can decide to buy/sell on the day of your choice.If you buy on the first day at 9 units and sell on the second day, you make a gain of 2 units.if you buy on the second day and decide to sell on the subsequent days, you make a loss of 3, 6, 4 and 1 unit respectively.If you buy on the third day at 8 units, you make a loss of 3 and 1 units on the 4th and 5th day and a gain of 2 units on the 6th day.if you buy on the 4th day at 5 units, you make a gain of 2 and 5 units on the 5th and 6th day respectively.if you buy on the 5th day at 7 units and sell on the 6th day, you make a gain of 3 units by selling in the 6th day.As clearly seen, you make the highest gain when you buy on the 4th day at 5 units and sell on the 6th day at 10 units 4 Likes 1 Share Re: Competitive Programming by tensazangetsu20(m): 11:47am On Jul 29 clockwisereport:The aim of the problem is to make maximise profit.You can decide to buy/sell on the day of your choice.If you buy on the first day at 9 units and sell on the second day, you make a gain of 2 units.if you buy on the second day and decide to sell on the subsequent days, you make a loss of 3, 6, 4 and 1 unit respectively.If you buy on the third day at 8 units, you make a loss of 3 and 1 units on the 4th and 5th day and a gain of 2 units on the 6th day.if you buy on the 4th day at 5 units, you make a gain of 2 and 5 units on the 5th and 6th day respectively.if you buy on the 5th day at 7 units and sell on the 6th day, you make a gain of 3 units by selling in the 6th day.As clearly seen, you make the highest gain when you buy on the 4th day at 5 units and sell on the 6th day at 10 unitsAmazing way to think about the problem. How would you go about solving it then? 1 Like Re: Competitive Programming by Nobody: 12:10pm On Jul 29 What are the input constraints for the problems?E.g1 < The size of the array < 10^6Having constraints gives an idea of how efficient your algorithm should be. Like for the second question you could go for a brute Force approach that runs in O(n^2) time, but that would be horribly inefficient for an array of size 10^6, so you would have to come up with something more clever. But if the problem is simply just make a function with no regard of its speed, then that makes things much easier. 1 Like Re: Competitive Programming by Karleb(m): 2:54pm On Jul 29 clockwisereport:This is clearly a DP problem.i will post the solution when i charge my laptopI will be expecting it. I like the level of engagement on this thread. I guess I'll post another problem tomorrow. Re: Competitive Programming by Karleb(m): 2:57pm On Jul 29 clockwisereport:The aim of the problem is to make maximise profit.You can decide to buy/sell on the day of your choice.If you buy on the first day at 9 units and sell on the second day, you make a gain of 2 units.if you buy on the second day and decide to sell on the subsequent days, you make a loss of 3, 6, 4 and 1 unit respectively.If you buy on the third day at 8 units, you make a loss of 3 and 1 units on the 4th and 5th day and a gain of 2 units on the 6th day.if you buy on the 4th day at 5 units, you make a gain of 2 and 5 units on the 5th and 6th day respectively.if you buy on the 5th day at 7 units and sell on the 6th day, you make a gain of 3 units by selling in the 6th day.As clearly seen, you make the highest gain when you buy on the 4th day at 5 units and sell on the 6th day at 10 unitsI duff my hat for you. You should take up the role of a lecturer! Re: Competitive Programming by DrLevi: 3:15pm On Jul 29 if I got the question correctly then this should work. I can't guarantee efficiency or speed tho since I don't know algorithms terms like O[n2] or all that stuff`arr = [9, 11, 8, 5, 7, 10]def buy_and_sell(arr): sorted_arr = sorted(arr) buyAt = sorted_arr[0] slicedArr = arr[arr.index(buyAt): ] slicedArr.sort() sellAt = slicedArr[-1] return sellAt - buyAt print(buy_and_sell(arr))` 1 Like Re: Competitive Programming by Karleb(m): 3:35pm On Jul 29 DrLevi:if I got the question correctly then this should work. I can't guarantee efficiency or speed tho since I don't know algorithms terms like O[n2] or all that stuff`arr = [9, 11, 8, 5, 7, 10]def buy_and_sell(arr): sorted_arr = sorted(arr) buyAt = sorted_arr[0] slicedArr = arr[arr.index(buyAt): ] slicedArr.sort() sellAt = slicedArr[-1] return sellAt - buyAt print(buy_and_sell(arr))` Re: Competitive Programming by Nobody: 3:42pm On Jul 29 DrLevi:if I got the question correctly then this should work. I can't guarantee efficiency or speed tho since I don't know algorithms terms like O[n2] or all that stuff`arr = [9, 11, 8, 5, 7, 10]def buy_and_sell(arr): sorted_arr = sorted(arr) buyAt = sorted_arr[0] slicedArr = arr[arr.index(buyAt): ] slicedArr.sort() sellAt = slicedArr[-1] return sellAt - buyAt print(buy_and_sell(arr))`Nice approach. It works for that example but not for some others e.g [2,3,4,1,2] will return 1 and [2,4,5,1] returns 0. Re: Competitive Programming by Nobody: 3:45pm On Jul 29 . Re: Competitive Programming by DrLevi: 3:47pm On Jul 29 Karleb: Although my python is not that good and I've not ran the code, but I believe this will return a negative value.Lol... It wouldn't. The code works, just might not efficient 1 Like Re: Competitive Programming by DrLevi: 3:53pm On Jul 29 Darivie04:Nice approach. It works for that example but not for some others e.g [2,3,4,1,2] will return 1 and [2,4,5,1] runs into an error.now you've mentioned it, it becomes more complex.back to the drawing board Re: Competitive Programming by Karleb(m): 4:02pm On Jul 29 How about this one? Re: Competitive Programming by Nobody: 4:13pm On Jul 29 . Re: Competitive Programming by DrLevi: 4:21pm On Jul 29 Darivie04:[right][/right][center][/center] ``` prices = [9, 11, 8, 5, 7, 10] def buy_and_sell(stock_prices): largest_profit = 0 for i in range(len(stock_prices)): for k in stock_prices[i:]: if k - stock_prices[i] > largest_profit: largest_profit = k - stock_prices[i] return largest_profit print(buy_and_sell(prices)) ``` There should be a more clever way to solve the problem but this works. This code returns "2" instead of 5 Re: Competitive Programming by Nobody: 4:23pm On Jul 29 DrLevi: This code returns "2" instead of 5Must be nairaland formatting cutting out part of the code, I'm still tryna fix that. It returns 5 over here. Re: Competitive Programming by DrLevi: 4:41pm On Jul 29 Darivie04:Must be nairaland formatting cutting out part of the code, I'm still tryna fix that. It returns 5 over here.Brilliant, it works Re: Competitive Programming by Nobody: 4:41pm On Jul 29 https://pastebin.com/vpYL0k7r Much easier. The formatting on the site was messing up the code. 1 Like Re: Competitive Programming by vheckthor1(m): 11:24pm On Jul 29 Karleb:How about this one? I have done this before Re: Competitive Programming by Karleb(m): 6:54am On Jul 30 vheckthor1:I have done this beforePost your answer here let's learn Re: Competitive Programming by ToyinDipo(m): 7:15am On Jul 30 Karleb:Let's start with this This is a maximum sub array problem, famous Kadane algorithm.It's an O(n) algorithm, only one for loop is requiredCall the first array a with size n,You create a new array of size n-1, each index i will contain a[i + 1] - a[i], then you find a maximum sub array of the new array.If I had to study an undergraduate course in Nigeria again, I would have studied Mathematics 2 Likes Re: Competitive Programming by ToyinDipo(m): 7:28am On Jul 30 Karleb:For those that love the challenge. This should be O log (n).You sort the tuples, you keep adding elements from the tuples (navigating from top to bottom) to a new list, before adding you do this, if the last tuple that was added to the new list, contains the range of the new tuple you want to add, you skip adding this tuple to the list, if the new tuple contains the range of the last tuple added, you remove the last tuple added, and add the new tuple, else you just add the new tuple to the list 1 Like Re: Competitive Programming by vheckthor1(m): 9:12am On Jul 30 Karleb:Let's start with this function maxer(arr){ let holder = 0; for(let i=0; i< arr.length; i++){ let some = arr.slice(arr[i]) let maxima = Math.max(...some) let subractor=maxima - arr[i] if(subractor>holder){ holder = subractor } } return holder}solved in javascript and the big O(n)=1a single loop 2 Likes