Welcome, Guest: Join Nairaland / LOGIN! / Trending / Recent / New
Stats: 2,551,353 members, 5,881,079 topics. Date: Sunday, 27 September 2020 at 02:31 AM

Competitive Programming - Programming (3) - Nairaland

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

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

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

Re: Competitive Programming by Donpre(m): 11:05am On Aug 05
Darivie04:
I think I've solved this.
Kindly post, I'm looking forward to seeing your solution
Re: Competitive Programming by Nobody: 11:19am On Aug 05
Karleb:
.
elevations = input()
elevations = [int(i) for i in elevations if i != ' ']

def transform(elevations):
landscape = ['' for i in range(max(elevations))]
for i in range(len(landscape)):
for k in elevations:
if len(landscape) - i > k:
landscape[i] += ' '
else:
landscape[i] += 'X'
return landscape

def capacity(landscape):
puddles = 0
for i in range(len(landscape)):
for k in range(len(landscape[i])//2):
puddle = 'X' + ' ' * (k+1) + 'X'
if landscape[i].find(puddle) != -1:
puddles += k + 1 * landscape[i].count(puddle)
else:
continue
return puddles

print(capacity(transform(elevations)))



Enter the elevations on a single line seperated by space.

1 Like

Re: Competitive Programming by Nobody: 11:21am On Aug 05
Darivie04:

elevations = input()
elevations = [int(i) for i in elevations if i != ' ']

def transform(elevations):
landscape = ['' for i in range(max(elevations))]
for i in range(len(landscape)):
for k in elevations:
if len(landscape) - i > k:
landscape[i] += ' '
else:
landscape[i] += 'X'
return landscape

def capacity(landscape):
puddles = 0
for i in range(len(landscape)):
for k in range(len(landscape[i])//2):
puddle = 'X' + ' ' * (k+1) + 'X'
if landscape[i].find(puddle) != -1:
puddles += k + 1 * landscape[i].count(puddle)
else:
continue
return puddles

print(capacity(transform(elevations)))



Enter the elevations on a single line seperated by space.
https://pastebin.com/jufpns96
Re: Competitive Programming by Nobody: 11:22am On Aug 05
BlaqTesla:
Looking at the solutions you guys paste here... most of it were all copied.
I hope you have proof to back up what you're saying unless you'll just end up looking very foolish.
Re: Competitive Programming by Nobody: 12:06pm On Aug 05
Donpre:

Are you saying Nigerians aren't smart enough to come up with answers to those questions?
Na u talk am.
Re: Competitive Programming by vheckthor1(m): 12:08pm On Aug 05
Karleb:
....
this is a Depth first search algorithm
Re: Competitive Programming by Karleb(m): 12:20pm On Aug 05
vheckthor1:
this is a Depth first search algorithm

No. It's finding the smallest value of the tree.

The tree transversal will be quite unnecessary.
Re: Competitive Programming by Jummate(m): 6:22pm On Aug 05
Karleb:


No. It's finding the smallest value of the tree.

The tree transversal will be quite unnecessary.

No, the smallest value of a tree may not always be at the deepest level.

Take this Binary Search Tree for an example:

10
/ \
5 17
/ \
3 8
/ \
7 9

Re: Competitive Programming by Jummate(m): 6:26pm On Aug 05
vheckthor1:
this is a Depth first search algorithm
Yeah, I think this should do it.
Re: Competitive Programming by Karleb(m): 7:24pm On Aug 05
Jummate:

No, the smallest value of a tree may not always be at the deepest level.

Take this Binary Search Tree for an example:

10
/ \
5 17
/ \
3 8
/ \
7 9


That's right.

But in the question, the value at the deepest level is the minimum. So finding the minimum value of that particular BST would solve the problem.
Re: Competitive Programming by vheckthor1(m): 8:58pm On Aug 05
Karleb:

No. It's finding the smallest value of the tree.
The tree transversal will be quite unnecessary.
So how do you get the smallest member without transversal
Re: Competitive Programming by Karleb(m): 9:38pm On Aug 05
vheckthor1:
So how do you get the smallest member without transversal

Transversal means visiting all nodes. That is, breath first search or depth first search.

Finding the minimum value on a binary search tree should not require that, since we know that the smallest value will always be on the far left of the tree and of course the highest will be on the far right.

So we run a while loop to check if the left node of a particular node is null starting from the root node, the loop will return the node that has no left node.

In this BST the loop will go from 50 to 17 to 12 to 9 and will return 9 since 9 has no left node.

Re: Competitive Programming by Jummate(m): 10:09pm On Aug 05
Karleb:


That's right.

But in the question, the value at the deepest level is the minimum. So finding the minimum value of that particular BST would solve the problem.

Look at the question again. The tree was only used as an example so as to aid easy understanding of the problem. The question actually expects that any algorithm used should work in all cases(different arrangement of the tree).
Re: Competitive Programming by Jummate(m): 10:16pm On Aug 05
Karleb:


Transversal means visiting all nodes. That is, breath first search or depth first search.

Finding the minimum value on a binary search tree should not require that, since we know that the smallest value will always be on the far left of the tree and of course the highest will be on the far right.

So we run a while loop to check if the left node of a particular node is null starting from the root node, the loop will return the node that has no left node.

In this BST the loop will go from 50 to 17 to 12 to 9 and will return 9 since 9 has no left node.



Yes, very good. But this will work only if the BST is balanced(in the case of this BST). How about the case of the BST example I posted the other time?. I think it's better that an algorithm works in all cases. Only my thoughts though..

1 Like

Re: Competitive Programming by Karleb(m): 7:42am On Aug 06
Jummate:

Yes, very good. But this will work only if the BST is balanced(in the case of this BST). How about the case of the BST example I posted the other time?. I think it's better that an algorithm works in all cases. Only my thoughts though..

Binary Search Trees are always balanced!


Binary trees don't always have to be balanced and I guess in such case the tree transversal is the correct way of getting the deepest value.

The tree in the question is a binary tree not a binary search tree.
Re: Competitive Programming by Jummate(m): 8:56am On Aug 06
Karleb:


Binary Search Trees are always balanced!


Binary trees don't always have to be balanced and I guess in such case the tree transversal is the correct way of getting the deepest value.

The tree in the question is a binary tree not a binary search tree.

I beg to differ on your first statement. A Binary Search Tree may not always be balanced.
A Binary Search Tree can actually be balanced or unbalanced depending on its implementation. A BST can become unbalanced if rotation is not carried out after insertion or removal which increases it complexity to O(n) but balanced BST such as AVL Trees, Red and Black Trees etc always maintain a complexity of O(logn) which BSTs are originally known for.

Consider for an example, if I created a BSTwith 1 as the root and subsequently added 2, 3, 4, 5 which will make my BST to look this way:


1
\
2
\
3
\
4
\
5


This is an unbalanced BST. It will even become more unbalanced if I continue to add in this order up to say 1000. This is just as good as using a list as they will both run with the complexity (O(n)).

The only way the complexity can be restored to O(log(n)) is by rotating and rearranging the elements of the BST to form an AVL Tree, Red and Black Trees etc which are balanced BST trees.

Then, the BST can look like this for example:


3
/ \
1 4
\ \
2 5


With this now, searching can now be made in 0(log(n))


I may not know what Google knows. You can just conduct a search on this.


On your second paragraph, that the tree is a Binary Tree is even the more reason your algorithm will not work in all cases because you tailored your algorithm to a BST. Remember, you mentioned finding the minimum value in the tree the other time. You know, a Binary Tree may not always have its minimum value on the left as they do not follow the strict principle of arrangement as BSTs.


Please do not see this as any form of attack. You can correct me if I'm wrong. I'm always open to learning.

1 Like 1 Share

Re: Competitive Programming by vheckthor1(m): 12:37am On Aug 07
Karleb:


Transversal means visiting all nodes. That is, breath first search or depth first search.

Finding the minimum value on a binary search tree should not require that, since we know that the smallest value will always be on the far left of the tree and of course the highest will be on the far right.

So we run a while loop to check if the left node of a particular node is null starting from the root node, the loop will return the node that has no left node.

In this BST the loop will go from 50 to 17 to 12 to 9 and will return 9 since 9 has no left node.



I think your solution will be an hard coding of the example given, the depth is not always on the left of the tree, so how would you get the depth if you don't check through?
Re: Competitive Programming by Karleb(m): 5:30pm On Aug 12
So I got this question of recent.


The solution to this is the Dutch National Flag algorithm. Funny thing is, the algorithm only solves for 3 colors. grin

Re: Competitive Programming by InfinityFabric: 6:12pm On Aug 12
Competitive waste of time. Things u come across 0.001% in real-world.

While we are @ it, please change your profile picture, it's cringe-worthy.
People who make CPU and RAM have no business coding, THEY ARE THE CODES!
Have u seen a Photo-lithography machine ? Physicists involved in making of those machines have no business with JS like the JS junkie have no business with electrons.
Re: Competitive Programming by fortifiedng: 10:06pm On Aug 13
InfinityFabric:
Competitive waste of time. Things u come across 0.001% in real-world.

While we are @ it, please change your profile picture, it's cringe-worthy.
People who make CPU and RAM have no business coding, THEY ARE THE CODES!
Have u seen a Photo-lithography machine ? Physicists involved in making of those machines have no business with JS like the JS junkie have no business with electrons.

Do what you feel like and let others do what they feel like. Stop comparing one with another.

Let the JS junkie do their thing and the Physicists do their things.

Stop downplaying other people's interest and motivation because you want to promote something your are interested about and no one's talking bout it

Focus on your Photo-lithography machine let others focus on their JS.

Thanks

3 Likes

Re: Competitive Programming by InfinityFabric: 10:22am On Aug 14
fortifiedng:


Do what you feel like and let others do what they feel like. Stop comparing one with another.

Let the JS junkie do their thing and the Physicists do their things.

Stop downplaying other people's interest and motivation because you want to promote something your are interested about and no one's talking bout it

Focus on your Photo-lithography machine let others focus on their JS.

Thanks
Found the JS junkie!
You should learn how to read properly before commenting.

Stop downplaying other people's interest and motivation because you want to promote something your are interested about and no one's talking bout it
No wonder u can't write past JS. U can't think properly. I gave examples of other useful things in tech = promote something your are interested about
#Olodo101

Do what you feel like and let others do what they feel like. Stop comparing one with another.
Uhm...no. We don't support mediocrity.

BTW, what is:
"If you love technology, I don't understand why you're not coding" ?
Is it not downplaying other important of tech ?

No Thanks.
Re: Competitive Programming by fortifiedng: 11:04am On Aug 14
InfinityFabric:

Found the JS junkie!
You should learn how to read properly before commenting.


No wonder u can't write past JS. U can't think properly. I gave examples of other useful things in tech = promote something your are interested about
#Olodo101


Uhm...no. We don't support mediocrity.

BTW, what is:
"If you love technology, I don't understand why you're not coding" ?
Is it not downplaying other important of tech ?

No Thanks.

They never sounded like examples.

You say I cant think properly, Good for you.

You should actually be the one to write and express yourself properly.

To your Question, all I have to say is that, There are other sides to that Question. So if that's the best way you could interpret the question. Good for you.

Thanks

PS: Try to control your anger. I can see how boiled up you for just a little counterintuitive comment I made.
Re: Competitive Programming by Najdorf: 4:52pm On Aug 14
InfinityFabric:
Competitive waste of time. Things u come across 0.001% in real-world.

While we are @ it, please change your profile picture, it's cringe-worthy.
People who make CPU and RAM have no business coding, THEY ARE THE CODES!
Have u seen a Photo-lithography machine ? Physicists involved in making of those machines have no business with JS like the JS junkie have no business with electrons.
I'll only address the part of your post that was sensible, which is only the first paragraph.

People engage in competitive programming either for fun or to prepare for job interviews. There is a certain joy in finding ways to solve tough problems and not only that but finding ways to solve them in the most efficient way possible. But you're right, depending on the area you work in, cp skills might not be very useful but that doesn't really matter.
Re: Competitive Programming by fortifiedng: 7:37pm On Aug 14
Najdorf:

I'll only address the part of your post that was sensible, which is only the first paragraph.

People engage in competitive programming either for fun or to prepare for job interviews. There is a certain joy in finding ways to solve tough problems and not only that but finding ways to solve them in the most efficient way possible. But you're right, depending on the area you work in, cp skills might not be very useful but that doesn't really matter.
This was the message the guy was trying to pass, but ended up saying another thing
Re: Competitive Programming by InfinityFabric: 11:11am On Aug 15
Najdorf:

I'll only address the part of your post that was sensible, which is only the first paragraph.
You mean the part can half-comprehend.

People engage in competitive programming either for fun or to prepare for job interviews.
A good way interview: ask them things they would never use in their job.
#Shite

There is a certain joy in finding ways to solve tough problems and not only that but finding ways to solve them in the most efficient way possible.
Wastage of time, go make a library people will use instead. That's the real challenge not solving 2 + 2 in your favorite lang.

But you're right, depending on the area you work in, cp skills might not be very useful but that doesn't really matter.
It's not CP skills, it's mostly 2 + 2 or string nonsense.
Again, make a library, be contributor, make an app that other apps might depend on (gateway).

Imaging going into an interview an highly performant HTTP Framework or another of the crazy protocols or Concurrent programming lib.
Then an interviewer is asking you questions from Hackerrank, I will tear the questions and the guy!

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

Java Programs / How Do I Design A Computerised Stock (inventory) Card? / Java Mentor

(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. 138
Disclaimer: Every Nairaland member is solely responsible for anything that he/she posts or uploads on Nairaland.