Google Hash Code practice

sound test sound test one two three hello hello hello good morning i guess uh yeah good morning to you you like swishers hello everybody today i will stream solving some optimization problem my teammate will join me we are trying to connect via voice hello from india hello hello let's say that we will start in five minutes here sorry about the delay i will do some explanation yeah [Music] you [Music] i need to choose a problem to solve we as a team yesterday we tackled this qualification round practice problem but it was pretty boring i can still do something there because my teammate solved it like near optimally with some solvers some let's say with a black box solution where i didn't really do anything smart there in simplest plus yeah we can talk in english all right so chad you're hearing my teammate eulek jks i will put some info on the screen because otherwise people will keep asking then you're jks right in code versus yeah okay jks underscore pl because i'm from people i see done you can go see how it looks on the stream all right looks nice and handsome great okay now i already said out loud that we solved this problem the practice problem yesterday i still actually didn't code anything smart there in c plus so one boring possibility is to just do some stuff for this problem in c plus plus in particular try to get like you know the same score that we achieved yesterday but without grubby all right that's one possibility there is a train outside another possibility is that you can explain to me what we can put into gurabi so i would know better or we just can take a completely different problem perfectly something with visualizations needed so do you really want me to give you a grubby stream i don't know i no i i don't think so but this was an idea of mine but i don't really like this idea me either so there are actual heuristic contests or maybe there are more past practice problems from google hash code sure i mean i don't know too many problems of google hashcode so we can pick just whatever he wants then i will try to find something i think that they moved their problems to kaggle.com i will try to search there you can also try basically even past practice problems are available i don't know where to find them then chat same goes to you do you know if we can still solve practice problems from google hashcode from past years working on it at least one problem is available on cargo which one traffic lights traffic signal but that's from the finals or the qualification round because i remember the name why is it so difficult to find i just i now searched for hashcode in kaggle i can see some tasks but i already know something archive of hashcode somebody gave me a link qualification but there are no practice runs here okay then there's also replayed call replay code challenge but i think i also know all the past problems so then we can go without cutter heuristic contest but that one doesn't have tests so we could download them try competitions tab i mean competitions on air no not here so nope and i'm looking for something in that cutter heuristic contests which i haven't solved and perfectly it should have some kind of map or visualization i see something about genome sequence hot code you like have you participated in any heuristic contest no no there is an ongoing heuristic contest but then i i doubt we can solve it right now i mean not on stream right yeah yeah exactly but also we shouldn't do it then together we shouldn't collaborate i think all right duration local time remaining time five days i see so it's a contest lasting two weeks and then i'm closing this one can solve it then something else i don't know how i have closed the website well there is something about setting rectangles i will give you a link okay thanks we can read the statement and then decide if it's something we want to try so is it something we want to do um i haven't understood the the point for me yet yeah i also i don't understand exactly the scoring function i guess some kind of uh rectangle packing but you have to put a rectangle in a specific place yes and we want a proper area or at least close to it i think i think that the formula says you're also given ari no i don't know what it says well something okay are we solving this one sure sure but we can also pick something else uh i don't mind i don't think that there is that much choice uh there were three at qatar heuristic contest i tried one of them so i'm okay with this one i don't want to okay so we'll go we're going with this one there are some tools but while it's okay if we use them i think we also should try creating our own tools but i'm downloading them do you understand what is s i i don't see s i anywhere else maybe it should be something given to us in the input but in the input we have r yes there is r and there is s is it minimum should we minimize s or something what is this i think that s is the actual area oh yes and the area is s i okay so we we get the target area r and if we get area s instead there is this formula which basically measures the difference okay okay that makes sense the closer we get to this value the better oh yeah now i know i see it and the area is can we output only integers yes we can output only integers then the easiest solution to make everything to be one by one and let's try to split the work in some way between the two of us do we want to use the rust tools or do we want to just create everything from scratch because we will not have something like that in hash code not a smart person i've turned on the this card so hello hello you like do you hear me uh yes i can hear you now i closed the discord okay and still i was talking to you okay we need to split the work in some way and do you think we should use their rust tools or should we create something they provided input generator and visualizer we can download them all right and but in hashcode we will not have anything like that okay but the question is uh is this input generation just for us so is it some kind of random input generator or is the input random actually the input is random according to the procedure described in the problem statement in input generation section as and the visualizer and generator is just no it's helpful but we don't need it all right i mean i can treat it as an exercise i think so right right visualization for us yeah okay so let's say that we don't want to use their tools right i mean maybe once we can do it just in case to see i mean we can we can use input generation because we'll get in right but if that's implemented in rust then whatever it's easier i think to implement our our own generation okay right um so do you see a spot where i can submit a solution actually or there is no submit button yeah like i want to submission at the bottom if if you are logged in at the bottom there will be a place where you can paste your code just code we do you don't submit output files group tasks will we talk about the hashcode practice problem i don't think we have any mark done we don't have anything more to say than what is already discussed in code forces block eulek jks he solved it near in a near optimal way with grubby solver i tried something in c plus plus but i didn't get close to those results our other teammate actually got a better solution easy but it's all already described by other people in code forces okay then i will start writing the the actual program that will read the input for example and let's say that you take care of the generator according to the procedure described by them the random one in input generation those are two separate parts let's do that do we want to use github on first day sure okay or i can set up jupiter if you want i think that github is more convenient sure if you want to create a repository and give me access that would be nice all right and again sorry i didn't hear that invite pending just for you okay your profile picture says 200 iq yeah it's a nice it's an intimidation tactic i guess okay i cloned the repo so we can work i'm okay i'm reading the input and stuff like that so i'm starting the actual program i think you're the only one who doesn't use our templates i marek and conrad we all use the debug templates so you will need to learn how to compile in c plus plus with local and without oh yeah i know that just send me the please so i see there is a question is there some method to know that basically you can pass flag to compilation capital d and the name of the flag so you would write something like minus the local there was one question in the chat about this yeah okay so can you submit the template actually [Music] i need to set up no password submitting no you can't it says that you can only use ssh keys does it mean i need to clone with ssh already yes okay i mean you might have succeeded in cloning you just need for push i guess well i i can copy the instead of i can clone with ssh instead of https if that's what it's about it gives me a different address and i can say git clone and then this address git github.com something something uh yes yeah so i mean that's the clone part and the other part is pushing actually but in pushing i also need to do something in a different way uh yeah i will i will tell you what to do on this card i see then let me first try to do it without this because maybe i set the key already in the past [Music] i mean additional keys don't hurt unless this is something but i think i've already set this up in this pc maybe all right all right if you can't with http https instead of ssh yes it works just i need to remember to next time on first day do that with https i've pushed it yes somebody is asking if this is a paid class no yeah very well played no i'm not i'm not paying anything i'm getting this github knowledge for free okay we had a slow start it's now half past 2 p.m but i think okay let's say we start measuring the time from now or from half past two sure i want to rename r what do you prefer target goal area needed what was the question i want to rename r the input r into something else target does that make sense because sure go with targets aria would probably make more sense but whatever just that was uh asking how can you get upper bounds in in gurabi so what do you mean how can i get upper bounds in guru i know that was the question i mean how grubby does it or how i can do it from in in black box way i have no idea how can one know the upper bound of scar achievable without actually getting it oh so the question wasn't about gurubi uh okay well then then there are various ways to get upper bounds for scores for example if you in this problem that we have today we can get a very easy upper bound for the total score which is for every rectangle you can get at most one point so the upper bound is the number of rectangles i am thinking about a way to store the rectangles like how it will become how to do it so it would be convenient to shift them around but i don't have any smart ideas me then probably we just have to if we were writing operators ourselves so i'm i created this tract for rectangle with the input data and now i'm just adding the corners for corners to it and that's it i'm not sure so i will give the problem link to the chat reach out now exclamation mark link should give you the link to the problem statement does it work in incognito yes and the summary of what i'm doing is that because i know past google hash code problems then for the sake of practicing before the first day qualification round i and my teammate we chose one of other optimization problems out there where you need to do something as well as you can and we just will work on that for the next i know maybe two hours and for now we are just starting i'm here reading the input thinking how i will want to store everything okay i'll grab back i need to switch to linux okay see ya see ya so chat my first idea is that i will make every rectangle very very small just to barely contain the element so it is supposed to be here then i can just say this and for now the other corner will be what's the same it's a strange condition that thanks to those halves the actual requirement is this that x1 is greater equal x and x is strictly smaller than x2 i think that it will be easier to get through to simplify this condition to just be bounce inclusive bounce from both sides for now it's okay so i need to make sure that this is true x2 is x plus one this will be a very very small rectangle for now sir check i will do this in order to just check if my format is okay and wherever i can submit whether the score is exactly what i would compute because the website will tell me what's what's the score then i will try to make this a random rectangle of size five by five or so and just to make sure that no two rectangles intersect if so i need to shrink then i will maybe for every rectangle binary search how big it can be i think it's a reasonable start oh and first i will just make everything to be a square so rectangles are very is a very long word is there a shorter maybe add does that make sense yes i think that makes sense so those are rectangles but now the typing will be so much easier ads adds ads and intersects jks is telling me that he now switched from windows to linux because he needed to start actually coding and his microphone doesn't work on linux so he needs to use windows for microphone and linux for c plus programmers we programmers we aren't very good at using computers i think wsl it's not perfect i used wsl in the past i still prefer virtual machine i we are using this card but his microphone doesn't work and yes i told him to try a phone it's fine he will be fine when two rectangles intersect i think it's easier to say when there are disjoint that happens if my x2 is greater smaller equal than his x1 r and here are series of multiple conditions just let's not mess this up all right i have no input let's use the sample one first okay it's fine but now if i make this bigger five and five still fine fifty fifty assert failed i'm just making right now squares of psi a fixed size and if i make them big enough there will be some intersections and julia stop spamming please and use something like a google translate because others could not even understand you what did i do jks right now i don't think he's connected by this card is square optimal here no not at all but you want to start simple you always want to start simple of course sometimes it should be optimal to go further away in some direction instead of making a square but squares are easier at least for now scoring or first maybe output this this will not work if i reshuffle the rectangles but then i will sort by id hmm zero everything should be up to ten thousand i think it's just in this order where was i here hello hello hello hello yep we hear you hello can hear me chat you can also confirm but i didn't change settings so it should be fine yes i confirmed that i can hear you well when you are gone i complained about somebody in the chat named julio and somebody else said poor you like that i'm complaining about you even though you're not here somebody with similar name is asking about cost of these classes okay so how much do you want to pay me i don't know if i can afford you but i can pay you with exposure is that fine okay sure okay so you're getting exposure right now you're welcome so so far in this code i read the input and i'm what i want to create small squares like one by one or five by five make sure that they don't intersect output that submit and see that i'm getting accepted rather than wrong answer that's my goal right now okay uh if you can hear my keyboard too well just tell me can hear it but if it's annoying the chat will tell me usually people like hearing keyboards i don't know why i even thought about getting a louder one because of that okay one more thing can you send me switch to vm maybe why would anybody switch to vim exposure is taxed 8 or 12 that's interesting so you need to pay back a little bit of exposure to the government okay i got 47 accepted and three wrong answers which is reasonable i'm now printing squares of size 3x3 now i will make it much smarter i will make such a size that they it will not intersect with other rectangles and there are some limits actually it's strange that i got wrong answer because oh no wait 1000 seconds to submit again how many we must wait half an hour between two submissions oh that's bad but there are two of us so we need to wait only 15 minutes oh okay i think this condition was introduced during the contest so that you wouldn't spam too much which makes sense if you have localities for testing well i can by the way push code that i already have in case you want to use any of that that being said no more what you go ahead that being said maybe during a competition it would be better if we before talked about sharing some code between the generator and the checker and my actual submission what are you typing the generator yes okay then good that part i think it's okay if it's totally independent so i'm not sure yeah it's it's very simple am i planning to draw an explanation of my solution no yes i i need to do it from time to time sure but right now it's not very smart so you like just for your information what i'm doing now is starting from squares one by one then for every square i just keep expanding it into a bigger square as long as possible yeah makes sense i open it you can do some kind of local search sorry local like improvements yes and right now i think about it really very much about squares i should treat the dimensions in a different way also i should actually consider the requirements about the area needed and i should stop expanding once i hit this area yeah that makes sense then for everybody viewing for everybody watching here's information about what i'm doing for every point i need to draw a rectangle containing this point and just going starting from index 0 i keep expanding rectang a rectangle actually square as long as possible oh and i'm now doing it to the right and down so it's like this now if i keep expanding now it would hit a there would be an intersection so i stop and i'm saying okay this is the rectangle then i do it for another one and it would be also limited by the coordinates limit it's only up to ten thousand so in this test i think we would end up with something like this i can i will visualize that using the website they provided on the official website hey we have a drawing so from every point i expanded right and down scoring where is the scoring so it is allowed for a rectangle not to contain a point and it we just then get a score of zero maybe it's sometimes optimal to skip a point yeah but right now i'm not allowing that in my code and for a long time i will not allow that sorry i didn't get that once again for a long time i will understand i will not allow skipping a point it's theoretically allowed in the output for a rectangle not to contain a point you just don't get points for this particular rectangle yeah i mean then you can just not place the rectangle at all indeed and i thought that it is forced because otherwise you get from cancer all right [Music] all right uh do we want the generator to be parametrized by seat or just whatever random input is good i think the seed would be nice so an argument in terminal our arg one this car i computed locally agrees with the online visualizer they provided the not the one in rust but the one in the website so it seems that my code is correct of course it's very stupid but it's correct good all right i've pushed my generation code okay and i will push my code as well okay done i pushed can see that now in my code it's very easy to make some improvements like stop when you reach the area needed don't expand just to the right and down stuff like that but it would be nice to think about something that is actually much better than that i think we should switch and we should split the work and one of us should work on this greedy algorithm and the other should try to optimize the solution further uh yeah i'm thinking about optimizing this solution actually i think something like about a beam surge so we would like maintain some kind of population like hundreds 100 good solutions and then you would you take them somehow what are the limits and time on this no but i think that just a simple locally i think you don't need populations you also don't need any kind of like real annealing where it will be just looking locally at some place and changing two or three rectangles at the same time and if that improves the score we can try to fit one rectangle for example like get one score for it or we can take too many boring neck rectangles and get maximum score for just those two rectangles or something yeah so you can think about this second part of given some solution keep improving it like total independency or from your code well you can look at my code for the formatting unless you don't agree about some something like how this extract works but generally i'm okay with using my code where i will keep modifying my part but already there you can see the format of my output which is basically that i populate the struct so instruct add my my solution my choice of rectangle is just described by the corners x1 y1 x2 y2 and right i can see that if you want to switch to some different format from that it will be easy for you to to do that no i guess i guess that's fine i will answer some questions from the chat had stupid algo yeah my my comment name was at stupid algo well this is a very very stupid algo can you show practice around google hash code code please we solved it in gurabi so i'm not even the author of the solution and just see code versus discussion for anything about that practice problem i don't think i don't have anything more to say than what is there already in code forces here on this page go to hashcode2022 practice round one pizza discussion that's the block name in code forces is there a difference between practice sessions and competitive sessions sure right now i'm more you know chilled i talk with the chat for example during a contest we need to be very efficient and for sure we should have already prepared the github repository what is max antique yeah i see yeah you are just expanding in one direction right yes that's right i mean two directions but simultaneously yes i i should do that independently there are four directions and in each of them i can i should keep expanding as long as possible and i will make that change now plus i will stop when when i can also i think that the drawing will be more balanced if i don't focus on one rectangle first expand it be done move to the next one but instead i will keep expanding all of the rectangles so i will make a form of that 1000 times does the following for every rectangle try expanding it by one in let's say a random direction i will experiment with something like that but it's it should be independent from your improvements later yeah i see okay got it uh sorry good question do you rely on order of those rectangles um not really they have ids i i for now i didn't reshuffle them or anything like that but they have ideas exactly so we could reshuffle them but before giving the solution to you so before providing vector of ads for your solution i can sort it as well by id in line 69 there is cerr with some debug line you can just remove that because it will it will print too much stuff in the output there is c r r s space r e and d l just to remove that okay sure i'm not touching that anymore is this contest winner is whoever gets the highest score or you need to get perfect score the winner is whoever gets the highest score most of the time you nobody can achieve the perfect score yes i use virtual machine you you compile you like i think you compile with some different saturn flags of flags than i do because i have some warnings when i compile your generator declaration shadows comparison of integers it doesn't matter i mean i know that it doesn't matter but you can just as well compile with proper flags um yes i can i mean i get those warnings as well so i see so it's not that you don't have flags you have but you ignore the warnings great yes i am conscious of the dangers but i i ignore them anyway amazing idea i like to live dangerously has anyone ever got a perfect score in a heuristic contest yes from time to time it turns out that the problem can be solved or just the tests are easy enough what was i supposed to do all right you i'm now implementing something so that i could run a program for 10 different tests generated by generator with seeds from 1 to 10 and i want to see the average score so i could compare how my improvements help on tests on average what i'm displaying now is the percentage of that final score i think that that's a very very valuable number hmm okay now i run my program for 10 different tests i write down the values here now i want to take the average of them where i'm sure that this can be done in bash but i don't know well enough so i will create a separate program called average okay we have the average but i would instead prefer to see it divided by actually it's not easy for me to like shrink or shrink one rectangle such that it doesn't intersect with other rectangles i think that shrinking part is easy but i agree that expanding might be difficult i think that it's okay to just focus or focus on such cases where we will not mess up anything where we will not sorry what so if you by expanding to some direction if you will mess up multiple rectangles if you will have many intersections then just don't ignore that place don't fix anything there don't do that all right yeah i mean shrieking after some invalid expand that's what i meant chat anybody understands what why i'm getting this warning i want to print the percentage and then a new line i need to do backward slash otherwise percentage is a is a special character when printing percent percent okay thanks thank you okay so we have the average i can just run this and always i will have the average score out of 10 tests on average i have just below 60 percent of the possible points i will see what happens when i don't have this 43 points and now i want to repeat this twice to separately handle vertical and horizontal and i think it will be slightly better can i even do that no 64 percent that's better but i think that it's even better if i don't do it separately now let's once expand in this direction and twice in this other direction so twice do this hmm i will refactor this later that's not a nice way to code what's a nice way to do it either i still use print because it's convenient for me i know how to use print you you now i want to expand in four directions so in in an infinite loop i iterate over four directions i move the add i expand that in that direction i now am creating function to check if everything is okay so i shouldn't intersect anything new which in the future i will do that in a faster way it's stupid to expand by one check if intersect expand by one and so on we just can once find the nearby other rectangles if this then also falls finally iterate everything else [Music] 69 when scoring the check failed something must be wrong here also i should write down stuff like this so i will use the chat as note two directions only is 64 percent you're like just for your information i'm now trying to expand into four directions and something doesn't work do you see how to do your part oh so we are actually doubling work because i'm expanding one of my improvements expanding but you will do it in a very different way i believe i'm doing some kind of binary search until it intersects with something okay then we will both need that part but you will need much more and i instead will also anyway think about other things like how do i initialize the rectangles in a smart way maybe i will reward for them for something all right when it's not okay you should break and not check other directions that's not true maybe it's impossible to go in the right direction but in the three other directions it is possible i want all the four oh maybe not that's of the fine 74 that's great all right i see that gupta now notice the error as well we have 74 percent but now one more thing is i don't want to do it in this order that being said let's see what happens let's visualize that all right we often will get squares if something can expand freely then it will be square forever i want something with bigger and i wonder what's the difference between blue and pink all the rectangles contain the point for me and i think i don't allow the area to exceed the given area because i then don't make the x expansion maybe it's about how well the score fits yeah i think that ping means that it's a perfect score and blue means it's not a perfect score but 149 if it's too small it could expand to the left well that's not what i expected now what's this what am i looking at maybe the visualizer assumes that there are at least 50 items i'm not sure let's get back to this no it's easier for me to analyze using smaller data now wait those rectangles only expanded to the right and down maybe something is wrong with my coat all right x1 y1 not i shouldn't move the point here you go but that's a much better scope oh maybe not i i pasted the output and now indeed we see scenarios where the answer is no only if our the rectangle will not be perfect only if it's surrounded by something this is one test and this will be another you like you can take a look at my screen at my you know the twitch stream honestly it doesn't work for me the twitch stream oh i don't wait it works what did you do i i implemented moving in all four directions and i think that pink denotes in their online visualizer pink means that something is a perfect area we we get the score exactly or close to exactly and blue means it's far away from the proper area which here almost it always means too small basically we never want to have too big of an area because it only blocks all the rectangles as well and i think that looking at this drawing might help in analyzing what should be improved basically other rectangles should be moved away to make space for the blue ones and yeah i as a human i see places where that can be done here in the bottom right the 34 well some some shapes look like they are sub-optimal like those long long shapes which could be fit yes but maybe some other rectangle blocks us from expanding very early on like this 66 should be moved more to the right the 34 it should be moved down a little bit because it can anyway expand to the left so maybe every rectangle should also have a boolean value whether it can still expand in one of the four directions and if so then we know that this x this rectangle can shrink in any direction as well if needed or we can just shrink it to one pixel and then expand randomly good point so forever for any rectangle if you want to make it bigger because it's now too small then for every neighbor for example you can shrink it down to zero expand the one you wanted to fix and then expand the other one and see if the score improved but in case like 71 and 73 so this those two here i think that maybe even they should be almost vertical or what about this if you can fit 71 then yeah it seems that the following logic might be very important given to given a boundary of you know where you can operate and two rectangles you basically we can reset those two rectangles but given two points that are close to each other and they are needed area it might be good to solve that optimally like here 71 and 73 given some white area allowed we might want to say think how to fit those two in a nice manner okay um i'll try to sell my solution now okay just checking if it works do you have something that started from scratch or started from my solution i started from your solution and just wrote y clock minus start time clocks per sec four and half improve okay that's fine you i think you can submit what you have in that coder you can also use this visualizer to make sure that your output is reasonable and but then we need to actually update stuff so i have a much better solution now but also because of that your updates will not improve my solution more and on average now i have 86.5 percent of the total allowed score 86 percent of the points which makes sense a lot of rectangles are perfectly done yeah i can see that good job i wonder whether someone can record my mechanical keyboards and try to get my password for add code maybe given enough data if they also know what you're coding so maybe it's easier in my case if i do a lot of coding where you hear it and you see that the code you see the characters then maybe you can match that with your password have a lot of data yeah yes i think hundreds of hours of live streams this is why in most almost all the websites i use how is it called password keeper google chrome automatically saves passwords and suggests random nuance are you working on a file product uh cpp but i can work on some other file yes i think for easier merging you can create a new file and work on that one you will also push that new file instead of pro.cpp okay i'll name it julek drew like in polish with dz no in english because it's an english stream okay okay i know what i was going to do i was going to change the order of expanding where first is that enough huh i see your wrong cancer in recent submissions in etc yes oh no and i have to wait 30 minutes what that's right i told you now i wanted to i warned you about it i wanted to make some easy improvements i know i was aware of the danger but i ignored it anyway congrats so i now have an average score of 90 90.7 percent okay how about you send me those evaluation scripts you have yeah i will just give me a minute pushing done all the cpp files you need to compile by hand like if there is gen.cpp you need to actually create an executable call to gen and then there is s.sh you can open that script you will see what it does okay sounds good if you're inside change pro to julek then drew like will be checked not real actually in pro i did something so that to the standard error output i would print the score at the end so you need to mimic that or i can look at you like that's fine i can move dru like to my program as well and then we can continue from there sure whatever whatever you wish i wanted to go with my [Music] idea so that i will just shrink some rectangles and then expand them in some random direction that should work well i guess yes you should do that oh yeah i got an ic are you winning i actually don't know where can i see my scores i don't know my submissions uh here's the thing somebody in the chat suggested but i think it has a disadvantage so they are saying that i should add compilation commands to the script s.sh but well i understand how it works in make file can i easily make it in this bar script so that it would be compiled only if the executable file doesn't exist yeah i give i will give you a pro tip you can actually call mac but i need to then call it make file no i mean you can call mate in a bash script okay but so i need to first define how i want comp compilation in general right okay but how do you compile it uh like visual way f8 oh okay um i don't use make files yeah so i don't need to compile in terminal because i can copy this whole command but but obviously i don't want to tell this script to recompile so uh yeah so i i would need a separate make file right yes so you need a separate method will restate the basically the flux and then you just go make uh make a gem and it make also look something like this cxx plugs okay so and then i we need both the the script and uh and the make file okay got it yes it saves you from some catastrophic failures but it's a bit more work so it's a tradeoff okay can you tell me how can i see my like visualization of something in the problem statement ctrl f cancu or kenko or control f tools i don't and do you see it okay yeah oh wait so it's an offline tool right there is an offline tool in rust but i think we're not using that and also if you want you can try doing a visualization independently from that website if you want to practice okay so you don't have a single uh like true result uh on the page with a positive what do you mean by true result like the actually submitted result that's right i don't okay so what's your result on uh on this script you have written 1990.67 percentage okay what's yours i don't know your score plus one what if mine is 99.5 this one okay i'm i will move here so your solution only expands right it doesn't shrink it doesn't shrink it i will change my script to run everything in parallel is it okay if we always run for example 10 different threads you i think that it's strange that instead of fixing the running time of your improvements you're fixing the running time of my part plus your improvements so now if i slow my program my parts down then also it will seem that your part got much worse you should re you should start start time just before starting the improvements i think okay once i'm done i will push the combined solutions mine and yours do you remember how in bash i can do something so it wouldn't tell me that stuff is up to date like make things silent i don't want those warnings probably you just redirect make uh make uh stdr to death okay but if there are actually some errors but okay oh then don't make any errors simple paulo check is in the chat oh i know him i think conrad if you want to join the stream then feel free to join if so just write to me in messenger okay actually your avr fails assertion count not equal to zero failed okay this happens because you said that it happens if pro.cpp didn't produce anything so if product cpp had an error count checks if actually anything was printed it means that the standard error outputs were empty okay you actually depend on standard error outputs okay i managed to run stuff in parallel that's a success now let's verify if your part helps at all there is a question in in the stream how does python compare to c plus plus in terms of algorithm speed can you neglect the difference for most cases no you cannot i mean the overhead is like 10 times and sometimes it's even like 100 times so python is like 10 times slower 100 times slower okay then i confirmed that your program works if i start with very small squares and don't do anything smart with them then by default i have score below one percent but once i add your part the score becomes 85 percent that being said if i actually make my part smart so i expand in all four directions then your part doesn't help at all which makes sense you need to improve it okay sounds good i will in a moment push okay can you actually send me like the working pipeline for testing yes i can okay i'm doing that now pushing done now the only thing that you should care about is s dot sh where right now it runs pro but you can change it to like if you want and also i pref i suggest that you right now copy paste my product cpp and do changes on the top of that my current product cpp includes your improvements you can see them there inside but just my prop cpp it matches the standard of i don't know the gener not the generator but what i print to the output and the standard error output oh no you're actually stalling my solution i can sue that's right exactly can you try running sh yes i will i'm actually running no you should see something like 90.7 percent yeah i got 90.8 sounds good oh why i think it should be 90.67 are you already 90.85 but you added some more stuff or what no i didn't do anything is it maybe you pulled your stuff okay is it possible that your generator behaves in a different way on my machine and on your machine not really md5 sum or gen 1 redirect to md5 sum i'm pasting mine in discord this comment yeah it's different interest wait i will make them yeah it's different interesting you only use empty 199 stuff stuff something maybe you have an undefined behavior somewhere and the warnings actually tell you about it no i don't i really don't i mean it's deterministic on my computer what about md5 sum gen dot cpp just in case 85a is the start eight five a yeah okay exactly the same code and it behaves differently you have power you you race for to some power with real values oh right oh so this is the source of non-determinants right and you round it with round instead of l around come on never never use surrounding c plus plus use another round maybe this will fix the issue already so i i will paste the fixed line this is what you should use round still returns a real value another round returns an integer but still i don't know if it will be enough i don't know why you didn't use uh no just integers it didn't do anything for me um how would i use integers actually i don't know what are you trying to do they said that we need to generate a real value or what i mean yeah okay that's what they did what is your n in when you generate with sid one okay what's my my n is 199. it's the same so that wasn't an issue but in a moment i will find another issue okay shuffle shuffle uses that generator or maybe it uses something from stl it uses this generator it's one of the arguments okay i mean a tip is that it's deterministic on my side and is there a music on your side so probably implementation is different what about i pasting in this card the first three lines of of this file do you confirm all three lines or just n okay i don't confirm even the first line i mean only n is okay but then the numbers are almost up yeah so maybe a shuffle has different implementation maybe or somebody in the chat understands this well this is maybe because i have a newer gcc for example maybe i have 11.1 and you have probably nine point something somebody says the generator will generate the same values maybe they mean they will not the distributions may not uh i think the distributions of this generator may not produce the same values at least with different compilers or library versions what's your gcc version or whatever you use 11 11.1 okay i have point three i will update can i type suda apt in update sudo apt upgrade but you won't probably get it because how do how do you update a single thing like gcc is that possible uh yeah sudo apt install gc minus minus upgrade but i'm pretty confident like 90 that he won't get 11.1 by the way it says that it's already the newest version yeah it's the newest version in ubuntu repository but i have newer stuff okay well the we will need to fix that before first day i think because it might be annoying during a competition if we don't if we cannot use the same generator don't you just want to use maybe stl round you mean uh sure i can use it it's weaker than mt19 but that i have to like then i had to re-implement like the float generator for example yes which is easy because you just say rand divided by rand max that will give you a number from zero to one yeah okay do you want me to implement that or or will you just send me the input files i don't know maybe you can re-implement that so just update the gen.cpp push it now maybe i should get back to coding an algorithm because for the past you know half an hour i didn't do anything and i need to order some food [Music] oh no no i get a warning round has limited randomness use c plus plus 11 random library instantly remember warnings are there so you could ignore them be right back can you hear me by the way yes i can okay so i have submitted the generator called downgraded from 11 to stone okay we can check if now we agree about the md5s well before i pull what is the easiest way to ignore my changes to gen.cpp i want to drop all of the changes i did i'll get restored so you check out okay you can i don't know maybe you can hit restore you can check you give check out head minus minus again cp sorry i will write this in the discounts okay but git restore worked perfectly okay okay now this is my md5 sum is the same success great okay somebody on the church wrote today i learned guitar so yeah me as well it's actually an educational stream i mean restart restart seems to be one step more right because i'm restoring the file before my changes only then i wanted to pull i wanted to make sure that there are no collisions okay now we can check the results i have 90.34 including your solution so it was my not very smart but still not very stiff okay makes sense and now we can work independently right so i will improve my part you will improve yours then i'm back to ordering the food sounds good sounds like a independent part indeed you you um a quick question yes how do i disable your part like your you're expanding i can tell you how to make it much more stupid change 8000 to zero yeah exactly that will turn off my part or just before that for loop say if zero or if false did it work getting rid of my part uh yeah it works but it didn't improve the score surprisingly but i was expecting some kind of sabotage but you can also turn off your part and then see that the scores are getting very very bad then i think for me it's time to start thinking about the some smart algorithm i can maybe detect that something is nearby and try expanding in the other direction but i need to visualize a bigger test you answering questions from the chat what am i working at there's this problem where you need to set up rectangles in a big area where for every rectangle you need to you are given information where roughly it should be and what should be its area then the difficulty is basically that sometimes you cannot make a rectangle big enough because other neighboring rectangles will block you i am now thinking about a nice greedy way to do that and eulek is working on an algorithm to keep making some improvements once we have this solution we can look at two nearby rectangles and try to reset them maybe resize so change to rectangle string something local what is the use of arranging this rectangle sir no what is the use of anything i'm creating a program that does it we're just following orders we're not asking questions yes and the blue color it denotes that the rectangle that is still too small i hope we're not assisting some invasion ukraine or something i hope so too if it was possible to drag stuff around i think that a human would solve this optimally or at least much better than what we achieved so far probably because in this drawing i i see what is bad and which rectangles should be moved those small green squares it means it is a point that must be contained in a rectangle and we are also given the area where it's not that we want the rectangles to be as big as possible but we want them to reach this given area i think i will implement some detection of nearby rectangles first to make my part faster so maybe i could repeat it many many times in the random way but also so i could prioritize moving away from neighboring rectangles if a rectangle sees only obstacles in one direction i will prioritize moving in the other direction all right sounds good maybe try processing rectangles from top to bottom and always try to expand upwards first that's i think a good idea but prioritizing vertical over horizontal will give us very long rectangles very tall rectangles and i think that's bad or maybe it depends maybe they push better because i tried to keep them as close to square as possible maybe that's not the best idea is it generally better that they should be squares or very wide or very tall rectangles probably a mix probably square is bad if and very long stripes are also bad what if if if we use very very tall stripes if the areas in the input if they sum up too much smaller than the full drawing then we could perfectly cover everything with just vertical stripes yeah but you can see from the picture from the example randomly generated examples that this shouldn't work why it's actually easy to check you just need to uh make a preference for expansion like deterministic and then you would get long stripes that's right i will i would i don't think it's an easy check but i will try i mean if we keep it just going up and just going down we will get always the the full height of ten thousand just maybe remove the shuffle just remove the shuttle from expand and and move x x to uh [Music] you're describing your part or what yes okay then it would be easier for you to modify your part but i will modify mine to experiment a little bit i understand my part better okay uh well i got vertical stripes but it's very hard to read this drawing and how's the score i'm checking seven percent interesting interesting i guess the issue is that if i keep expanding up and down and only then try going left right and then moving to the left or right even by one increases the score by a lot it creases the area by a lot and it's easy to overshoot the area maybe i should then add shrinking back so yeah something like that hmm i'm i need to do much more work if i want to make a reasonable solution with vertical stripes even just because of rounding if you want to get perfect area equal to something it's very bad start to make it very very very tall because you can only go in multiples of this of this height oh wait i thought that i changed this to twenty thousand i see so my solution is just stupid who would have thought it didn't help that much what if now it's greater than minus one so i'm experimenting a little bit and what i'm getting it doesn't seem to be very consistent but i will look at the drawing for a moment it almost seems like indeed horizontal is better than vertical you like you know the generator x and y coordinates are symmetrical when we create them right they should be okay yeah in my call they are absolutely symmetrical so um would it be much harder to implement as a 2d array it would be much slower i think switch so i would need to iterate this two-dimensional array again and again it's a huge array oh i i don't want to mix horizontal and vertical that's a terrible idea because they will intersect all the time so now either horizontal or vertical you cannot do both what's the percentage you're getting no 82 percent if i try to use vertical stripes actually now i'm looking at horizontal but it's the same thing 82 right yes or 92 82. so it's worse significantly worse than what we had oh i had a mistake uh does the thing influence my score or [Music] not really what your score you shouldn't worry too much about what i'm doing right now i'm just experimenting with those vertical stripes okay so i guess you're just sm smr exactly with vertical stripes i have an average score of 88 percent which is nice somebody is asking wouldn't it be better to first expand than ones that require a bigger area now for me the order of iterating i doesn't matter too much because i have this big outside loop actually many many times i iterate through all the rectangles and each of them i expand only once so the order of them is negligible it can only affect things by one no the food is coming how is it going with your solution with my solution yep well i have made several improvements and they aren't improvements actually you mean they didn't find any case where something can be improved uh i mean i tried making a square initially preferring like some stripes uh now i'm looking to shrink some close rectangles and then expand them in one direction like prefer the same direction order okay fine so i take a random rectangle i shrink closest like 10 rectangles nearby and i try to expand them in the same way i thought that what you should do is just focus on a random rectangle that isn't that doesn't have a proper area yet and then see what blocks it from from each of four directions okay and at least i think maybe even just take a random neighbor so something that touches it so doesn't allow expanding and try to shrink that one by one expand yourself by one and maybe that neighbor can be expanded in some other direction be right back i have some classes in half an hour and the food is coming right now so i think i will be finishing the stream now and okay i think i have time tomorrow so if you want you like we can continue tomorrow some work here but actually still our work right now is independent it can be a synchronous okay sure tomorrow and then the chat to to you the chat the summary is that i was experimenting a little bit about this arrangement of rectangles but at the end i don't have any smart algorithm my solution just this is a very basic solution that i had an hour ago where i for every rectangle expanded in each of four directions and i didn't add anything more i just kept thinking and talking but we learned some things we for sure we for example learned how to use github and how to use a random function that will be the same on our machines thank you everybody for watching thank you you like for joining me thanks bye-bye bye

Channel: Errichto Hard Algorithms

Views: 10,906

Keywords: coding, programming

Id: RLe2rXTjl-w

Length: 167min 39sec (10059 seconds)

Published: Sun Feb 20 2022