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

Competitive Programming - Programming - Nairaland

Nairaland Forum / Science/Technology / Programming / Competitive Programming (1448 Views)

Thread For Competitive Programming (2) (3) (4)

(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 units
Amazing 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.g
1 < The size of the array < 10^6

Having 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 laptop

I 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 units

I duff my hat for you.

You should take up the role of a lecturer! cool
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))

cool cool
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:


cool cool

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 5
Must 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 before

Post 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 required
Call 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)=1
a single loop

2 Likes

(1) (2) (3) (Reply)

Learn How To Develop Facebook Applications Today / I Need A Very, I Mean Very Professional Web Developer/designer / Meet The 33 Year-old Nigerian Entrepreneur Who Built A $3 Million Edtech Company

(Go Up)

Sections: politics (1) business autos (1) jobs (1) career education (1) romance computers phones travel sports fashion health
religion celebs tv-movies music-radio literature webmasters programming techmarket

Links: (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)

Nairaland - Copyright © 2005 - 2020 Oluwaseun Osewa. All rights reserved. See How To Advertise. 356
Disclaimer: Every Nairaland member is solely responsible for anything that he/she posts or uploads on Nairaland.