Google Hash Code 2020 Finals | Robot Arms (Upsolving)Jul 13, 2023
and I think I think that in life hello everyone, I'm Erica and this will be a broadcast in which I will absolve the Google
finalswhich were yesterday, Saturday April 25th or something like that. My team didn't. I didn't do well on that. contest I made the back part in the middle of the contest and our solution because of that force is very bad, you hate to see some drawings. I should chat, but I don't know if it will work or not, so far it seems like it will. It doesn't work there is also this hello Jojo in the trapped sigh hello Joseph hello Joseph so it's this competition there should be some link in the description and first I will talk about the problem statement it is here then I will tell you what we did during the competition and that It will take in total maybe 5-10 minutes.
This is the declaration and then the main part of the string. I'll go for a few hours to solve this problem in some better version, like the one I've trained here. This is my count. It's another count. I will continue to improve that during the hours yesterday were not enough to test even a third of the ideas I had. This still doesn't work. Come on. I see the chat on the side. Just rest. Sleep should hold a combination. chat I'll turn it off and down maybe that will help maybe a bath changed your system Oh turn this off and on at least important twitch messages I'll be fine hello Qing Yun proxy if I Suns Kauai and use YouTube hello everyone, I see the chat first, statement, if you don't know what Google
codeis about, you are faced with a problem, there are four to four people in a team and you need to solve this problem to the best of your ability.
This category of problems is called Optimization or Approximation Problems where no one knows a polynomial solution that will simply solve it in the best possible way and it is necessary to continue improving the problem. There is a grid with some mounting points for
armsor snakes. They behave a bit like snakes. and you need to keep moving this arm, expand it and since a long time I see that my face is the screen, there is a grid like this and there are mounting points for
arms, you can keep expanding and retracting, shrinking this arm, there will be multiple arms in the grid and they need to reach some particle cells to collect items and finish our task, the task consists of several golden points, there are some points on the grid that you need to reach in this order, then you will finish the task there is an example here what happens there two robotic arms starting again here the one at the bottom will move up first this one will move first to the right this is the situation after the first step after the second step they expand even more than this the one at the top picks up an item and returns from this way also once it goes down to zero the second arm can instantly hear reach freely to the top column and then even reach this one so basically you just need to finish the tasks and each task has a score how to send the codeine hash code, well, you have to submit it to the judging system.
I won't do it. I'll interact with the chat just a little bit because I mainly want to resolve the issue. Etan on my youtube channel directed to you, you can see the real screencast. contest and a screencast of me creating this solution, but I was also on the team, the other teammates in particular made some special solutions for two tests because there are six tests that you can download and analyze on your own, maybe I'll show you this. our shared Google doc where Carol analyzed the tests and showed some statistics about them, particularly those that are difficult to perform to complete a task.
This is each test showing three random tasks, which path we would have to follow to complete this task. just a very specific one where everything was on the edge, but our goals are in this test, right on the edge, the orange dots represent cells that you need to reach, but those are more normal tests, there was also visualization on the judge if we go here. If you go to the leaderboard, the maximum score of the contest was 6.7 million, we got 14th place, a very bad one below 4 million points right after the contest and I found an error in my BFS.
I can show you that error in a moment. we jumped to 5 million points which is still far from the top, not that if we found a bug five minutes before the end we would win, not even close to the bug, my mistake was pretty simple and that was in BFS. I added this if I didn't reach the final position then it returned the empty path because BFS found the path from one cell to another to say ok this robotic arm will now make this path but by adding this before I forgot everything was fine, sure he had responded.
I found the way, but then I added something I needed to handle multiple robotic arms. I enjoyed saying that if you can't get there, try other tasks, try to wait, that's rushing because you know that when turning, the robotic arms can't cross each other like in steak, basically you need to handle several snakes, but they also have all the starting points and here is a very important part of iterating our visit cells in a BFS queue and marking them as unvisited, a solution for all the errors was to copy this and also paste it here before this other return every time I record from BFS a moment before I should delete visited so this is a wrong code and now this is the correct code unfortunately a stupid error now in such a long code if there is a problem if my solution was very bad I would notice that something is wrong.
I would look for a bug long before the end of the competition, but I thought I need to improve the logic of how long the 400 line count is and I think I'll start by cleaning the coat I have two instances, I promise what I had near the end, but then I went back to an older proto-like version where I tried to debug this one and while I clean it up maybe I'll get a discount. I have a github repository and will publish at least a few. part of this after the broadcast I want to refer this yes, this may be different, ok, it doesn't matter, I know what I did.
I continued like this after the contest. I spent a few more minutes trying to choose the right seed and things like that. I will review this code. and while I'm cleaning it I'll also explain what's going on because right now it's pretty ugly. Can I delete something? Maybe from the top you want to say that you will be my yellow duck for debugging, but this code works. We have some global height and width variables. grab the number of robotic arms possible mounting points tasks and turns game duration total score if I complete the task I increase the total score by scoring a task here each task is described by a sequence of cells this does not matter I have a function for distance of Manhattan between two cells which works to check if a cell is inside the grid or maybe I try to get out of a grid, then I precomputed some number of neighbors of each cell at some point because there are about four billion cells in the grid I can't enter those Delta, this is just something useful for founding neighbors.
Its mouth. I don't remember if I use a clue here or maybe a bull. Let's try to discover his mount. This is just a boolean value so you can change it. a vector vector of boolean values this this mount means it's a forbidden forbidden sucks so because it's a possible mount point compile navigation crank what assert wasn't declared what did someone change my my include what's up with that sorry something happened in the repository apparently in Google Code Jam we have a different UI, for example, I won't explain the hash code UI to you, come on, it's not that easy to chain, you can remove the vertical line from Jeannie.
People are very upset with this line. This is this vertical line that bothers everyone. apparently it's just Sam, you know, position means I'm not true. I don't want to get past this. I think it's sixty characters, not 72, and that's pretty reasonable. It is a good rule of thumb not to cross it. Not to say I don't cross it as you see here, but I try to avoid that if it bothers you that much and I saw comments about it on YouTube, I'll delete it. I guess I'll use the Google Dreamy Height vertical junk search interface editor here.
The line preferences editor shows you I don't see it, oh this game, here we go, there's no vertical line right when I don't see something, remember the chat is like 10 seconds so it's still going to take me a moment to realize what what is happening. I will continue to explain some parts of the cost. This cell size is prohibited. This is complicated. I will explain it later. I do not use it. This means that some tasks will be deleted. BFS starts the cell, ends the cell, and the current turn thinks strangely about time. We must remember that every time a cell is available, he finds the shortest path from one cell to another.
Each arm remembers its mounting point, the starting point, a stack, means how it expands right now. It moves, remembers what to print and this too. you need to print something there are some helper functions to advance and retract the current white digit here i don't use it some constructor i used i think not this is like the current cell solution that's the main part i won't touch it for a moment let's hide it recalculate neighbors do I use recalculate neighbors? I don't like it right now it's just calculating neighbors. I meant that I wanted to ban them so this is just compute neighbors and then respond that it is empty and do that, what happens in the main function, we read the particular input, we have mount tasks, it reads the tasks that I don't use, which there are some seeds because I experimented with it, I randomly shuffled that order of mount points here, I try to choose the mount points to be far away from each other.
I'll come back to this later, I'm sure this is an arm limit to start with. I'll delete that bit later, neighbors of this main part. You're supposed to do this as long as it's true. First look for an arm that is available and that is free like doing nothing first and assigning it some tasks while it is true no, don't do this, this is a debugging, find the best arms of the one that minimizes the size of the movements, the amount of moves already made, so the current turn if not done. found and broken otherwise if it raises who is always here as oh here I wanted to pass some information I will delete it automatically returns true if it managed to assign a task if this is false then delete and now I will need to change a little when I can delete stupid useful debugging arms at final.
I just need to find arms that do anything now to resolve in a moment after I'm done with this feature. I'll show you a visualization of what my program does because it's available on their website. anyone who can observe the solution or just the participants. I am afraid that Google hash code participants alone do not need to qualify for the
finals, but something that any participant in the qualification world can do, but suddenly, it is not that everyone can, but a very good one. The news is that they announced that yesterday all the past problems I hope to overcome the problems.
Some past problems will at least be available on Kaggle comm hashcode will put your past problems on upload this way you will be able to practice them all year round and I think it is very good. option if they didn't want to handle that themselves now remove this and resolve the compile errors print I just did it in the last few minutes to debug something okay let's see some visualization of what happens in B I had problems with this visualization during the contest. Can? Play continuously you see a snake at the bottom in this test there is a limit of only one robotic arm and that is why it is optimal to just move like a snake all over the grid only once I heard that a right arrow works right ? enter works and then it's faster, so this is our solution for task B.
I can do this, one of my teammates. Kostka implemented this logic, it doesn't work at all for any other test if you need to handle multiple arrows at the same time and the tasks don't. Not only here also a task consisted of a single item, so it's not like you have to go through a greeting in various directions, such as go here, go there, etc. I think it's quite nice to see this and if we see a scene that serves the Captain. n I don't even know if something is happening or not, but there are several snakes on the grid now and they need to move quite a bit.
This should be better. Multiple colors. This will be better. Each snake has a different color. Now shows the assembly points. showing traces doesn't matter too much this test is not that easy because robots often try to pass through other robot territory and this is that strange test wherever Finkle is on the edge. We had a special solution for that too, but I heard that If one makes a good general solution, then it will work for both special tests B and F. We did this. I think that with that I would say that E is better to see that nothing happens.
Now it's time to search for the function. Work out what it does. do a boost that stacks Isis one, so let's just start at the start of the mount point, it's not like we're partially expanded, those are prohibited, those are tasksforbidden, tasks I know I can't do, I remember movements because maybe I want to decide, oh no. I'm not doing the best homework, if it's banned, then I keep going up to this. I calculate the maximum length, the total length. I want to estimate how good a task is and to do that I use a formula for scoring a task divided by the length I need and the length I need. estimate with Manhattan distance, in fact you should run BFS s to know the exact total length, but just judge to choose the best task.
I'll use this and that's it, I mount it and I do it starting from the mouth because every time I retract, it's great if this is valid now to do a task I go for targets for those cells that I need to visit in this order I run BFS from the initial cell until this thing I go like this so this means retract I hope that's the word for attract you know go back to zero if they didn't find it if they didn't find a path then roll back the change stack versus a stack it's already some size one if it exceeded the number of shifts then also reverse the change house if it did not exceed then really do it this task tasks performedreject the idea of this task that was current Chris body tags tasks delete auto this task is no longer available to anyone and when can and one can is an array which specifies when something this cell was last visited if a robotic arm visits any cell from time 10 to time 15 I mean until time 15 this cell is prohibited the maximum MPS of this doesn't matter too much this should be a little better Now I'll check removing this randomization because not really using that too much and limiting weapons is stupid to just count weapons.
Save this so it is available. Let's also ship. Let's see if it's that slow. My solution is proud to put the CPP dot. I just want to make sure my current count works. This looks like. being slow could mean you entered a while loop, let's just ship let's be alone, I loved the details as 200 out of 1000 tasks have been completed, 1 in 100 body cams have tasks assigned, this is that special test with just one game arm display. continuously and we can see pretty well what my algorithm just does. The black dots are mounting points. I can't enter them.
These are mount points and whenever we have some objective, I just go to the shortest path using BFS and then back out of the first thing I planned for today. is not always retracting to 0, I actually implemented something for that during the contest but it didn't seem to work, but it was after I went back to BFS that it was impossible to get it to work, now I can copy some of the cpp product that thing I wrote in the last two hours of the contest or I can write it from scratch I will decide at the time I make the CPC t-shirt yes, it is related to the fact that it has Crisium colors it says execute research simulate and execute it is from something that I I don't know if it is not from I Am technological competition or code versus let's rewind it's a little now my snake will try to visit ourselves a little more, it takes more time, did you calculate C and D D was already done?
I used a hundred arms and got the score of 1 million by the way during the contest, if we see here in D, we got a score of only six hundred thousand instead of 1 million and that was a much better solution and I spent much, much more. time on it, plus I tried different seats, different mounting points, but it was a bug in BFS, but sometimes it blocked everything in the future. I didn't uncheck the visit so any future BFS couldn't find a way, apparently I see it's quite slow, maybe because every time. I do all the tasks I did and see that it only has a score of 600,000.
The thing is, the best score we have now is not much worse. I'll send those two and then improve. I'll see that and do that. It's quite annoying that I can't send zip with all the evidence I need every time only to see that I was transferred since I'm polished. How do you recommend studying C++? Some cars on the Internet. I don't think it's my source of learning from ten years ago. matter I'm pretty sure this is B I want visualization I still think this is B what's happening I'm not doing anything yet I claim this visualization also had a delay during the contest maybe a refreshing connection something very interesting happened here because robots understand to some extent, what is available why don't you retract at the end or let me, this is what I could look at in D, yes that was the one in D, let's print in the final stack size of each arm and can I Easily improve speed?
BFS will take most of the time if you need some links then they are in the description at least of the YouTube video. I don't know if I put them on Twitch also on Twitch, it's categorical, right, a creative RL. I want to program, sorry. done, yes, each stack size seems to be equal to one, so I think the display is wrong. I hope the visualization was left as robot traces. Let's analyze some particular robot, let's say this orange one and the one above moves to the right, then to the right. left and it stayed here I don't know if that's good or not, I mean for sure something here is suspicious but I don't know if it's my fault or not, but this car is, I think pretty good, my options are to speed things up to investigate what I just saw or to implement some logic to not always go back to the initial starting point.
What about investigating first? This seems the most important thing. This was the here. I'm also clicking on Andy. What I can do is look at the output and for each robot to see if they retrace their steps how many you and descending order is the number equals you you three four five six that's stupid maybe I should have a checker I didn't write the print function let's make sure make it reasonable for everything in moves it moves as third that assembly is equal moves as back this should be good no if this statement is true then I think the visualization is stupid and it does what is the time complexity for this solution the complexity of the time doesn't matter optimization problems time matters if your solution takes up to a minute it's okay let's say if it takes an hour it's too much but you can run it on your own computer this is the no no let's try not to always go back to square one in solving iterate over targets and in pro i have something for that in pro iterate over iterator of this and i had some logic here comparing two consecutive positions but i experimented a lot with it and i'm not happy with what happened here as it said this didn't work anyway because there was a mistake somewhere else.
Can you teach us how to test and debug your programs on Linux? Test it by running it abroad in a small test. That's a summary. Let's safely say I won't. concentrate on this today see this is something very bad I don't always want to do that is index of a go right now it should be equivalent I it is I dream to find a path follow that path but I don't always want To do this, what can I say? The easiest thing will be that I have some difficulties, it is remembered in a pile. I actually know what another team did, but I don't want to just copy.
I've already heard some of the best solutions. teams, I mean if I'm close to the goal then go straight to the next thing, if I'm not last then use some special rule trick, what will that logic be and also if I also had that in the other coat he this model of fife is not for this means once every five steps I'm sure I'll go back to zero so I don't get stuck for too long if there is then just retracting well gets you closer to the goal what's up with that? well, this and the simple distance of Manhattan from the stack and this is the second to last item for the Hydra task objectives plus one, this is less than the distance between me and the task, stay back and this goes back one.
I want to run it first on test B 309. and without that, oh, but I do this anyway. I want to say more, nothing changed and this is very suspicious because in test B there are not all tasks that consist of a single objective, unfortunately I need to run it for something else like D, then D, I believe in something. startup will fail, no error occurred, it means sometimes I try to move from a place. I'm already there. I would know how to fix it in BFS if my current cell is equal to the target then just continue, I hope then it continues different.
The size of the different ink habit affirmation stack is equal to one sense in 964 because I want to make sure that after I finish checking all the girls within a task, as long as there are these two items in a stack, I do that and I'm still quiet. I'm not sure of the solution. I'm afraid that if I start something, the robotic arm may try to visit them again in BFS as well. Don't expect me to get very, very good scores today. Arm 69 tried to get into an already copied cell occupied by arm 69 we have some self collisions and this makes sense if my robot starting from here was like this then let's say down down down and this here and maybe the target is there and you might think that for Sure from here to G there will be no collision, but there could be some forbidden cells in the middle and then . but I don't want to make BFS slower.
If you try to wear a set, it will be very bad. I think BFS is the slowest part of my solution, at least now, so I need to pass the stack, this will contain information. If something is right now on the stack, it can't be unstuck, but something like that led me to a stack size error before. Do you do 3D before debugging? Sometimes I use gdb to tell me which line there is a runtime error, what is your plan after solving the hash code? they go to sleep on the stack when they move forward like cows right when I go back the stack gets stuck in the back the first stack in the back the second is Falls does it happen that I go back without dysfunction do I ever change the size of the stack it happened here and I hope that wherever I go back after?
Solve strange things or even solve certain terms of who stacks. Second size this will ensure it doesn't get hung up honestly I think you did it right guys I'm just saying you know what it's like so what does it do? The same thing says that your appetite grows as you eat more. I think it's a Polish saying: it doesn't matter if you're good, you want to perform very well and be in first place 14th, it's not so good for me. I think it was. Farfán six in the past in the final, true, at least now it is valid and it is worse than that, but I think now sometimes I move on and we will see it here in various colors.
What I mean. I want to say something. in bin I'll see that he doesn't, I won't see that in be I shouldn't just take task by task maybe this should be even smarter I don't know how to run this for sed and for sed see why I didn't send it II this discovery is pretty bad maybe because the snakes keep going through the net and that's apparently bad in this test, but it might be better to always go back. I don't see them continuing the movement unless it's another test where each task consists of a Single Objective Where did you learn to code on the Internet?
Why isn't anything happening here? I have some back that was visualization of Oh, I have the best score so far in C. So let's send this, but I need to do some research. The visualizations suggest that my snakes stop after one for Java Game, this is C. I think blue already did something clever. He picked this up, oh, and now he's going there. My logic works now. The blue should get here unless it's divisible by five or something like that. Get there and now it's stupid to go like that. Instead, you should back off a bit.
Go like I said, investigate. Is it true that in the middle of a game everyone stops? It seems to be true. So in a movement of that size, this will tell me how many turns this arm used. No, I have some static. I have internet but this DNS is wrong and I can use it, I can access it, I can't. I started using some tools on YouTube so that stopping a stream, some problem with the internet doesn't cause the video to break. I hope the same video link that still works in the past I needed to create a new link that was very inconvenient in a total score was much worse because of this not backing up what about this if something is wrong?
I already had it but it was discussed for several turns the game divided by 20 wait there is also an option to wait. I made a mistake. I repeat that many times the hours of who moves push their arms back and who moves, but there may be nothing here. This assumes we're still in Mount, but I had this trick. what if someone what if you can't figure it out then for so many laps just wait something is wrong with that new DB Pro to run in the back truck or any racing truck 3 5 5 oh if it's empty if the arms of the one who's empty move that empty if you start at five five and you didn't make any move, then writing means being at five five.
You could also implement a function. Wait, that will be better and you can reach out to chat. Try again later. Three to the nearest goal. For now, I'm usually going back to square one. Is there somewhere we can see the problem statement? Good question on YouTube. I don't think there is such a place, but let me fix that.It looks like I assigned all the homework. that snakes don't always look for the nearest box, I choose a task based on some heuristic and this heuristic is here, it uses Manhattan distance only to estimate, it shouldn't be more precise than calculating the total length as the sum of distances from the mount point all the way.
I'm thinking, in the meantime, let's look at the visualization. At least the beginning is good when your program works very, very well. So it's very satisfying to see those animations in normal programming competitions. Your program is fast. enough and it will produce a great correct result, but that's all. If you write a good program, you'll see its behavior in a drawing like this. Red Bull and wrap the coffee. Thank you. I don't know what froude coffee is. I know shroud is a streamer, what is brown shrouds, let me add this actually for some tasks. I'll check how big it really would be with Ephesus.
I will calculate it and then choose the best task to take on that will take the least amount of time. Can you make the arms wait for another arm to retract so it has shorter puffs? Yes, I can, but you know, expressing that logic is quite complicated. Is this an optimization problem? Yes, declarants find a way, so I'll do it. Actually find the best tasks using this simple heuristic, first double pour estimate of a task right now with this plus equal how I will also investigate whether I look at the scar or not because my goal really is to finish all the tasks in total 9 plus the same Manhattan distance between starting point until the task score divided by the total other is returned will be a good estimate here.
In fact, I'll simulate hell if I copy and paste all of that. I'm not sure this task is maximal. I'm not using this feature yet. I will run this to make sure that the score is still the same visualization automatically generated by the program no, the contest organizers prepared some visualization on the website best task, not best task I will look for double tasks, I don't know good tasks for each task good tasks by the estimate it gives me a measure of how easy this task should be for me to finish the sort, if it is empty then break, this means get a higher score, better, sort by sort in a decreasing way and, for the first ones, this just excites the F for cult versus I think They really tried the first twenty tasks for each of them.
I'm going to run this algorithm because I don't want to copy and paste this and then keep modifying in two places, so there will be what we need to push back on the stack moves, so this can be quite slow, let's create a function, let's try a task or let's do tasks with a real boolean value for real if this is false at the end of this I'll just retrace the steps maybe I can return something it will return something enter it over the goals I think I'll go back to the easier version what about that where I go somewhere and then come back, so this objective role, if this is the case, continue, this is the easiest version, no problem, what is this?
I hope I'm not doing something stupid, can you say it briefly? check the problem I did it at the beginning of the stream but in a very very very short moment you have this grid with moving arms our snakes need to reach some target cells, you can this is how they keep moving here each color denotes an arm they have some targets, they keep moving and can't collide with each other which is very hard to handle and he shouldn't really it's just a casual transmission this should be fine now i'll move him to do tasks some unrelated data.
I recently finished playing Amazing Spiderman on PlayStation, it was very enjoyable and enjoyable, it's not the best game of my life, but it's a very, very enjoyable, good game. I did homework and it's true, do it Kent, should I basically move this up? Yes, do not continue. I would quote this which returns information about how easy it was to perform this task or how long it took, let it return how long it took and mmm-hmm, that's a good idea and it will be minus one if it takes forever, let's say these approaches can continue, it's okay, make sure you go back to zero if the cans don't move, this is prohibited, where do I save the note movements?
Here it should be there less. one means it didn't succeed, it didn't succeed and in this case the move back sighs: minimum size this is the vector of moves before I'm done with this this is after so the difference is how many moves I made and I shouldn't be able to do it over here that forbidden undeclared don't do it there this is to direct you to the handle counter all this makes sense there is no return yet I'm not using that task delete in tasks I need to find this thing and delete let's do it like this that to iterate over tasks if its ID matches my ID then really do it to clear task counters is a very bad variable name because it is global to me time let's call it time needed please work.
I only came worried about success in unpredictability, yes a little. a little bit and I have some hitter cards that I don't hit at first. I don't remember. I think at the beginning of the broadcast I got a better score, maybe a C. I think from 700,000 I got to 800,000, but that's not the point. the point is to do something much smarter and this takes me a lot of time apparently final, I see you broadcast financial here in the viewers Greg hehe in polish it's called hdhd haha I don't know what it's like in other languages this car is worse so my changes are not well, I messed something up, iterate our goals from this move backwards, if you can, then Richard comes back with the move stack already size 1, if he took too many moves, then same thing, this is unnecessary after that, but no.
It hurts that the days of tasks completed the total score increases. I think this is fine, but I'm not entirely sure about updating one and returning the number of moves resolved in decreasing order, so it will be the first to be the biggest time you need it. Those competencies are mainly discussed. find errors, sorry if you expected something else, there is no maximum possible score because finding the optimal solution depends on the time explanation. What is this exponential? Write an algorithm that, for any input in polynomial time, finds the best possible, but the goal here is It's not to minimize the total duration or time or something, if in some time you are able to do all the tasks, you solved it optimally and a good solution with multiple heuristics will do it similarly.
I think just writing an optimal girl is exponential. I'm not 100% sure about that, but whether it was made or I wasn't sure, it was made for the ladies and the ladies still have it. I think there are an exponential number of states. I'm cautious about this part, maybe I'll do it here, wait what do I do? add US banned this something went wrong because my scar decreased and I thought I was moving a piece of code from one place to another but it has only been fully automatic if there are less than seven or eight pieces on the board I think Alright. but maybe that compares to the records with this thing here.
I have some real tests, it would be like playing against humans. We can create a computer program that wins against humans. It doesn't mean it's optimal, but it was good enough. Similar thought. these tests, if I solve all the tasks within the test of those missions, I will get the maximum score. Nothing has changed. I get the message "nothing important", a reminder. I'm trying to understand why this auto decreased after I removed one's code snippet. place another banned type decreasingly, so first we will have Maxim's car, well, let's think if anything changes if I do this, but now it should be increasing, so the first one will have a minimum score.
This should be worse, right, I maxed out before. It will also be why. Is it four times slower? That's suspicious advice. It took twelve seconds in the same test. The shroud says hello, remember me. I am a very old viewer. Was there a veil in my audience in the first broadcasts? I may be able to remember you, but no. I'm not one hundred percent sure, I think it's a rather unusual nickname that discourages worse now and this means that a moment ago it was better because I find the maximum. I'm deleting a wrong task or something.
Do you take the nation now? No, you can read my FAQ in the description. Something I said about that here is that if you have some general questions about just programming, many of them are answered in the FAQ links are below the video below the street. Is it correct to save movements? there, if we can't, it's true if we can, so is there something global? I switch when making moves, I do forward, but then I do this and back cancels the verbal unstack or maybe the discard decreased because I modified the logic for this. I don't think so, let's try that.
I think it will only get worse and I will make a very comfortable living as a software engineer, but I don't have time for one of my passions, which is algorithm competitions. What should I do? Maybe think about reducing your full time to 4/5 like 80% of full time your employer probably won't want that, but some argument is that you will be more effective, that is, more efficient, then you will have more time, a few more hours a week for this and that. a boy emerges who didn't use to put spaces, yes, I remember your shirt now I still do it with the slow button, how is it possible?
I'm sorry it's taking me so long to look at this one number, but there's nothing I can do. I can do it at the moment I could just move this back you should work less and give up your standard of living those are some answer tasks delete tasks start more this yes we are deleting this one because it is done why did I use only 39 arms? It's always the case, I'm limiting them to 50 and why were only 39 used, it seems like all of them were used, maybe some of them didn't do a single task, but was that like that back then when my solution was faster now 50? tasks were used 50 arms something is not equivalent when you work 90 hours a week it is a real problem we are sure do not work 90 hours a week unless you want to do it only for two three years because you are starting your business or maybe you are saving money to buy a house.
I'll save this as equivalent to CPP. I'll move it back. I guess I don't know what happened. Should I use control? Many times, yes, I delete them. two states before moving to this function maybe something was wrong when sorting what about those good fangs starting good tasks from scratch in that second first served? This should run in 12 seconds and give well over half a million points. Yes, it does this. There is some code that works reasonably and they moved this part for me again. What could go wrong? The traitor Berta avoided this. I also moved this memo. let's call it TMP or it doesn't work we will get a task by reference a variable can't either because I could modify it it doesn't work tasks should still work in eleven seconds and give me nine hundred thousand points it seems to work if it can't then continue on my wrong count maybe I didn't do that continue right this continues i mean its minus 1 if minus 1 rows are returned i add 2 in forbidden and repeat move this forbidden task insert point id did you have a check for the number of turns in this function perform tasks yes i got it everything seems fine continue continue return true do I return true where do I return this way?
That was a problem, wasn't it? it's done differently maybe this is why sometimes I back out and in this one I don't back out okay, that explains things proto now we have this do tasks but doing tasks tells me how long something might take and I can say in this do tasks for real return -1 return -1 else do this only if it is for real tasks, lower the total score below this taken, if not real then I need to move this back, but before that remember how many two turns I took now I can run. this will also with false value tell me how long something would take or that it is impossible.
I will compare some of the best tasks and choose the best one. The program will be slower but much better. Let's try five candidates or maybe I'll just be free to do it. pretty fast, it's not just a zero element, but the time taken for this element is that, but with the best false value of the comma inter max, what I mean, it tells me how many turns it took. For now I just minimize the number of tours, why won't I do it later? think of the scar to know only the number of turns comma that can be tid House forbidden forbidden insert world task ID task point ID then I can do the task, but this time, fingers crossed, the second thing is tid, that's the beauty of programming when you find re and finally understand what's wrong then quickly fix it now that you know finally this feature is ready run tests and see you, if not these tasks should take longer but I hope to see a score better than 1 million, then it's still wrong, doesn't your head hurt?
That happens to everyone, so I saw an interesting question 5 minutes ago. Well, nothing changed, so that's bad. Kunal Trump asked what do you like or is it aDisadvantage of live teaching. That's an interesting question, lifestyle teaching, live teaching, unless you prepare all the slides, you can't cut something out when I make a video. I can think a lot about what exactly to say. I could remove some boring part and redo it. The advantage is obviously that someone can ask a question but there are so many disadvantages imagine you are preparing I don't know anything giving a presentation versus life versus recording is I don't know I think it's obvious what I'm talking about consider a few things This will be the best from them.
It's slower. It's not slower. Why isn't it slow? what is happening more than a million and actually works faster could work faster because there may be less dead spots the puffs are short or something like that there I will find the way the best among five candidates the best among ten candidates and this is that moment of satisfaction what is my best score on And so far 1:07 can we beat that one zero five and this is with 50 arms? Can we make 100 herbs? Do you work as a freelance software engineer? There is a gap in the description now my job is basically to teach 400 arms, that's how it was.
Isn't it so good what about 75? It makes sense that a hundred arms would cause a lot of deadlocks. I'm not doing great, but it's better than a moment ago. I also see what happens if I allow these 75 arms to be fine. I re-allowed Don't go back to start to continue a path and it made the score worse. I'm still not satisfied with what is happening maybe it's time to run it in C or D. Here I will visualize everything that should be an interesting moment for you because something will happen on the screen not only in the count C C and D are working, he is the one that would send which against some token exception and I need to update this was a DS also calculated and this car is very bad for some strange reason strange strange they are still being calculated here a lot of people stopped after 2000 here this is a test very short and I still have these things unblocked, not that I want a recent test, I think it's time to retract more intelligently, don't you think how to do it? make it easier.
I can try to go back a few steps and check with BFS how good it would be or I can. It's hard for me to run BFS from the target cell because I don't know when it will be in each cell. I think I started this implementation with some wrong assumptions. I wanted to do all the homework. I chose one arm for the entire task. It might be better to do something possibly dangerous, so yes. I have some very stupid logic to expand on. Maybe you want to move second by second, not just plan everything out, but this is stupid because you're looking into the distance of Manhattan.
I would find an easier verification with my logic, it is impossible and I also see that it was probably done with some bets Karl because I have that if That works well maybe for one test, but not for the others. It was every so often. I do this, let's increase this to infinity and run C and D again. I'll run it again and think out loud. Everyone is stuck. What's happening? I'm sure the logic of whether I should retract it or not is stupid. I have an idea. If I'm close to that goal and then move there, what happens to that?
My cost is too long. I'm stupid as to where I can find anything. my code estimates this, so that's the logic, we just compare the distance from Manhattan, well this, if you allow this special case, then look at the next target, find the distance to that BFS thing from the current target to the next target , the current tip term is not -1 and ladies and gentlemen, this will be TMP is smaller, equal to the stack size over 2, if this is so then do that, else retract the next target if I have a stack of length 20 and I see that the girl is at most 10 moves away, move there, otherwise retract I' I'm very happy because BFS will return a path that has this point length, this is not 0, well, if God is the sickle of the next girl then everything is fine and the moves needed are zero if the girl is not the next target, mostly I don't like that, but if it's the same. to zero means I didn't find it outside, so it's some kind of infinity, if this is true, if it's close, then I don't need to retract, I also don't need to retract, no P team moves needed, the next step, the next thing I'll add is , otherwise, it's not that.
I will go back to the beginning. At each step of the retraction I will check this condition if I can be close to the goal and I can reach it and I can experiment with this a little bit, maybe it should be smaller or minimal and do the trick. d 1 million points, it's strange how, but my solution is that it's still five million points, he got enough for a 6th place in the competition, but not even close to the winners in the middle, people stopped finding new tasks , those numbers we see are still being calculated. here our moment when something last moved the number of turns in the game is 200 someone stopped 12 months before the final code apparently it was not possible to perform any new tasks but this 80 seems suspicious now it is possible that it is around a hundred.
Don't know. I like the fact that most of the snakes are now still here, almost all the territories move up to 190 movement, so is this the correct visualization? I only see 10 snakes moving in a line in the hundredth turn, only some snakes are moving, but here this is written, those are moments when they stopped, it seems that another snake cut them, yes, they can be next to each other , but this is the last useful move. I don't make moves for something unless I finish a task. Look, still calculating how long it lasts. The broadcast has already been going on for two and a half hours.
I'll spend another hour today maybe we'll come back to this in a few days if I have time. I like those problems, but I have to say it feels discouraging that I'm doing so poorly. It's so bad that I'm not doing my best, it's just that most of the time winning seemed to be within my range. I could do it. If I was like this, I didn't understand that I will run this over and over again. Submit it, do it and try it. visualize that if someone has recently joined the stream, they can find an issue statement so they can read about what I'm doing in my github repository.
You can go, we'll get hyper on YouTube or we'll see the link in the description and the hash code is here. 20 $25 around that PDF on my github, yes, but I did the same thing, a hundred arms were used and it stopped working around 180, create this line with around 200 characters, 200, this is 175. I have to remember to display your dozens and show The last two that retract after I finish performing tasks, you think I stopped like this. I think the viewer had already recovered it. I knew it, yeah, almost all of them here last up to 190 or so, so I hope the visualizer still bothers Percy. it's going well, better logic, bye, what about / because if it's too close, let's do the other thing first when I get back?
I can continue with this track, don't listen to them, this didn't break because this is a good starting cell, otherwise go back myself I'm still afraid that my approach that I had taken will lead nowhere because I do task by task . I assigned all the homework well. I know for at least one computer in the top row of fingers that it is another computer in the plant or for them to decide things second by second, although this program is very, very slow because every time I go back in one I run a separate BFS. I could do a trick and repeat this four times.
Maybe Route 6 should be six times six times faster. I don't know anything about coding. but I like the barcode if you want to participate in a similar competition maybe not so similar there is this contest what is called first day there is a website stupid goodbye with many contests and one of them lasts three months and is called Statue of Liberty, the name is stupid, but it's about finding a set of numbers such that your power, the sum of your power, satisfies something that's not as good in terms of visualization, but it's much easier to approach and this is what another one looks like optimization problem.
For example, you can try a bunch of numbers and you need to find the best possible set and you can run the program on your computer for about 10 hours a month, but first we need to implement any program for that, we will approve this one in the box, if anyone wants take a look, the website is called Alzheimer's Man Programming Contests. They calculated it and the score is no better. I feel very discouraged. I don't know, I don't need this, like I said, my Fink, my solution is. I'm not going anywhere, oh let's say you're not much of a scholar, though let's at least visualize it, I don't get hard answers, the map is bigger, that's why it took me so long to calculate C, because each BFS covers a large part of the grid .
The robots in this test hardly collide with each other, what did the ping do? But it's very important to choose good tasks and right now I'm deciding to just look at the total time it will take. Instead, it should be the scar, the pink color should matter. You did it? It keeps moving up, so it's not stupid at first. Something strange happened. Oh, pink, I tried to avoid orange. I think the pink is moving to the left. I see the target cell for pink over here, then the hexagonal target cell is there. It should retract when I take a step forward, it's a little faster, but it shouldn't retract completely.
The code for which this is the output draws completely or nothing at all. I'm still eyeing the pink, it may increase I think. increase it actually the pink is on the bottom right this is more like purple it's bad that the pink has moved all the way down and then up where does it go there why is it a little hard to move that's wait, wait, let's wait a moment hello Marco Shiva I I have no idea why the pink ceiling is like that. Also, I didn't watch the YouTube chat for a long time. I need to update what that means second by second, since every second I've gone back to decide what should happen, maybe the pink team.
I decided like this I don't know, I didn't see any objective down there what is the time allowed per turn. I don't understand it, but time is the turn. Yeah, I think I'll end the broadcast in a moment. Not my program. It doesn't work very well and I think I would need to rewrite it from scratch because my first assumption will be that I will choose the rubble that finishes first among all the ones still working and just do some tasks for it. work, I mean some tasks will be transferred and then a large part of the grid will be banned for a long time, so I think these 5 million points are easy to get, at least doable in 4 hours, my approach doesn't seem to work. but better to get like 6 million, my scar is still enough only for 6th place not even close to this 5.1, what can they do?
Yes, that would be all for today. Should I do something else with this? Anything simple you wanted, there are things too. like changing the number of ms to change the mount points where we start, but it seems so unimportant what the wait time per turn is in milliseconds. I run this on my own computer. I can run this. I have a test file. This is a test file that describes the tasks where. our mount points how many tasks are here one line uses a sequence of point coordinates and if I have a very powerful computer I mean I can even run this in parallel on multiple threads change your approach today I'm not going to rewrite this from scratch that It would take a long time, so I think this is not surprising at all.
Your fingers have a very nice car, so close to 7 million, their approximation is about 2 per second. I decide what to do. I will draw this if you are a snake. I know this because I talked to them about it. If it's a snake, this is the mount point and now their next target is, let's say, this is the target, so what they do is they run BFS between the target and this current snake and they find the closest one. point then they retract to that point and in their solution and from this moment they will continue in their solution a big problem is what happens if there are dead looks because as I said it is not that they have planned the whole way, they did not make it known what a snake will do then maybe she gets stuck maybe she can't get to the next objective so they have some extra things like once every few turns they all go back to zero at least it was useful in the test e and if you're stuck because some other snake blocks, then you wait or retract a little bit of things like that and three against my logic was just thinking what is the distance F as distance from this to that if it's closed and moved there and a moment before.
I had something even more stupid. I just compared this point or this point. I checked which one is closer to the target, but this doesn't account for everything. What if there is another snake here? So I need to move around her if I'm white. snake then I can move like this to aim, but here it should be better to retract. I think eliminating all that retraction up to here maybe even down to zero. Let's move there now. We had the idea that maybe if the grains were smaller or with a little help from a computer, a human would solveOk this problem, but the sand was too big.
Who won? You can verify that here, the past glory and the steam with Canada, Kurt, the three teams, those teams have someone very strong in competitive programming, actually, the fourth team as well. There is also something here with very strong people in optimization problems with psycho wle ite. I don't know how to pronounce that politely and it cuts a niche if I remember correctly, those are three very good people in coggle top coder marathons on optimization problems in general, but this was a very short contest that doesn't fit well with them, so I'm going to end this broadcast.
I hope everyone has a nice afternoon or evening, whatever your time zone, this could be a whole day. I'm going to sleep early because it's around 10:00 p.m. Whenever I plan new streams, you'll find them on Twitch DVD/Arita. I have a schedule here, it's usually empty, but once in a while, once every few months, I have more time and then I would stream a few times a week, only you can. follow me on Twitch and then watch this from time to time, but also feel free to subscribe to my youtube channel Arita and Arita; currently you are in I provide a lot of small code problems but after that this 30 days contest will last I will surely take a break from the late code because now it gets boring.
Problem number 25. I already recorded today 26, so maybe some competitive programming and cow jumping in the second round and then in the third round. I need to train for that. How about we do some weird color contests or past Cullum contests? Something like that. Yes, thanks for the transmission. Good night. Thank you. You are welcome. Broadcast again tomorrow. Please, I don't plan to do it. You know, weekends are better. People have more. time including me, so that's it, thank you all for watching and I'll see you in the future or just in my videos on YouTube, bye, the broadcast doesn't want to stop.
If you have any copyright issue, please Contact