Welcome, Guest: Register On Nairaland / LOGIN! / Trending / Recent / NewStats: 3,195,544 members, 7,958,674 topics. Date: Wednesday, 25 September 2024 at 08:24 PM |
Nairaland Forum / Science/Technology / Programming / Competitive Programming (2722 Views)
A Thread For Competitive Programming / Thread For Competitive Programming (2) (3) (4)
Re: Competitive Programming by Donpre(m): 11:05am On Aug 05, 2020 |
Darivie04:Kindly post, I'm looking forward to seeing your solution |
Re: Competitive Programming by Nobody: 11:19am On Aug 05, 2020 |
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, 2020 |
Darivie04:https://pastebin.com/jufpns96 |
Re: Competitive Programming by Nobody: 11:22am On Aug 05, 2020 |
BlaqTesla: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, 2020 |
Donpre:Na u talk am. |
Re: Competitive Programming by vheckthor1: 12:08pm On Aug 05, 2020 |
Karleb:this is a Depth first search algorithm |
Re: Competitive Programming by Karleb(m): 12:20pm On Aug 05, 2020 |
vheckthor1: 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, 2020 |
Karleb:No, the smallest value of a tree may not always be at the deepest level. Take this Binary Search Tree for an example:
|
Re: Competitive Programming by Jummate(m): 6:26pm On Aug 05, 2020 |
vheckthor1:Yeah, I think this should do it. |
Re: Competitive Programming by Karleb(m): 7:24pm On Aug 05, 2020 |
Jummate: 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: 8:58pm On Aug 05, 2020 |
Karleb:So how do you get the smallest member without transversal |
Re: Competitive Programming by Karleb(m): 9:38pm On Aug 05, 2020 |
vheckthor1: 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, 2020 |
Karleb: 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, 2020 |
Karleb: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, 2020 |
Jummate: 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, 2020 |
Karleb: 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:
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:
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: 12:37am On Aug 07, 2020 |
Karleb: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, 2020 |
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, 2020 |
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, 2020 |
InfinityFabric: 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, 2020 |
fortifiedng: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 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 #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, 2020 |
InfinityFabric: 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, 2020 |
InfinityFabric: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, 2020 |
Najdorf: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, 2020 |
Najdorf: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! |
Vb.net For Dummies: / What Is The Difference Between A Programmer And A Developer / Please I Need Help With This Assignment
(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 - 2024 Oluwaseun Osewa. All rights reserved. See How To Advertise. 50 |