Відео

Depending on which playlist? This video was a lecture for 3rd year students, so that's not a good starting point for data structures and algorithm (DSA). Your intro to DSA course would be a much better starting point, or if you don't have one, you can checkout MIT's one: ua-cam.com/play/PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY.html The other playlist I have are support materials for the coding club at our uni, and the basic one (ua-cam.com/play/PLMDZqACtfCkN0QFu10NFx3e3P-vKB-CQ2.html) is meant for 1st year students. We use Java at our uni and the 1st year students wouldn't have done the stuff I talked about there (HashMap, StringBuilder, etc). At the same time, they're not a structured course on programming. Neither is CP1 or most competitive programming books. You really need to start with a DSA course and then complement it with CP books/resources.

You mean the visualisation in the video? They're just slides. I used slides.com/ for convenience, but if you're comfortable with javascript, you can also use something like github.com/hakimel/reveal.js or github.com/impress/impress.js. I have also used d3js.org/ to make some animations in the past.

@@DanielSutantyo Thank you are the best.

Thank you 🙌

Yes, but so are other resources like leetcode. Kattis questions are closer to contest questions because it doesn't tell you the approach that you should use, while in leetcode, you usually know what to do because the questions are organised by the topic =). We've been using CP4 since that's pretty much the standard book for competitive programming, and it has a list of relevant questions for each topic it discusses. CP1 and CP2 are free, and the website cpbook.net/methodstosolve has the list of Kattis questions relevant to each topic.

Hi, the code is simplified, yes, but with that code, there's no 'early exit', i.e. you will keep recurse until you hit the end of the array even if it's hopeless. As a simple example, iif there's no answers, e.g. groupSum(0,[10,20,30,40,50], 5) you will evaluate all the possibilities (2^5 = 32), where as if you have the early exit (if (target < 0)) you'll only evaluate 5 times.

Do you mean when I 'restore' the board by cancelling the move, like what I said around 22:50 mark? It's like playing chess or any other board game, but you're allowed to take back a move. Imagine you move the king and you get check-mated, then your opponent say, "OK, let's try again, do something else". You'd move the king to its original position and try to go somewhere else instead. In this setting, basically what we're doing is: for loop - keep repeating until we've tried every single move do a move recurse - we go to the future and see what happens take back the move (reset the board) if we don't reset the board, then we're not really 'taking back' the move, right?

​@@DanielSutantyo Yes, it is from 22:50. Thanks, I think I understand a bit better now!

Thank you, Tina. This was the first video that I recorded and I made the mistake of recording it in 720p. Every other video I made were recorded in 1080p, and if the text is still not clear, the link to the question should always be in the video description.

Thanks for the comment, and sorry, obviously I don't check youtube that often =) I realise now that I made a mistake in this video. Your code is basically the first approach that I discussed, but obviously you are not permuting anything. I guess in my mind at the time, I wanted to make sure that students know the difference between combinations vs permutations. As for efficiency, I'm sure there's a way to prove this mathematically, but I can't think of it for now. My gut feeling says that your code is actually FASTER than the solution I have, because as an example (I hope this make sense), let's say your array is [1,2,3,4,5], if you want to evaluate the sum of single elements, your recursions would just try 1 on its own, 2 on its own, 3 or its own, etc, where as my solution would try [1,0,0,0,0] [0,2,0,0,0] [0,0,3,0,0] [0,0,0,4,0] [0,0,0,0,5] In fact, I think I will always do twice the number of recursions. I haven't had the time to make more videos for the last few months, but when I do, I definitely have to address this mistake.

Sorry, just to be more clear, when I wrote 0, I meant "choose nothing". What I'm trying to say there is, in my code, to check something like [0,0,0,0,5] I have to make the function calls 5 times, but in your code, this is only done once because when you start with 5, you won't try anything else. Another way to put it, you never take the 'NO' branch, which means you're doing half the recursion (in the worst case).

In general, it is up to you how you want to handle the case when target == 0 (do you allow the trivial choice of not selecting any integers?). For this question, one of the test cases is an empty array with target == 0 which should return true. It also makes things simpler because the point is to show how recursive backtracking works. If you require at least one integer in the array to be selected, then you can pass another variable that keeps tracks of the number of integers chosen so far.

@@DanielSutantyo i see thanks.

It's actually faster than using Scanner, but I chose Scanner for the target audience so that we don't have to worry about tokenizing the string =). There are definitely questions where using a Scanner can result in a TLE.

@@DanielSutantyo Yeah exactly, but I guess Scanner is the easiest way for beginners so it makes sense in a tutorial like this There are also more ways for faster output options like buffered writer, but usually I like print writer more. The only difference to system.out is that you have to use bw.flush() afterwards or set auto flush to true. People would not expect it, but sometimes i/o can be the bottleneck so it is worth to consider it. Btw thx for your Java videos, there are basically like 10 people on earth who use Java for cp, so thank you for being one of the other nine haha

哦btw你是中国人吗-?

@@user-pd1en1fd1r Nope, but I can read enough to understand that lol. We use Java because that's what our uni use for 1st and 2nd year students, and yeah, I think 99% of CP is C++ =).

@@DanielSutantyo Yeah, C++ is more efficient and the std library is great, so it is probably the better option. Sometimes I also wonder why Rust is so uncommon in CP. We learn C/C++, Java, Assembly and Haskell in first year at my university + VHDL.

Java..

​@@startinggintamaAh yes, thank you, you saved me after 2 years. I really needed it 😮