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

## Competitive Programming - Programming (3) - Nairaland

(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 landscapedef 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 puddlesprint(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 landscapedef 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 puddlesprint(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 algorithmNo. 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 algorithmYeah, 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 transversalTransversal 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. 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 itFocus 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 itFocus on your Photo-lithography machine let others focus on their JS.ThanksFound 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 itNo 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#Olodo101Do 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#Olodo101Uhm...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.ThanksPS: 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.#ShiteThere 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!