Would love a lecture on Chinese Remainder Theorem!

@refeez3700

3 жыл бұрын

Yeah, that one was a head scratcher.. I remember looking at someone else's solution and then... I wept.

The cool animation from outro: kzread.info/dash/bejne/dJWEpKmCctWufLA.html All codes are in my GitHub repository: github.com/Errichto/youtube/tree/master/AOC-2020/20-jigsaw

Wow that visualisation was very nice 🤩

@Errichto

3 жыл бұрын

Thank you :)

You are my inspiration.

You can also put all edges (forward and reversed) of every tile into a hashmap. That reduces the complexity to linear. You instantly know who is the neighbor of whom.

@Errichto

3 жыл бұрын

Good point. I would say that the "should line up exactly with its adjacent tiles" condition wasn't precise enough and I expected possibly more edges in this graph, hence backtracking. I agree that if degrees are all as small as possible then everything is linear (if we find edges in a smart way first).

@sebastien_lemieux

3 жыл бұрын

I had the same concern as @Errichto! So first I built my hashmap for edges by using a flip-invariant hash (thus one hash per edge) and then counted the number of tiles sharing each hash. Corner tiles are tiles with two unshared edges (part 1). Then it was simple to verify that all edges are shared by either 1 or 2 tiles, confirming that there was no ambiguity and suggesting a linear solution. (btw, great explanation!)

@CarrotCakeMake

3 жыл бұрын

@@sebastien_lemieux Yes, and if it is really size 10 edges like in the example, then a perfect hash is possible.

Love the # visualisation in the console. Very nice video and explanation.

What a lovely explanation!

Errichto : The code isn't scary , it is around 100 lines Me : 😭😭😭😭

@Errichto

3 жыл бұрын

Imagine that it's just 5 easy problems, each requiring 20 lines of code :)

@harshsamoliya1954

3 жыл бұрын

@@Errichtoi use java so for me it is 10 easy problem 😏😏😏

@techwiki1512

3 жыл бұрын

haha google service have 1.8 -2billion lines of code 100 lines take about 2 mins and if your typing speed is 100wpm and your thinking is fast enough to keep up I can see someone doing this in a few seconds if you already solve it and just coding it

@pictureus

3 жыл бұрын

@@techwiki1512 Pretty sure it's for the memes.

@techwiki1512

3 жыл бұрын

@@pictureus Oh ... um hahaha?

instead of the can_right and can_below function you could do a byte comparision. The tiles are 8x8 so each tile would have 4 bytes representing each edge. You could describe a tile with a 32 bit int and for the rotation you just would have to bit-shift the representation. With that aproach you can check all edges of a tile at once for any given rotation :-)

Every other video for Day 20 (this one) was more than 35 min long. Thank you for this one. Please make video for Day 13 (Chinese Remainder Theorem) and Day 23.

Visualization is very food! You very good master🙂🏆🎉✨🎖️

@Errichto Can you please explain how the problems are in Div3 contests on Codeforces? Like, what are the necessary prerequisites for participating in them? What should be the learning level to take part in it? I have been attempting to take part in an online contest for some time now, just too afraid to take the step, so hope that you can provide help:)

Have you considered performing affine transformation on the tiles?

Hi, what program do you use for drawing/writing your explanations on gnu/linux?

Can you suggest one good book on data structures and algorithms? I have searched on internet and find like so many books and it's really confusing. If you can suggest one book which is going to cover everything and can be used as a good reference for preparing for coding interviews then that will be great. And if that book is written for c++, then that's even better.

@Sebmen4

3 жыл бұрын

I strongly recommend Algorithm Design Manual by Skiena. It covers all the important topics, the code is in c++ and it contains an amazing catalog of commonly seen problems.

Umm bro could you pls explain why my fb email changed into blackhole null woth numbers what does it mean?

There are eight possible solutions when you are putting the tiles together. Depending on which tile and orientation you choose for the first tile, you could get the same connections but with the whole patchwork of tiles flipped over, or rotated. This is why in the problem statement says you might have to rotate or flip to find the sea monsters. Probably with your code you just got lucky that the solution you found was already oriented correctly (1/8 probability).

@ElephantHannibal

2 жыл бұрын

YES! Thank you. I'm looking at this now, and was wondering the same thing. And that's why he's exiting 0 at that return. I thought I was crazy. :D Thanks for confirming that I'm not. :D

Hey. I want to learn competitive programming but I'm not good at maths. Where can I start?

Is it possible to use this backtracking technique without exit(0) or throwing exceptions?

@tomaszzielinski1704

3 жыл бұрын

I think he uses 'continue' for that. You could also use 'break'. I would rather saperate this to other function and use return.

Hey Errichto, what do you think, if this problem was on Codeforces, what would be its rating? Advent of Code problems were quite different from typical Codeforces problems so I'm not quite sure if they are more suited for Div. 3, Div. 2 or Div. 1.

@prakash_77

3 жыл бұрын

Actually they are very different from the CF problems. A good part in AOC is parsing the input correctly. The input is very small, there's just one case to run in AOC. Most of them don't probe your algorithmic skills but only your implementation skills. No wonder, quite a few participants do it to learn and get better at a new language. But baring Day 13 part 2 and Day 20 part 2 (this one), there weren't any hard problems. Maybe you can add Day 23 part 2 also. Rest would fall in the easy part ( initial questions ) from Div 3 CF. Still this comparison isn't fair.

@Errichto

3 жыл бұрын

It's hard to say because AOC problems aren't difficult in terms of algorithms. Even Codeforces div2-C (div1-A) already requires a more tricky idea/insight than this Jurassic Jigsaw problem. On the other hand, CF problems require much less implementation and thus quite a lot of time. Maybe it's fair to say that this is around div1-AB level because it would take me around 15-20 minutes to implement during a contest.

I love u sir

You can optimize this a bit by only trying all the orientations of tiles with degree of 2 at the top right corner.

"code not scary" yeah, just really killing

please provide amazon link of the chair you've got

Wyrazy podziwu za wiedzę jaką posiadasz :) czy są jakieś strony dla totalnych laik'ów z tej dziedziny, którzy chcieli by zacząć przygodę z programowaniem?

@Errichto

3 жыл бұрын

There are hundreds of free programming courses online. Later, after you learn any programming language, read this to start with competitive programming: cses.fi/book/book.pdf

Hi Errichto! any suggestions for a beginner preparing for google code jam??

@Errichto

3 жыл бұрын

I wrote down my long advice some time ago: github.com/Errichto/youtube/wiki/How-to-practice%3F

@deepeiton6112

3 жыл бұрын

@@Errichto Thank YOU!

Which keyboard do u use?

Is the diagonal pattern always there?

@Errichto

3 жыл бұрын

I used colors only to make it easy to see where tiles are. Treat them as random colors, there's no diagonal pattern.

I have any project available

how does he have one note on linux ??

@korosensei3780

3 жыл бұрын

that too with the dark mode

Dude, you're looks like Ed Snowden. 😁

@programmer2279

3 жыл бұрын

Yeah 😀

Some people just like to tap dislike button.. they make it a habit .. we should ignore them..

how (/why) are you using onenote for windows on a linux system?

Bro I need project

Bro u can calculate the edge with binary with . As 1 # as 0 and store the result and check compare with other

@Errichto

3 жыл бұрын

That's not a bottleneck of a program so no need for extra code to speed it up.

There is no need for backtracking: just bless one corner as top left, rotate/flip it to match top left position. Now repeatedly go down -> left column, now go right for each tile in left column.

@yixing2301

3 жыл бұрын

underrated

Can you consider making some content on educational DP problems from AtCoder? Here's the link to it. atcoder.jp/contests/dp/tasks . These questions are very basic, but they do teach beginners on how to frame a thought process to answer questions using dp. Learning this from you will be impactful.

Hii sir my name is Saurabh priyadarshi from Kaimur Bihar please help me sir. I am in class 9 and I want to prepare for International Olympiad in informatics. I belongs to backwards area and here I can't learn competitive programing. Next year I want to participate in IOI. These are My question 👉👉 1. How I can prepare for IOI for beginners. 2. Which books are required for CP. 3. From where I can learn CP. Please give me your email address sir Thanking you My biggest inspiration is your are sir. I hope you will really reply me.

U became newbie in codeforces right 😂😂😂

hey google?do you wanna algho engineer?

Oh, funny that you mentioned the chinese remainder theorem. I wouldn't have known it, if it wasn't because of a cryptography security ctf challenge.

dO yOu wAnT tO bE a sOfTwARe eNgINeEr aT gOoGLe?!?

POLSKA GUROM

Why bother trying when you can just buy an Errichto?

@Errichto

3 жыл бұрын

This is what I did and it works fine for me :)

@OptimisticForce

3 жыл бұрын

​@@Errichto I bought petr mitrichev few days ago, So I am safe as well

Bro you should stop doing those useless problems and get a job at Space-X where you will solve important problems. Or maybe you already are?