Really helpful and well explained, thank you very much for your vids✌️
@tempdeltavalue11 күн бұрын
03:09 it's not exactly true because you can remove similar pairs like "1 - 2" and "2 - 1" so you will get O(n^2 / 2)
@mateusvmv11 күн бұрын
Big O ignores constants like the division by two, but yeah that's an optimization in fact, big O is too stupid sometimes: if your algorithm had a fixed amount of particles and kept all of them somewhere very far away until you chose to spawn them, but ran the quadratic algorithm to calculate the gravity, then it would be O(1) because the running time would be constant (as in, constantly the worst lol)
@pawelokowidza20 күн бұрын
15:58 ♫
@LakieshaKuzyk-h7l22 күн бұрын
Damon Landing
@photonicsauce772924 күн бұрын
Hi just have a question. Since n-body problems (for n > 2) are known to be chaotic, isnt the barnes hut algorithm unsuitable for long time scales? The error accumulation may be significant right?
@pnachtweyАй бұрын
Use Storm's theorem.
@kaiyueguo16242 ай бұрын
Really good illustration, appreciate a lot❤❤❤
@Niashi242 ай бұрын
Good solution but it annoys me greatly when advent of code makes it so that the only way to solve the problem is to look at your specific input data for patterns and make assumptions that weren't in the instructions or the example. Going back to the previous years and this seems to be the only one in 2021 that does (unless day 25 has it, haven't gotten to it yet) but 2023 had like 5 of these. Is it really that hard to just...make the assumptions part of the problem?
@suryanshsingh72472 ай бұрын
thats was amazing
@askforinfo2 ай бұрын
Which software you has been used for this presentation?
@BrillCodeCS3 ай бұрын
This is the best explanation of Miller-Rabin Test I've seen so far. Thanks for this.
@andreaslundin1923 ай бұрын
This is an interesting solution for problem 4, but I am still trying to fully understand it. I can see how the location of a specific cut fully determines a set of subsets, and the number of steps we get for this given cut. However, I struggle to convince myself why one of the optimal solutions must exist among those provided by the cuts.
@Rozy754-i8g3 ай бұрын
could you please provide the codes here?
@sloodey83153 ай бұрын
thanks
@coopergates96804 ай бұрын
My recommendation for dealing with cases where the base and test number are not relatively prime is to only remove all factors of the test number from the base if the base is indeed a multiple of the test number. If the test number is prime but is not relatively prime to the base, then the test number must divide the base, and removing all factors of it will yield a "new" base that is indeed relatively prime to the test number, so the Miller-Rabin test can still run (if the resulting "new" base is all the way down to 1, pass the test number for that base right away). This guarantees that if a composite test number does not divide the base and the test number and base are not relatively prime, the test will properly flag the test number as composite, while still allowing primes that divide an original base to pass the test.
@integrantedavidanoturna4 ай бұрын
The explanation was good enough until you brough the tortoise and the hare. Then I had to sub.
@potzko25525 ай бұрын
I "invented" this when I was in eleventh grade learning how to program, it was my first real "hard" problem I solved kinda neat seeing someone else talk about it :)
@WilliamYFeng3 ай бұрын
yo that's so cool :D looking back on this now I realize how many steps this actually involves, so kudos to you!
@TarkTheConlanger5 ай бұрын
I feel really stupid for still not understanding how this works
@tanhnguyen20255 ай бұрын
very easy to understand.
@metallust5 ай бұрын
why lcm??
@zweitekonto96545 ай бұрын
Doesn't part2 takes like a second to run with just looping over all the edge points like this?
I am trying to learn dynamic programming, and for the most basic of problems like the staircase stepping I fully understand how to reach those objectie function/recurrence relationships. I had no idea how to apply DP to this problem and I thank you for taking the time to exlain it it in a table manner (non-recursive) because it truly captures the essence of dynamic programming that way, it feels like to me at least.
@Minji000018 ай бұрын
In this year i'll go😊😊
@akoshhh_32266 ай бұрын
how did u know that u were accepted ? have u already sent responses to ur applications?
@aaditya49988 ай бұрын
Just add this line before the part one if else statements #also i used value instead of amount if len(value) != 0 : value[-1] += joker else: value = [joker]
@0MVR_08 ай бұрын
this idea is coherent as a lagrange point
@kaleoxy9 ай бұрын
Congrats on plat!
@filmamundo91949 ай бұрын
wtf, i was trying to do systems of equations with conservation of energy when it was this easy
@CursedOneShot9 ай бұрын
Really Amazing video :D
@TheFrogfather19 ай бұрын
Welcome back! I bailed around day 10 but am still interested in seeing the solutions for later puzzles.
@aspzx9 ай бұрын
Thank you for reminding me to rewatch the KZbin classic Amateur by Lasse Gjertsen and for putting a different spin on it.
@footybite-gt1by9 ай бұрын
12.2 has been kicking my ass for 2 weeks now, I understand the purpose of pushing solutions to a map to reduce the amount of time spent processing solutions. People have tried to explain using a fib() function, which makes sense. Instinct tells me I should be running the original 12.1 to get solutions for each individual block, then multiplying out for the five. What throws me is how the combination works, there's an extra ? in the middle so the original solutions only make sense if every additional ? is a . I'm trying to understand dynamic programming and I keep getting "it's complicated, I won't go into it" 😂 I'm sat there like no, please do!
@HoSza19 ай бұрын
ok, now let's do 2048 bits 😂
@AlfredZhong9 ай бұрын
Really solved my problem. I had no idea about the part2 as I have never heard of the Ray Casting Algorithm. 😂Thank you.
@lee-uq6pm9 ай бұрын
i still didnt understand how do you know to append in which box? i dont get the logic
@vegeta39939 ай бұрын
I implemented the "hashmap" as a list of dictionaries (python3). The list is 256 elements long, and the index of the list to either place the lens into or pop from is the result of the hashing algorithm developed in part 1 on the first letters in the current line in the sequence (ie. 'rn', 'cm', 'qp', ...). Hope that helps.
@krige10 ай бұрын
Thank you for the explanation of part 2, that was very clear. Would be interesting to know what made you think to look into the input data and how you came up to the conclusion that the nodes looped. I tried to solve it by spawning a thread for each starting node and then let them run until they all reach a node ending with 'Z': this will be super fast, I thought, but instead it took forever. It never occurred to me to look into possible patterns in the input data. I am kind of disappointed about the fact they did not give any hint about the input pattern.
@Irakli00810 ай бұрын
I reached the same conclusion that William did, but only after trying to do parallel runs for all of them, like you. When I tried to debug it, I took a single starting point and made it loop 10 times and logged the amount of steps per loop. I noticed that the 10th loop was 10x bigger than the 1st loop, and everything in between was also a multiple.
@Telepriester10 ай бұрын
I like your videos a lot. thanks for sharing.👍
@agnesakne440910 ай бұрын
Your explanation is not superb
@DingoDummy202610 ай бұрын
I wish I saw this before taking number theory, would have helped so much 🥲
@agnesakne440910 ай бұрын
when will you get married
@leifmessinger10 ай бұрын
Hi mom
@TheTrienco10 ай бұрын
Kept coming back to this one. From brute force (2.5min), to multithreaded (45s), to parallel reverse lookup (75ms) and finally splitting the ranges from back to front (450us). Amazing how much difference an approach can make
@briandawley780810 ай бұрын
For reverse lookup do you mean start with locations? I couldn't figure out how to handle when something "upstream" doesn't have a mapped downstream value so instead just uses itself in that case.
@TheTrienco10 ай бұрын
@@briandawley7808 yes. But you have to pretty much start at 0 and count up, because the default mapping says "if no mapping, value maps to itself". So you can't just look at the location ranges, since all values are potentially possible.
@briandawley780810 ай бұрын
@TheTrienco yeah I tried going from zero but the "use self if unmapped" rule tripped me up.
@TeemuSa10 ай бұрын
In part 2, Instead of trying every substitution, I iterated over rows, and kept a tally of the total number of differing characters. If that exceeded 1, I had an early stop, and if it wasn't 1 in the end the line wasn't a smudged mirror location.
@TheTrienco10 ай бұрын
For part 1 I was happy with my one pass approach. Making it more generic for part 2 somewhat ruined the neatness. Rolling a column north just keeps track of the next valid destination as it goes, so no nested loops needed (swapping ranges with indexing for clarity): int64_t dst_row = 0; for (row...) { if (grid[row][col] == 'O') { swap(grid[dst_row++][col], grid[row][col]); } else if (grid[row][col] == '#') { dst_row = row + 1; } } Still can't get part under 19ms, though. All the copies to keep a history up to the first cycle must be killing it.
@TheFrogfather110 ай бұрын
In part one we have a method that finds a reflection point (horizontal or vertical) where there are 0 errors between reflected lines. So for part two we can run the same method but looking for exactly one error instead of 0! I tried this thinking I was probably missing something and was quite surprised when it worked!
@seboqw709910 ай бұрын
In part 2 there is no need to count the rem_jokers variable and also add it in if condition because it will always be 0. Remove it, think about it and see that the result will be the same.