ICPC World Finals: JetBrains Presentation and Livecoding Session Feat. Gennady ‘tourist’ Korotkevich

[Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] i'm pretty sure you know him you all have been waiting him and you know him better than i do uh gennady tourist karate cabbage yeah so this is the team uh another our you will be with them but like now we are living on the chairs we'll we'll leave andrea over here and we'll be back thank you good morning everyone thank you for joining us this early in the morning on behalf of jetbrains i'm happy to welcome you to the icpc worldwide bosco first of all i would like to express great respect and gratitude to the organizers the preparation for the final were made in the unprecedented conditions of the pandemic uncertainty closed borders and still here in the world final and that's a great achievement congratulations great things happens when grain minds come together jetbrains want to seek out great minds all around the world support the initiatives and work together to create great things which make the world a better place that's why job brains is proud to be the global sponsor of the icpc we look forward for the next few days we are going to be here in the finals and we would like you to meet us and talk to us also the kotlin heroes competition which allowed all of you to compete test your skills in kotlin language the next round of it started yesterday and you can practice and we would like all of to take part of it and i would like to give as much time as possible to my colleague sebastian who will give you a jetbrains product overview sebastian everyone uh it's really good to finally be back in a real in-person event you know it's in a way for me it's kind of poetic because the last time i spoke at an in-person event was during the icpc uh north america finals so it's yeah kind of you know all kind of comes together it's a nice conclusion of you know just staying inside my room all the time and you know speaking to a camera in an empty office so it's really really good to be here um and be surrounded by you know some of the greatest programmers and uh competitive programmers out there so before we actually get into my whole talk i just want to kind of address the elephant in the room again i was introduced as sebastian that's my name you can you can see the font size on this and then you can see gennady's name size up here so i think we all know why you're actually here and what you actually want to see so i'm gonna keep my part pretty brief um we're just gonna talk a little bit about what we do with jetbrains the products that we build and then we'll see some really exciting live coding right after that so what's on the menu for today first of all i want to talk just a teensy tiny bit about jetbrains as a company after that i want to give you a little bit of an overview of some of the products that we build some of them you might already use but some of them you know they only came out quite recently so they might not be on your radar yet and you know maybe you can you can take something away with you that's going to be interesting for you um i also want to talk a little bit about uh the educational endeavors we have which will you know help you maybe learn for yourselves but also that's something that you can you know bring to some other people and you know help other people learn programming as well because well you know lifelong learning and the pursuit of excellence does seem like something that's pretty tightly connected to the icpc community we're also going to be talking very briefly about uh kotlin and kotlin heroes which is very atypical for me because i'm a kotlin developer advocate so usually you expect me to stand here for 45 minutes just talking about kotlin but we'll be delegating that to to gennady who's hopefully going to convince that you can do some pretty elegant coding uh with the programming language so i'm not sure if the introduction really is necessary but we at jetbrains have a pretty simple yet complicated mission and that's to make software development well more uh pleasant uh and also just kind of more productive and the course that we've kind of chosen as a company to do this is the power of our tools we've got a portfolio of more than 20 ides for example and those are being built by more than 1 500 people now who are all working tirelessly make sure that people can be more productive both in their day job or when they also learn new technologies it seems that this is all paid off because we have more than 10 million users at this point in over 200 countries which is something that i'm really really excited about so our bread and butter really is the integrated development environments the ides again i'm probably preaching to the choir here because you've probably seen a couple of them but you know we can play a little bit of a guessing game um you know we'll we'll give you a couple of cookies if you can correctly name all the abbreviations that we have on the screen i'm really just trying to drive home the point uh that for all the major technologies there probably is a jetbrains tool that can help you with them i want to highlight a couple of them of course now today that might be particularly relevant to you so we're gonna start out with the classic um at least for this because i know that a lot of you folks are c plus plus programmers and that is c-line because well as luck would have it we are building a powerful and also cross-platform ide uh to write c and c plus plus code now i'm actually not a c plus plus developer so um maybe don't take everything i say for like the you know the the gospel here but i've heard from a lot of people that they really enjoy the typical things that you enjoy from uh intellij based ides that's things like small pleasing and assistance um you know saving time by generating the the boilerplate code that otherwise you would have to type out manually quick fixes and refactorings all these kind of things i'm i'm sure you've you've kind of seen all of this one thing that i usually don't put on the slide but because i know that u-fault are probably a little bit more of a keyboard driven crowd as the last point that is that we have a vim emulation plug-in uh so if you are currently working with vim and you know you're uh very excited to be one of the the quickest people on the keyboard but you don't want to miss out on all the awesome features that we provide in our ides you know maybe give that a shot and see how you can combine these kind of things now of course again i'm not a c5 plus developer so don't take it from me usually i'd say listen to the professionals there's a couple of big folks who've fortunately given us a couple of quotes for us uh to to share with you one of them is matt godbolt who you might know from uh building the compiler explorer who says that well sea lion makes it possible again to concentrate on the interesting parts which is problem solving and again i feel like problem solving is something that you folks at icpc are certainly quite interested in and the other person that i've just kind of put out on the slide here is jason turner who you might also know because he's pretty big in the c plus community who especially mentions the real-time feedback that you get when you use our ides um and kind of mentions that they are excellent time savers and you know who has time to waste in high stress situations but really in a competition like this you're also not really as professional developers who have to work with a code base that's been around for years upon years you kind of have your own demands so maybe actually don't listen to the professionals but listen to maybe the team to your left or maybe the team to your right because we actually collected a couple of statistics from the icpc world finals in 2019 and we found out that well 33 of the competing teams actually used sea lion during the competition so now that you are actually here again in person and you have a chance of chatting with some other people again you know take this opportunity look to your left look to your right exchange with your fellow competitors and see maybe you're you know missing out on some productivity hacks some tips and tricks um i mean where where better to get them than in an event like this now one of the classics that probably i don't even need to mention uh is intellij idea because well a lot of the industry runs on the jpvm uh and we are very excited that our flagship product with over four million users um provides a really nice development experience for people something that sometimes gets omitted a little bit but it's really dear to my heart is that the core of intellij idea is actually it's an open source product right so it's licensed under apache 2.0 you can go on github right now check out the source code if you have enough ram you can probably also build it locally that might be a bit of a challenge but generally you can build your own ides on top of our products as well i'm not going to go too deep into the different kind of features that we have obviously because this talk is kind of more designed as a little bit of a taste maker we're up there on the third floor if you actually want to learn a little bit more about what goes inside the ides and what kind of features could maybe help you so i'm we're more than happy to kind of give you some some tailored demos there one thing that i love though is integration with git and github because when i'm solving problems i don't want to work with branches and do all my cherry picks on the command line that's something i personally don't like i'm very glad intelligent does that for me well since we are also of course talking about education we can't really skip over one of the technologies that has really made a big impact over the last decade or so and that's python we're again very excited to offer an open source ide called pycharm for professional developers which once again i didn't copy paste the same couple of points about you know smart completion uh inlay hints all these kind of things i didn't copy paste those three times in a row so i i just highlighted a couple of uh points which i find particularly interesting in the cost of science stuff like the fact that if you're uh using any of the scientific packages um you can immediately see your data or your notebooks right inside the ide you have a plotting view which allows you to to see the plots of your data directly but yeah mostly that's just more of the same goodness if we haven't convinced you with this kind of yet again stop by talk to us we will be more than excited too now one thing that i think we've also kind of all learned is that collaboration can be a challenge but it's also something that's really important and one of the new products that we've recently introduced is jabrin space so jabra in space is our collaborative platform that encompasses pretty much everything you need for professional software development um i've written up a couple of use cases here so whether it's you as a software developer just wanting to have all kinds of things integrated into one um if you're working in a team if you are managing a classroom and you want to make sure that different teams can work on their own submissions individually or you want to be self-organized that's something you can easily do with space now obviously when someone says an all-in-one solution that can mean many many things um for space we have a pretty clear roadmap of what we already have and what we want to have in the future i've put up a couple of things here these are things like git hosting code review ci cd package management of course we are vendors of id tight integration with our ides as well which makes all of this quite convenient we're more than happy to demonstrate that as well i don't want to dive too deeply into that for time perspectives now of course collaboration as we've probably noticed over the last year or so is something that doesn't just happen on a macro scale you also want this to happen on a micro scale right the experience of peer programming and being multiple people sitting in front of the same monitor and working on the same problems probably sounds a little bit familiar and we recently launched a tool after a long time in in development called code with me which enables exactly this um just as one of the technologies where once again i would personally say seeing as believing but the idea is essentially this imagine just having one ide your intellij your pie charm your sea lion connect from multiple machines to the same instance you can all work together and you can all use the features that you know and love that's everything from the debugger to running your tests to just doing a bunch of pair programming uh with the with the same kind of inspections that you usually see and really we try to make this experience as seamless as possible for people meaning that you literally just send someone a link they'll paste that link into their terminal and they can just get started working with you immediately the kind of key phrase here i would say is it's the same experience that you would have if you work in intellij or sea lion but you get to share it with someone else and they don't have to be in the same room they can be on the other side of the globe it'll still work just fine now obviously there's a bunch of different features here and with static slides vic of having multiple people work on the same thing it just doesn't come across so once again my call to action stop by we'll set up we'll send you an invite link and you'll be able to work on our projects live with us because why not but one thing that i kind of want to highlight especially is the combination um between the fact that we have collaborative editing but also pretty fine-grained permission management which means you can also do things like read-only so if you're teaching give them full access to your computer but you still want them to navigate the code on their own or you want to kind of do like a code walk and show someone around inside your your code base or you're just kind of introducing somebody that's something that you can easily do with code with me but just giving them read access automatically telling their cursor to follow and they'll see everything that you do or they can freely move around in your code base without any kind of issues again one of the big endeavors that i think icpc is pretty closely connected to is the whole idea of lifelong learning and we of course also want to support both educators and students in their journey so i want to briefly talk also about what we do and this is one of my favorite slides um because i don't have to sell you anything because you'll get all this stuff for free anyway so if you're a student or you're an educator you get access to our jetbrains ides completely for free um that's our all products packs so you could name those technologies back on from a couple of slides back those are the technologies that you can use for free um that's as simple as usually putting your email address into a form and then getting a registration code a couple of moments later you can just install those locally on your machine and really start start coding away both at purposes now for universities we actually offer a pretty similar deal we also want to make sure that universities have access to our ides directly for example to staff computer labs so we have a bunch of different uh setups that usually work with whatever configuration universities have again for details just kind of talk to us that's mainly for for programming classes but for example if you're teaching software engineering classes in particular and you're interested in something like jetbrains space we also offer free plans as well as discounted classroom plans that include even more features you can see that on jetbrains.com education or you can talk to us for more of this stuff in case it wasn't really clear yet in this context the collaborative things that we have in code with me for example so just being able to invite a couple of other students your colleagues or people that you're currently teaching into the same session that's all you can do all of that there's no no extra cost or no nothing nothing hidden like that but we also go beyond this because well so far we've really just talked about the things that we have you know that we build for professional developers and the needs of professional developers might be different of the needs for someone who's just starting out or you know who's really just digging into programming for the first time that's why we will have a couple of educational editions of some of our integrated development environments specifically we have intellij idea as an educational version and we also have pie charts as an educational version and we'll see a little bit more about what that kind of contains but what it boils down to is it's a slightly simplified interface for people that really focuses on the features that people use the most but it also includes things that are meaning things like you can solve coding challenges directly inside the ide and we integrate with learning platforms now those two ides are actually for free for everyone even if they're not signed up by the university if they're just studying on their own they can always download these and just get started and for all of our other ides we also also have an educational tools plugin um which enables the same kind of learning features even for the ides where you do need a license so the key thing that we wanted to design with the pie charm and intellij educational editions is an experience where you can have all of your parts that you need to learn something new inside the ide without having to tab out tab back in all these kind of things so the way that it works as you can see right here is you can have the complete problem description for coding challenge right inside the ide we have a new mechanism that uses placeholders so that you can you know fill in the blank kind of problems and you can also submit your challenges immediately from the ide with a single button and get immediate feedback which kind of tightens that circle that cycle a little bit of of getting feedback and kind of iterating on your solutions as well but of course course where does not fall from the heavens we understand that if you are an educator you probably have a pretty clear idea of how you want to teach people you don't want to like take some random course someone created and just say all right you just do this you want to customize things and this is why we actually included all the tools that are required to build to build full courses inside this ides as well you can build those so you can build those for free completely as well and that includes things like rich problem statements which where you can also embed images and videos all these kind of things you can define your sample solutions and then mark placeholders for people to fill in have automated tests so that students get immediate feedback or learners get immediate feedback and the most important thing is that we're not trying to lock you into any kind of ecosystem or you know sneak in some kind of subscription somewhere at the end of the day you can export your uh your courses as a zip file and just send those over to your students on whatever platform you have moodle or you just want to send them a really big email all of that's perfectly possible of course we also offer integrations with learning platforms for example jetbrains marketplace we have a couple of these integrations uh probably for the main part of this crowd the most interesting one uh will be the last one in the list which is code forces um because you can actually write from your ide uh open up any kind of previous code forces contests and start the practice with a single click which means again the whole thing just pops up a window you'll see the whole description of your problems you can write up your solution and submit it directly from the ide without ever having to leave it which might just be like a convenient little experience now we also have some endeavors at jetbrains where we are rolling out our own learning platform and that would start with jetbrains academy so let's talk about that a little bit because we found that teaching people programming is a really interesting task but it's also a really challenging task and we found that for a lot of people it works very well when they have something that they conquered their knowledge to so with uh with jeopardy's academy we essentially built a project-based learning platform you pick out some kind of problem or you pick out essentially some kind of project which is like the guiding thing for what you want to do you say okay i want to build some kind of calculator app a bill splitter or whatever and then you just kind of complete stage after stage task after task and at the end of the day you'll actually end up with a full project and of course this is always hard to pace for people because different people have different kinds of like previous knowledge people sometimes already know things sometimes they're missing like just that one little thing and this is kind of where our knowledge graph comes into play where essentially we have a dependency graph of all the things you need to know to solve your problems or to solve these kind of projects and depending on your previous knowledge we just kind of like different types of tasks [Music] that you like different types of topics that you can usually complete within 15 minutes as a single unit closer to what you need to submit to solve your problems these also include things like code challenges which once again for the tight integration with our ides single press of a button you can solve them inside intellij ideas c line or whatever also things like quizzes now we actually have a bunch of different tracks some of which might also be interesting for you because i'm sure that well maybe if you're learning a new programming language it might be interesting to um you know just do it with a little project i personally know from experience that it can be kind of hard to find that initial motivation or that initial like little problem that you want to solve with a new language so that might be a little bit inspiring but also just if you want to learn a new industry-proof framework if you say you want to know more about how you're becoming a back-end developer android developer all of these things or you want to just see some implementations for certain algorithms in a different programming language jetbrains academy by might be an interesting place for you to stop by something that we're of course also very excited about uh because we are kotlin people at heart at least i am is the fact that we offer two new uh kotlin tracks and that's the kotlin basics track and the calendar track now the basics track is available for everyone for free um and it kind of gives you a first taste of the language and takes you all the way to the point where you can already be productive and then with the cotton developer track uh where um if you have a subscription for that one you can also learn some advanced topics of the language and become a real professional karan developer in probably no time so uh if you are interested especially in that second track we have a qr code here i was told to make a gesture so that people can know what to scan um that will give you access for a little bit longer um you if you keep self learning we actually kind of continuously extend your your free trials for a while so you might not have to end up paying at all if you just keep at we're just trying to motivate you there in that regard a little bit um if you currently don't want to scan code because it's just kind of awkward sitting like somewhere back there and the phone camera doesn't work and it's all smudgy just stop by our booth again and we're more than happy to share that with you as well now super briefly before we move on because i don't want it much more of this time we're going to talk a little bit about kotlin a topic that is very dear to my heart as i've said beforehand to just kind of you know get everyone on the same page colin is a programming language that we at jetbrains kind of conceived for the first time out of our own need to be more productive on the jvm it's something that we started back in 2011 um it's a language that's completely interoperable with java and when i say that i mean that it's to the point where you know you can literally instantiate a cal an object in java the same way you would instantiate a java object and the other way around it's also of course an open source project for us but the big goal that we have with this is to make programmers a little bit happier what we're really glad about is that the uh educational space has also kind of picked up on this life as well with over 190 different universities all over the globe already teaching kotlin we're also very excited that uh during this symposium uh we're also going to be talking a little bit more um about cotton in education and for universities because we think that can uh it can bring a lot of good to people and it might make people enjoy programming just a little bit more some of these universities you know if we want to be braggy about it 26 of the top 100 universities and the times higher education uh rankings already include in their course and of course you know if you are in a position to move a course to collin once again uh or that's something that's interesting to you you know where to find us we're right up there uh i think we're the only booth that has a really nice glowing logo which i think very much that sets us apart if you actually are more of a hands-on type learner and you want to compete with a couple of other people who also write kotlin code then we of course invite you to our code forces contest called kotlin heroes it has already started and we're actually going to see a bunch of the practice round content in just a little bit but on october 7th we're going to have the real challenge there's going to be a couple of prizes for you to win as well so just as a small little incentive well that's all i have for you today i know this talk was kind of all over the place that's kind of in the nature of an overview talk if any of those things were of particular interest to you once again come talk to us we're here all week um let me let me tell you i can guarantee you we're more than happy to spend even extended periods of times telling you what's going on so yeah stop by uh make sure to have your free licenses whether that's for yourself um for your classroom or for your university if you want to learn new technologies make sure that you pick up your access codes for jetbrains academy and if you're looking forward or if you're looking to you know join a company where people are really really about making other people more productive stop by take a look at our internships take a look at our open positions we would be more than excited to have you all right with that we're going to be moving on to uh gennady's part of the talk so i'm going to be stepping off and yeah i hope you still have a wonderful event take care [Music] so [Music] one two three hello everyone and thanks to to jetbrains for inviting me um i must say that i did not mean to steal the show and i was not in charge of the font sizes we have this kotlin heroes contest which you have heard of as of now at least and it's held on code forces that's the announcement and the rectus round that is running right now so it's the eighth edition and i took part in most of the previous ones and i'd say it's a pretty fun and cool way to print language and get out of your comfort zone so to say so let's try to solve the practice round and just let's go um okay all right so this is the intellij idea id and i'm using the edu tools plugin to have the problem statements right here so the first problem is just a plus b um how do it start so we need the main and then we need to read input from standard input so the default function is redline but to read integer we need like we can define another function which is an integer which is just convenient to have it will be just redline to end and then we can have a function to read multiple integers on one line and we need to map all of them to in this one so that's how you can do that and it's just convenient to have these functions in your template in general and you can have functions for different types for example doubles but we will probably not need them and now we don't have to just answer one test case we have multiple test cases so to solve multiple test cases we can just do something as simple as repeat reading times now we need to read two integers we just read a list of integers and destructure it into two values because we know we'll have two values and we just print the sum uh all right um in this plugin we have the run local tests button which will just test the examples for us um yeah we can see the local test passed so we can just copy our code and submit it so we just paste it here we submit and in some time it will be tested maybe we should not wait i mean in queue it's it's okay cues happen uh we can just go to the second problem in the meantime so in the second problem yeah this one is a bit longish but yeah let's resize and take a look so we have some kind of football match we have n yellow cards shown to the participants in total we have a1 players on one team and i want a two players on the second team and the rules of sending players off are a bit different the players of the first team have to receive one yellow cards to be sent off and the second team has to get okay two yellow cards to get sent off like one player and we want to know the minimum and the maximum number of players could have been sent off maybe it has tested ryan on test five we are going good um yeah okay so this is kind of your mess like maybe arithmetic's textbook problem but also requires some case analysis so first we can just read all the variables we have the sizes of the teams we have the numbers of cards and we have the number of cards in total okay accepted we have solved the third problem um yeah so what is the minimum number of players that each player on the first team can get k1 minus one yellow cards without getting sent off right so that number is number of yellow cards we can show to all the players on the first team without getting anyone sent off and that's what we want to do because we want the minimum number of players and the same goes for the second team uh yep so that's the number of cards we can show without getting anyone sent off and every subsequent yellow card will send someone off so the answer let's say min will be n minus this value uh all right almost there oops oh sorry about that that will be the minimum number however we don't want to get negative number of players sent off so we should get the maximum of zero and this number and that will be the minimum number what about the maximum number we basically want the players to be sent off as soon as possible so first we can make the first team the team which needs less yellow cards so if that's not the case we can just swap and we can swap this way there is no swap functions because we cannot um pass variables is references but this is pretty short anyway and then if n is not greater than ny a1 times k1 the number the answer will be just n divided by k one um round down and otherwise we will have a one players and then we divide that by k2 and that will be the maximum number okay i should not do that i should just have a variable max let's define this int we will assign that to max we'll send that to max and we'll print both values we can do it like this okay let's see if we can pass the local tests okay we can so let's submit okay that's kind of the process this problem was just mess let's go on hopefully it will pass soon yeah the third problem we have n cans in a row and the i scan has durability ai and it means that if we have already knocked x can down cans down we will need a i times x plus one shots to knock this one down all right so basically it just means that we get tired so for the first can we need one shot and then for each subsequent can the later the like in time shots we will need all right i should maybe i should not switch too often we just have to shoot the cans in decreasing order of a i and we have to print the number of shots we need and also the sequence in which we should knock down the cans all right so uh we are half n we have a which will be a list of integers how do we find the order of cans we can do it like this so first we take a since we need indices of the elements we can call the function with index which transforms all elements into indexed values pairs of index and value now we can sort them by understanding at least indeed by values yeah and now we have the order okay keep going um yeah and also let's find the answer this will be easier to do just with a for loop um yeah so for can number i uh we will need uh b i value times i plus one shots right should be right okay and now we print result and we print indices so we can use joint string of space and then we also need to only take the indices and also we need to add one because we have zero based index in here and we need one based indexing in the output so we just um it index plus one is how jointly so let's test the solution all right so we have incorrect test2 failed and that happens because the order of indices can be arbitrary if there are multiple orders so for example in the second test case we have four equal numbers and we can just output any sequence any permutation here since the plugin doesn't know like it can it cannot check the answer there is no checker provided by the by code forces we can either like run all the test cases manually and take a look ourselves or we can just submit right because we just trust our instincts and mean time we have second problem solved uh yeah i suppose we will not wait for the third one thank you yeah let's proceed to the first problem in the meantime okay we denote the function f of x which is okay i suppose x is a positive integer we add 1 to x and then we remove trailing zeros in the number yeah so for example f of 599 is 6 and so on and we say that some number y is reachable from x if we can apply function f to x multiple times so that we get y okay and then we are given a number and we need to count how many different numbers are reachable from that number okay yeah i guess the main idea of this problem is that the number of reachable numbers is actually not that high just because we will moving the trailing zero is divide the number by 10 and then after at most ten steps we will divide number by ten so we will quickly get to a one digit number or so so let's just simulate the process so we have n it should be a variable here let's also have some set of added numbers it will be hash set of integers and now while our set doesn't contain n because if we make a loop if we run into this number we have already seen we don't need to continue because we will obviously just see all the numbers that we have already seen so we just add n and now we have to apply f of n you can just do it in place so we just add one and now we need to remove trailing zeros so while n is divisible by ten let's just divide it by ten uh and that's it yeah then we try to add this number to the set again okay and in the end we just print the size of uh of the set right yeah looks good to me okay third problem accepted even though we did not test it on the samples right uh don't try to repeat that at home okay we have tests passed for the first problem let's submit uh yeah actually we can also instead of checking contains and adding we can just add it here and we'll the method add will just return a boolean value whether the insertion was successful to work actually let's just try it on the local tests okay we don't need to submit again um yep let's go to the next problem we are given a string of characters zeros and ones and we want all ones in the string to form a continuous subsequent sub segment so for example yeah this is the example of good strings and these are the examples of bad strings all right and we may erase some zeros from the string and we want to erase the smallest number of zeros possible all right uh so we are not allowed to erase any once we can only erase zeros so all the ones are kept in the string and we want all the ones to be sub like to form a sub segment so basically we can find the first one in the string we can find the last one in the string and you have to remove all the zeros in between right between them uh yeah let's just do that so in this problem we have multiple test cases again so we just repeat reading again let's say we read the string it will be redline double band because the value can be now but we know it will not be now uh okay let's find the index of the first zero uh we can use index off of a char of one for example right yep there is a special case if there are no ones in the strings in string at all yeah for example in this example we have a string of just one zero then we don't remove anything and in this case index off will return negative one so that happens we just print zero and otherwise now we need to find the position of the last one we can just use last index of one again so we now have two positions and we need to count zeroes between positions i and j basically you can just take a substring yeah we can call substring is different in different ways we can call it from i to j for example uh i guess we can also make it i until j or we can do it i double dot j which are a bit which is a bit different but in this case position j has is one anyway so it doesn't matter you can keep it like this and you want zeros so that's how we can do that um and we need just to print it number uh whatever answer this would be some variable and we just print it okay let's try [Music] so yeah obviously like you can also just use some for loops you can use a for loop to find the first one to last one you can use maybe the same for loop or a different for loop to find count zeros but as you can see you can also just use some built-in functions and it will be fairly concise right uh all right accept it as well yes by the way all right let's go to the next problem uh yeah it's also a bit lengthy so let's resize we have two matrices of the same size each element of a is zero or one or in each element of b is zero and we perform some operations with b we choose any sub-matrix of b which is size 2 2 times 2 and replace all the elements with 1. this is the formal definition and we want to make b equal to a and the question is if it's possible to make them equal and then come up with a sequence of operations that achieves that if it's possible all right so this is kind of like the stamps i know problem like we have a stamp of size 2 times 2 and we can stamp with somewhere on matrix b and we want to make it equal to a and since we don't need to minimize number of operations we can just make an operation in every position where we can do that so we just take any two times two sub matrix in a if it contains all ones we can just make an operation like here in position one one position one two and position two two and after that we just compare a and b and if they are equal then we that we have a shift our goal otherwise we print negative 1 in this case all right let's implement that so we have the sizes of the matrix um uh yeah it should be read ins but we have two ins and now we have the matrix itself uh let's make it a list of size n and we can just initialize each element of the list with a list of integers thread from input so this is pretty short we can just read the matrix this way and now let's also create b it will be uh yeah it will be a list of lists again but we will need to change it so we can define mutable list of size n size m zero all right and we will also need a sequence of operations um well for example we can define the class basically you can also use player which is available in kotlin but you can just use i know step which will have i and j and we will have a result which will be [Music] some mutable list of steps okay so and now let's just check all uh possible two times two sub matrixes so for example we can go yeah from zero to n minus two right uh from zero to m minus two now we have to check if this sub matrix is good what does it mean if all the elements are once yeah in this case we add a new step at i j and we also change the corresponding values to in b yeah you can probably make a for loop here but four lines so it's not really needed um okay so if a is not equal to b in the end we can just compare with not equal we just print negative one otherwise we print the size of the result and we print the operations so we just join to string them we don't have to we can just iterate over them but you can also join the string with vexilar chinese delimiter and we also again need to transform each player into a string so it will be i again plus one because we need one in one indexing and plus one here okay let's try all right passes the local tests let's submit and let's proceed to the next problem yeah and this will be probably the last problem because of our limited time but let's take a look at it anyway um this problem is interactive uh what it means i guess most of you know obviously but anyway in just given some input and you bring some output and in interactive problems you do that multiple times you read some inputs you bring some outputs then again you read some more inputs and so on so you just interact with the testing system yeah we have an integer x picked by the judges in these ranges and you have to guess that number and you can make at most two queries okay and each query should consist of 100 integers and in response to our query the judge will pick one of these 100 integers and tell us the value of exclusive or of our one of our 100 integers and the secret integer and we also need all the 200 integers to be distinct and we need to guess the number right okay let's take a look at f okay f accepted good um so um yeah our integer is not greater than 2 to 14 minus 1 so it means that it consists of 14 bits right how can we extract some information from the decision system like the actual problem is that we have to give 100 integers and we will be given the xor with some one of them we will not be able to tell with which one so it's hard to just find the result value because like the secret value i mean because we have at least 100 candidates right but let's see for example if our number will be our number is small like for example one if we provide an integer one uh x x or one will be kind of close to x right so let's see for example if we just provide integers from 1 to 100 then the result will have it will be x xor 1 or xx or 2 or xor 100 or anything in the middle but the highest seven bits of the result we will be given will match the seven bits from x and this way we can extract the highest seven bits from x and we have two queries and we have extracted half of the bits so now let's just do the same but with the lower bits if we provide integers uh 1 to 100 multiplied by 128 which is 2 to the power of 7 we will be able to get the lowest 7 bits of the result and we will form the secret value from these two queries so we'll need exactly two queries uh yeah let's implement this um yeah so the interaction format we have to print a question mark for followed by exactly 100 integers and not three all right so we just print question mark and we have to follow it with okay in the first query we want to print integers from 1 to 100 let's just have a range from 1 to 100 and yeah just join it to string i suppose and print ln automatically flashes the output so we don't need to make any extra flash statements now we can read the first integer given to us by the interactor okay now we want to make the second query we need integers from 1 to 100 but multiplied by like shifted by 7 bits so we can again have oh a bit too much this hints are of course can be turned off if you get two nights or if you have a larger screen you will probably not have a problem but here we have big font for you to see so we can just map all the integers to shift them by seven basically this is just how you do it you just map all the integers into the same value shifted by seven and again we just joined them to string and now we read the second value we are given and we can just we just need to take the highest seven bits of a and the lowest seven bits of b uh so how do we take the highest seven bits of a for example we can just shift a to the right by seven and then to the left by seven so you just shift and then get back and you erase the lowest seven bits and for the lowest seven bits of b we just end it with one to seven minus one right and we print x uh not just x we print exclamation mark x all right we can run local tests but it would not make much sense because we are cannot know what input will be given by the system you get incorrect you can compare outputs but that's not really useful in this case uh in any case like again it's a bit difficult test but it's just the uh property of interactive problems in general uh but we can probably just oh yeah it's already running we can just type some integers here and see that it is the protocol is what we expect and you know just submit all right um yeah that was it i guess we will not take there are two more problems but they are probably harder than this ones and that's all i have for today so once again thanks all for your attention and i hope to see you in kotlin heroes 8. thank you jenna and um one more technical announcement timirlan aman gildin or those who know tim mirlan please tell him to come to the house desk at front entrance this is extremely important once again tim mirlan thank you very much yeah that's it for now and um a very warm welcome to our next global partner global sponsor huawei and let's imagine a world where you have just one championship for solving the all the problems connected uh with the main tasks of humanity obviously there can be no competition there will be just one global team uh containing the programmers from all over the world and of course it will be open sourced and how to save the world with open source vladimir rubinov cto at holloway russia please a very warm welcome from you thank you yes and i will find the clicker just give me a second ah it is good okay colleagues i'm happy to see the brightest minds of the software world and today we really need to talk about things that matter globally i might assume that you might have two thoughts when looking at the title of this talk that it is something that you already know yes a lot of you really know in general what open source is and you might think that it's not too important for you now but believe me this topic will be important for you with some time because it's inevitable that open source will be the major model of software development in the whole world and let's talk about it yes we start with really simple things and this slide you really should know uh before but interesting thing the open source you might face some open source with specific licenses but did you know that actually there are more than 100 different open source licenses in the world and there is actually formal definition of what open source is it is defined uh by uh open source initiative it includes ten criteria but most important are the first three underlined here about that it should be the core

Channel: Kotlin by JetBrains

Views: 2,232

Rating: 4.8947368 out of 5

Keywords: JetBrains, kotlin, kotlin heroes, icpc world finals, gennady korotkevich, tourist, competitive programming, CLion, IntelliJ IDEA, PyCharm, JetBrain Academy, Space

Id: MQV0lAM2I5A

Length: 66min 50sec (4010 seconds)

Published: Sat Oct 02 2021