Codeforces algorithms problem-solving

What is discussed, and when

1. 1:30:00 – 1:45:00: Ashwin

Notable quotes from "Codeforces algorithms problem-solving"

• And Ashwin one thing that how you can already start in some way being taught by me is this thing.

  about Ashwin · at 1:37:10

Who and what is mentioned in this episode?

People

• Ashwin — Person · 1 mention · first at 1:37:10

Companies & orgs

• Codeforces — Company · 5 mentions

Concepts & topics

• C3 — Concept · 5 mentions

Full transcript with timestamps

4:14 All right. Sounds test. One, two, three. Hey guys, Vivid says, "Pre I said to get in top 10 All three members should have rating 2500. No, I'm not saying that. What I said yesterday is that if you all have that rating, then I said that maybe you have 50% of getting a medal or something like that. I I was trying to specify your own question. What's the role of coach? Actually for most teams the role of coach is to register the team. In many teams ICPC coach doesn't really teach them. That being said very often uh a coach even for a strong team is useful because they will organize a competition make sure that something is happening every week conducts trainings conducts analysis for high enough rating. Coach doesn't do lectures. Maybe they will help you get materials stuff like that.

5:25 And yeah, coach also can have higher rating than 2500. For example, I could still teach a lot of stuff to a team of 2500s. Um, okay. Uh, yesterday I mentioned that my plan is to choose problems a day before. I didn't have time to do it. Yesterday in the evening I was just very tired. didn't have time. Uh so I don't have a choice of problems but I will take a look on discord whether there was some discussion and maybe you guys did choose some good problems but it might be hard for me to find.

6:15 So, anybody here knows? Hi XX no master. Welcome back. Dante lead geek. I should mute your Twitch stream from your site. I can hear you twice. Are you sure? So you're saying there is echo because I think I don't have Twitch open. Maybe it's not good here. I think master maybe you opened it twice.

7:09 Okay, what I'm going to do uh for now is I'm going to open the most recent Division One contest. So maybe this one. I solved the first problem and I already took a look at those two, right? Oh, I did uh Okay, I did try to solve this and mostly got to a solution. I didn't code I opened YouTube as well. Okay, then it's on you. Uh we live on code forces, right? Uh what is the previous code forces? This one here, 2024. Uh I'm just taking a look if the announcement doesn't have a lot of downloads. It doesn't. Uh should we do this?

8:07 I will start from let's say this one. Here's the link and then we'll see in particular if on discord I get a message that actually there was some discussion yesterday in the evening and I actually got good suggestions I will move on to those. One more thing

8:45 link. All right, I think I'm ready to go. You're given n squ cards with values 0 to n square minus one. You are to arrange them in a grid of n byn. The max of a sub grid is defined as the smallest non- negative integer that does not appear in the sub grid. Arrange the card such that the sum of max values is maximized. So among different sub grids we want we want many sub grids to contain a zero. Then we want many sub grids to also additionally contain a one and so on. I think that's the that's the idea. I can already write this down. So we want as many as possible. Maybe we roughly we want to maximize the number of sub grids with zero inside.

9:47 Uh then we want to also maximize the number of sub grids with zero and with both zero and one inside because if both zero and one are inside then the max value will be at least two and so on. So this means that roughly what we want is for zero to be inside as much in the middle as possible. One next to it two and three then next to those in any order because it's only important how it behaves as a sub grid. So like a bounding box of 012 is needed. Like if I do it this way, 012, then everything that contains this sub grid, this 2x2 square will have a max of at least three.

10:38 And if I do it as much in the middle as possible, then I'm good. Uh so it doesn't matter if two and three are in this order or the opposite order. And I think that's it. We will like build from the middle. They are in suggest problems.

11:07 Okay, I see that we got free suggestions for cut versus problems in uh in the Discord. So, I will maybe copy them. This is possibility number one. This is pro possibility number two. And this is possibility number three. And I'm for now pasting everything. If somebody here has time to do it, you can open them and especially if you're high rated and later tell me if some of them are better than others. I will solve at least one of them. Maybe two, maybe three. Should we do a spiral? I I think it makes sense, but it also is not that necessary.

12:02 Two three four, five. How do I want to build next? Is it okay to just do it like that? Four, five, six, seven, eight. I think that's reasonable also. And we start from zero. This is a square. Can be odd or even, right? Yeah.

12:34 If it's 4x4, what we want to do is something like this. And if it's 5 by five, we want to do something like this. Now, one two. So, I'm tempted to do some kind of sorting from the middle. I think we will start here and we will go clockwise.

13:17 I don't know how to do it very easily such a spiral. By the way, this kind of thing should be common. I'm sure that there are problem a lot of problems online about doing something in order of spiral. So this is where stuff like chat GPT would be able to solve the problem quickly once we get it down to this form. So I think if I now plugged this comment into the uh chat some kind of LLM where we say I want you to create a program that prints the cells of the grid in this order or actually prints the grid with such a spiral. I think it should do it nicely.

14:04 I see in Discord some new suggestions. I will take a look later. Hi Pak. Hi Armenia. Okay. Uh well we have test cases. We only read N. uh we want to start from the middle and I think minus one over two is the middle for 4x4 this is one for 5x five this is two so that works okay this is the middle and now I want to what do I want do I need to list down how many steps I do in every direction Like from here, one step to the right, then one, then two, then two, then three. Three. But the end might be different. One, one, two, two. I think that will work. You try to do one step to the right, one step down, and so on. For moving by directions, I'm going to create uh directions where first we move to the right that will move row by zero column by one. Then we move down that will move row by one column by zero left uh 01 and what remains is this.

15:48 Initially the direction is this. And now as long as I don't exit out of the grid, what I do is this. And how many steps we're doing is for first one repeat twice that for this number of steps what you do is row plus equal directions of the current direction first column the same if this is outside of the grid we need to exit that I will do in a moment and then after this direction changes

16:44 and after repeating this twice steps will increase by one. I think we go one, one two two three three four four. I think that's correct. Then we want to save the grid here after doing the step. If this is inside,

17:12 if this is inside then this is good. So grid of row column is next++ some kind of counter pop else break and like stop completely finished is false while finished also this could be done with go to is true This will repeat I don't care at the end for safety. Let's see what is next. And we want to print the grid.

18:12 Um, let's see what happens. Grit a lot of zeros. That's not good. It will that also happen if I add That's right. My dog doesn't really like like the doorbell. uh looking at the chat. I also got scared. Yeah. Getting squad team because he he does problems. Uh that's exactly right. Okay. Uh what was I doing? I wanted to see what happens if the size is greater.

20:11 only zeros. Maybe while not finished. Let's do this. Not while finished. Okay, so we got zero. That's a little bit strange, but roughly we get the spirit. Maybe plus+ next. First increase by one, then save the value. Um, I don't need this. Okay. 0 1 2 3 0 1 2 3 4 5 Okay, fine. Now, next should always be n^2 minus one, I believe. So, that works. I think we can submit. I have no idea if it works. Cute dugger. Scary dugger. finished variable is wrong. Thank you. But and as I always say, it's okay to help me debug the code. That's perfectly fine.

21:36 Don't help me come up with a solution. This was my best contest ever. Congrats, Neon. What place did you get? Okay, now we have a choice between continuing here for example this quarted swapping or doing something from the suggestions that I pasted earlier. I took them from uh from Discord. No hacking numbers is too this statement I do not like. Well maybe it's not a good problem to start with, I believe. What else do we have? Finding or some also interactive. How hard reasonably okay. Okay. Do we want to do finding or sum or do we want quarter swapping? The difficulty might be similar 1,800 1900.

22:51 Any preferences? This one says uh you can ask two queries. You will get the sum of ours and you must do something. So figure out the bits of a number. And then here given a permutation choose an index swap element with two elements later and those two as well lexographically smallest. Okay. So here we modify permutation with some swaps and we want to get lexographically small sequence. What do we prefer the permutation swap or or problem? You can type like or versus uh swap. Any preferences? The difficulty is similar.

24:00 So, I want to move this to Linux. A moment ago, you saw it in in Windows. I see that Armenia first wrote or sum and later uh they said let's swap. Let's do the or task. So the one from discord suggestion this is the link we will also update it for the comment

24:45 I I feel like I recognize a similar problem but this one was recent right from where is it four months ago and I shouldn't see it I recall something similar where there is interactive problem and some binary operations. I changed my mind. Yeah, but also Armenia, let's swap. It sounds a little bit like I'm I'm swapping my decision, flipping my decision. Uh there are two hidden numbers. You can ask queries of form pick value n. The judge will respond with the value of this. Then the judge give you gives you another number.

25:34 Well, we need to understand the nature of this. If I or it seems reasonable to ask for the value of n equal to zero because then what you will be given is simply x + y. uh and everything else seems way more complicated. Now if I if I ask for maybe n equal to all the ones maybe we need to be more flexible but if we ask about all the ones we will get oh something useless just if n has all the ones then the bits inside of x do not matter so that's very stupid I'm guessing that now we will ask for something like this number itself or its um complement and something like that because what does it give me that I know x plus y in terms of binary representations?

26:53 Uh not much. How to come up with math solution after some observation in difficult questions? I mean if you have good observations then that's the hard part. I think to do a good observation is difficult and there is no general recipe and observations will make a solution.

27:27 So for those two particular numbers the sum is maybe let me fill this with zeros. This is zero. This is one. This is one. This is zero because we carry. This is also zero. We carry this is one. We carry zero. We carry uh one. We carry one that is that seems very different from this thing.

28:06 Also we don't need to necessarily construct X and Y. Actually I think we will not reconstruct X and Y. uh like because I think we cannot distinguish whether one is here or it's here. I actually I'm tempted to do something else. What if we don't ask about zero? But we ask about half of the bits like this because then we only get information about those positions and maybe they will not interact with each other too much because if I so this will be my n1 and then second n in my second query will be this. I think that is that has better potential because I don't see how the exact value of x plus y is useful to us versus this if I or it with some value of x of course those positions do not matter at all because in bitwise or they will turn into one anyway. So what I will get is uh few values here and I will get the same also there are zeros in between let's uh denote them as O for a moment those are very like we know that those

29:42 are zeros then we also compute bitwise or with the other value with y instead of x so also every second value is o the zero is for sure zero and some other positions are also are also a one and now if we have zero and one here we will get a one. Oh yeah, we we know exactly everything and those positions do not interact with each other because if we have a one and a one, so both X and Y had a one here, then the sum of them will here create a one zero. Basically, I discover values pairs of consecutive values. If I ask about this value of n spaces are for clarity then this is n or x this is n or y n or x n or y every second position is zero and thanks to that the sum of this plus that it will stay here for sure and it will not carry into the next pair of bits. So with that if I here see one zero I know that this was one this was one. If I see uh zero one then I know one of those was a one one was zero. If I see two zeros

31:08 it means two zeros. Yep. I think that's what we will do. And how big of value and I can choose X and Y are up to this much. Yes, I think we use 30 bits. Every second one will be on. time complexity we we only iterate bits so it's of 32 it's constant doesn't matter too much there are test cases there are test cases but just no matter this constraint if we are able to interact at all read the input output the stuff then it means that it doesn't hurt to do 32 extra operations per test case what if 1 one plus one one that cannot happen because I turned off every second bit. If n what I choose here has every second bit off then it means that in those two terms in this one in this one there are two every second bit is also off and for the others they can be on or off and if I add two numbers of this form like this and this and maybe some of the ones are actually zeros like this. When I add two numbers of this

32:29 form, the pairs of bits interact with each other like those two bits with those two bits, but they will not interact further to the left. In particular, you never have 1 one + 1 one because it's guaranteed that this is a zero. This is a zero. So, um, n1 is is there a good comment for that? I don't think so.

33:10 Um okay. So N2 was this. All right. Now, I What do I do? Print n. Okay. Print n with new line. New line like this flashes the output. It's needed in interactive problems. There's some description here. We read the feedback. I think sum of two numbers up to two at^ 30 will fit in int. Then we print the second value. We read the second result and finally we print the query and we need to print some answer. In between we will figure something out.

34:37 Okay, we need to do something like that for every bit starting from bit zero but add every two. So skip every second position. We want to look at N1. We are interested in N1 and this and N1 and this. Those are two consecutive positions in the binary representation. The first one and the more important bit. I can say that this is a value and then value plus equal twice this. This is how I extracted two consecutive bits. Actually, that's an ugly way to do it to be honest. Maybe better this way. Shift to the right by I bits and bitwise end with three. This is also how you can get two consecutive bits.

35:34 I will not do I want to explain. Okay, brief explanation. If I have a number bitwise shifting to this side, it cuts the last i bits and then bitwise ending whoops bits ending with three. It cuts the last two bits. I mean it leaves only the last two bits. So this is what will remain. Now this I can have a value of 0, one or two. And that will tell me exactly how many bits in numbers x and y uh are on at this position. On at position i is equal to value. Well, it's quite easy code.

36:30 I think it's the same just with N2. And then uh when I read n I need to go through the all the positions and this tells me how among x and y how many bits are on. Now if the given value has this bit on then the or will also have it no matter what. So answer simply increase by twice uh twice 2 to the^ i because no matter what happens we have that else increase it by however many bits I have on at this position with that. Do I need brackets here? Maybe not. Now, I feel like such a binary um binary representation problem. It's actually hard for me to cover during a stream because if you don't know binary operations, well, I think it's extremely hard to follow what I'm doing. But explaining everything would turn into a lecture on binary operations and I don't really want that.

37:51 uh test cases. Let's say there are two. Well, this is so hard to test. It printed something. I'm surprised that we got such a big value but you are not penalized in code forces for wrong answer on the first test. So, we can as well do this.

38:43 Oh, what I actually provided it doesn't make sense, right? Islands limit. Um, do I not flash enough? Oh, after finish queries output this. Okay, I didn't know that. Usually I code the checker for interactive problems. It saves a lot of headache. I do it if it's necessary. I mean because creating a checker a secondary program or something internal here it takes time and here maybe I will do it because I got frank cancer on test one which is not penalized in code forces. Okay, let's easily check what happens if x and y are both zeros.

39:56 So if I'm given this, I will say that the sum is this times two, which is this. If I'm given this now this times two. So the previous value times four is equal to that it seems. And now there comes a query. I want to query what happens if the value is 1 2 3. And what I should get is 2 4 6. So this is incorrect.

40:49 Oh, when I provide the value of n, I know that every second bit is on and those I don't care about. So I want to subtract them. So I think that after reading we subtract twice and one and we subtract twice and two again no penalty in code forces. So it's optimal to first no penalty for wrong answer on first test. So it's for interactive problems almost always optimal to submit and then think that's not the case when you expect wrong verdict on a test different than test one. Let's provide this first. It's still wrong.

41:36 This second and one to three. Still that's not correct. Not correct at all. because I'm using N1 instead of R1 and R2. Those are the so many mistakes. Okay, once more. No, not two. Oh, whatever. Oh, wrong answer on test two. Okay. 246. Uh some kind of overflows. Maybe the sample test is not very strong. Let's first analyze possibility of overflows and then after that I will create some function to actually emulate the checker. I don't think it needs to be second piece of program set on to size 31.

43:02 H I don't think that's necessary. I'm investigating the number of bits in the values of X and Y and they can have up to 30 bits. So I think I don't need 31. It's by the way a reasonable suggestion. It does it's not stupid at all. But I think that's not necessary.

43:34 The answer should not overflow. Good that we have directions from the previous task. Let's let's add some kind of hidden x and y. And now there will be a function query given n print n read feedback and I'm going to subtract this immediately and now instead of reading the feedback I'm going to say r is hidden x or Maybe even better if the local. So if I run this locally, I want to say R is uh N or hidden X plus N or hidden Y plus not else and if this will be performed on the judging environment. This is what will happen locally.

45:08 Okay. Then we read n and I will say this. If the local assert that answer equals query of n. Let's see. And I want one, two, three. Nope. Doesn't work. Why did one two three do something else than before? Oh, because we have hidden X and Y. Does it work if I do zero and zero? No. But 246 is printed. What two values do I see? written.

46:34 Why do I see here two values? Oh, this is uh what I print to the interactor. So this is something I should ignore and this is the actual answer. So this is the answer. Oh, but I shouldn't decrease that for this sake. I mean that this was part of my logic, part of my algorithm, not part of this query function from the statement.

47:28 Okay, it works for such two values. What if I use one and two? works. And what if I use two random garbage values? Doesn't work. Okay. Mhm. Slightly doesn't work. So when there are collisions of same bits maybe then it doesn't work. Uh

48:16 why filling array on twice should second time be this? I iterate every second position. This is even positions. This is odd positions. R1 and R2 which have length 31 in binary. Uh yes, but that's okay. I mean I take two consecutive bits. So I actually reach the 31st bit as well. I think you can debug interactives with preprocessor directives. Uh all this is useful. I mean this trick is just so I wouldn't need to change the code every time before I submit. But this part, this one, line 10, you can do anyway. Just then change it back to reading the input.

49:17 Can the on go above 30 bits? No. on on of i that's count of bits one on i position in values x and y so this value will be zero or one or two and there is nothing on positions be beyond that only positions from 0 to 29 m also I already figured out with this testing locally that the issue is not about the fertive beach pitch the fertive bit. No, no, it's something else.

50:05 Is it true that this is zero or one or two? What about this? I want to print the values that I figured out and I got this which is not correct I believe because this is second bit and the value should be two.

51:07 This is even positions. So N2 should include this guy. How can this happen? R1, R2, R1 is four, R2 is zero, but That's not right. Should we swap R1 and R2 in the loops? Maybe. I think something like that is needed.

52:16 So if those are values of hidden x and hidden y. Oh wait wait wait. When n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n one it gets even positions so it actually investigates odd positions. Okay. So n1 is number that ends with uh ends with this. So what it means is that it knows actually nothing about this position and it knows nothing about this position. So N1 knows about this position. So yes uh indeed we should swap those two.

53:08 Works now. Okay. Uh, printing this stuff is unnecessary and this one as well. Now, if I use two randomish values, it works. Now, can I just submit or did I mess up anything in the process? I think I can submit also. I think I will try to avoid problems like this one because as I said before it's hard to uh while solving the problem to explain it so that most people would understand. I feel like hard DP or graph problem is easier for me to explain as I go. For example, this issue again, I think it would need more time. It's not about interactivity. It's about it being bits.

54:15 Okay, problem solved. Let's move on. Uh what else do we have from suggestions? I want to read the other two problems that were suggest suggested. There was this one folding strip. Let's read. Half queen cover. I don't even know what that is. Let's read this one.

55:01 You can fold the paper. All characters must match. Minimum length of the strip you can form. That seems well known. I don't know how to solve it but I don't I think I I'm not sure if I like it. This problem I I'm not good at string problems. This will not likely require hard string structures like suffix array but already implementing let's say hashing and hashing in reverse I don't like that stuff why don't I use pen and paper I do use it you see this is this is my standard paper with notes uh so from problems from past few case I I do use paper while on the stream when I want to draw something I will use one note so I will draw in this program but so far today I didn't need to coaching techniques you find most effective for preparing students that's too vague of a not not vague question it's not a simple Simple question and not a simple answer.

56:54 Have queen cover. Is that a code forces problem? Maybe I can take a look later. Okay. I don't like this. From curiosity, I will take a look at the editorial at least the top part of it. If you don't want spoilers, you might want to stop watching for a moment. Uh, and what I'm doing is not good for training, for practice. If you want to practice and become the best, it's not that you read the problem and it's annoying. You say, "Ah, I don't want what I'm doing is I'm doing a stream where I also try to care about uh how the stream how useful it is for you and whether I like the problem I'm solving.

57:47 the pattern. Okay, observations. It's not really string data structure problem, but still I don't want it. Only 40 people are watching the stream. I think it's I'm sure it should be more than that if you count Twitch. On Twitch alone, we have 60 people. So, in total, it's 100. I think that's fine. Okay. Uh what about this long statement problem? So hacking numbers and it has multiple versions. We'll see if that's good or not. So this is the statement that I'm considering right now. It has three versions. Easy, medium, hard.

58:40 Let's what are the differences? Send at most seven comments. Send at most four comments. Limit of comments is described in the statement. Okay, let's let's read this thing. This one is easy one. If you say so then I should be able to solve quickly. There is an unknown integer x. You must make it equal to a given integer in the input n. Uh you can send commands to the one of the following. Add X. Sorry. Add Y.

59:51 Okay. So you try to add Y but if it overflows 10 ^ 18 then nothing happens. Multiplication has the same behavior. you say I'm trying to multiply by five. If the result doesn't exceed 10 to 18 then that happens and your the value x becomes that itself multiplied by five otherwise it doesn't change also you get feedback whether it happened or not you can divide and it will happen only if this is divisible. What is S? Sum of digits. Okay. That f of n be the minimum integer such that there is a sequence of nodes. You want to find a sequence that will change all the values from one to billion into the value n.

1:01:14 You want to minimize the number of comments. Okay. So roughly what you want to do is get all the values x from one to a billion into the same value. So you want to kind of collapse it and then you want to change it into n.

1:02:02 The second version is actually different. The second you can send at most four commands. You have to make x equal to n using at most four commands. That's kind of a hint. I I I like looking at this version more because this one seems difficult to start because I have no idea what is optimal. I think we should s start from this version. In this one, seven comments. Just the information about seven and four should help me.

1:02:50 It seems that this is how you quickly collapse a number into something very small. Right? So if you change the number the number initially is at most this also I want to grab this put it here the number is at most 999. There's this this will collapse to at most 81. In particular, it can collapse to 79. If we apply the sum of digits again, it will collapse to at most 16. If we apply it again, it will collapse to seven. No, maybe eight, nine. And then we can just add whatever is needed. And that seems to be four comments.

1:03:49 So should I apply this operation three times? One two three. Oh, you apply this operation three times. But then you do not know you do not know what value you have. How can you know the value? You can

1:04:28 x can become negative. No, it cannot become negative. We can initially add something random. Uh is the problem adaptive? We can cheat a little bit and initially add to the input number or to this mysterious value x. We can add something random and then the sum initial sum will not be that big. I don't know if that matters because the digits will not all be nine. The only way once the number is between one and nine, this thing is useless. What you can do is use those commands to basically binary search what the value is.

1:05:32 It will be 81. Yes, but 81 actually. Okay. After one step, I agree that the new number will be at most 81. But it's not the worst case scenario for me for what the number is next. If it's 81 and I apply the sum of digits again, it's nine and now it's single digit. I'm happy let's say. But if it's 79, which is possible, that will be possible if I start with number that doesn't have only nines, it has a single seven, then I will have a 79 and that's worse for my new sum of digits.

1:06:13 18 9. No, the x value initially is up to 1 billion. I can make it into something bigger, but it's up to 1 billion. Shouldn't 16 be nine? Worst case, uh I mean from six we can have here 16 or we can have nine. What I here I think analyzed is that in three steps you will get a single digit and I don't actually care that it's a seven here. Maybe I got a nine already after the first step. So the the claim is or lema three digit operations um create a singledigit number three times. If you do that digit operation you will get something smaller than 10. Then what you can do is you can do this operation I guess to binary search

1:07:25 or you can do this to divide by like two three multiple times you can divide by few values to always get a one. It seems so far that I don't even know how to solve the easy version. Let's see. I can three times do the digits. Then I can binary search. If I have candidates values from one to nine, then how many times I need to cut in half? How many times do I need to get information zero or one? I need after nine there will be five then there will be three there will be two there will be one possibility so that's four operations something and then I need one more operation to add so that I would actually make the n that's eight operations total

1:08:41 But after just twodigit operations, we already have something that is at most 16. So maybe we can already then binary search. So I think we will do binary search using addition because after that the value is up to 16.

1:09:22 The value is up to 16 and we can try to add such stuff that the value will become exactly 10 ^ 18 and still we need a single that doesn't help just four times anything to binary I think that's how we can solve C1. Is it hard to implement?

1:10:15 Okay. But anyway, even if that works, then we can need to get it down to four comments. I don't see how this is useful other than to basically apply binary search. When your dog barked, I had a gigantic mosquito on my Mac. Do you think there is correlation? Did the mosquito cause my dog to bark? I can force it to one. But how can I do it in so I need I would need to use just three commands to get the value down to one. Oh, we can do one more thing. We can maybe if we have a single digit or maybe we have something small if we add something random.

1:11:42 I I wanted to create such a number that it sum of digits will be even smaller but no that doesn't help. Seen some of your interviews with the NSA. I don't think that was me. I heard something similar before.

1:12:25 How do you do this faster? Why would we divide? If a number is small, we can try to divide by maybe four two 9 three five seven to be sure that we get it down to one. We might get feedback. Oh, that wasn't divisible. But does that help?

1:12:57 It feels like the first two operations they need to be this to get the number to be way smaller. But if I use this even twice then I have so uh so few comments remaining. Why don't I reach a specific number always like one or zero? It's hard to do it in few comments. We can sol powers of two from 16. That's that's a reasonable that's something equivalent to binary search. For a moment, I wanted to add stuff to always achieve 10 to 18. But you're right that we also can achieve zero. It seems well maybe we first add something random just so that the value would be not all nines.

1:14:10 Then it seems that we need a operation of digit. Then we obtain something at most 81. In particular, it can be 79. If we apply now digit again, x can be up to 60 using those operations only. I don't see how we could use two commands to get all the initial values to the same new value.

1:14:56 In particular, what should we do if initially the the value is from 1 to 9? Then this comment is useless. With those we can binary search. But if you have from one to nine then actually you need four commands to binary search. Three is not enough

1:15:31 and division. Well, if you have values from one to nine, then what do you need to do to always obtain a value one? You can divide by seven, divide by five, divide by four, divide by two, divide by three, and divide by three. Again I don't need to divide by eight because those operations they create division by eight. That seems to be a lot of work. If you could somehow said that the values can be from range one two three and let's say 4 6 12. If you know that you have one of those two values then you could just divide by four divide by two divide by three. If you have such three operations then also it could be eight also 24.

1:16:48 All of those values with such three operations they will become a one but that's also so much. Additionally, if the number is divisible by four, then you have very few candidates. If it's not divisible by four, but then you will still need to divide by two and divide by three. Is this solvable? Really? I mean, this I think I already solved that. I could code it, but to make sure. Whoa. Um, if we sub powers of two from 16, the jury will prevent it from going below one. I think it is how to solve the first one. Yeah, that's some version of binary search.

1:17:38 Think very simple. If we have singledigit number, I can add to it. Maybe there is some property that we multiply or divide and then do digit like multiply by nine. If you then do digit, you will get something divisible by nine. Digit sum of nine is divisible by nine. That's true. Multiply by 9. Do the digit and then divide by nine. Uh mole nine. What about mole three? I don't know which is better digit and then divide by three by sorry by nine uh after you do this you get a number that is roughly up to 100 then you do digit sum it needs to be divisible by nine you divide so you have now something below 10 would you like to take a hint no no no no don't if you know a solution don't tell me I I should be able to solve it. At least if you see this difficult,

1:19:31 but already I find this very like interesting. That being said, what now? You can repeat the process. So maybe if now you no why 9 there is some property of numbers divisible by 9 for any x if you multiply it by nine you will have number divisible by 9 and there is a property that number is divisible by nine if and only If its sum of digits is divisible by 9, the number three has also the same property. Then you divide by nine and this will succeed. So you will get a very small number in those three operations. I think that you will get a singledigit number.

1:20:34 Uh actually before that we could achieve the same with three-digit operations. The function s con serves the congress of the number module 9. Yeah. Wait wait wait wait. Should I then just do the digit again? And will I always have a nine?

1:21:21 After this I'm doing the first time digit the value should be up to around 80 something. If I do digit again will it always be nine? I think so. Alternatively, maybe we can multiply by three. I don't know what will happen. Now, it seems that those three operations will always obtain a nine. And then you just want to add the what's the target value n? Well, then add n minus 9. Is that it?

1:22:18 Implementation seems easy. So I think I want to verify that before thinking how that translates into C3 which said you need to do it optimally which will require us to do something special for very small n I'm not sure. Uh do we have test cases? Yes we do.

1:22:52 That was, I would say, very hard to come up with this logic. I could see myself not solving it for more than one hour. Read the integer n. Here we go. Four times. Send a comment. I want to print mole nine. I want to print. Oh, and we always get a feedback except for the operation digits. Oh, no. We all always get a feedback. Uh, by the way, here in this version, I do not care about the feedback, right? Yeah, that's that seems right.

1:24:02 So we query mole nine query digit query digit and finally add with value n minus 9. That's the four operations. Output the line of this format. Okay. We read N. N is one, two, three. You want to move by nine. That succeeded. Success. Success. Success. So to nine I added this. Okay.

1:25:21 Are we going to cover this year's IO? You mean after the I don't know maybe you mean solve problems or commentates. Okay. Uh we can also submit this to C1 if it's the same format. But for the C3 task for some values of N I want to be better. So given n I want to sometimes use fewer commands. In particular if I obtain the value of nine I need to stop. Maybe there are some other values that are achievable this way. And also what happens if I multiply by three? I do digit and digit. I can have three, six or nine. So I need the fourth comment. That's not useful.

1:26:41 I commentary like last year then. I have no idea. I didn't think about it. The solution to C3 is truly amazing. I already think that solution to C2 was amazing is not the word I would use, but very surprising. And again, I could possibly keep solving this problem for another hour and I would be stuck. If you do this, we need to figure out when it's possible to achieve this for given n always in free operations. When the target is nine, then this is not necessary. And when target is something else, maybe another third operation is needed. After those two operations, the number is up to let's say 90.

1:27:54 I think only digit makes sense. You can also multiply by other stuff. You can multiply instead of 9 by 18 27. Anton solved it in under 15 minutes. Oh yeah. In this problem, it's perfectly possible to solve it fast because the solution is simple, but you need to come up with the idea. I'm not saying that everybody will take a lot of time but this there will be big spread or variance of how much time it takes a person to solve it including very strong people. Yeah, it's hard to come up with. I agree. I didn't participate in IMO.

1:28:50 Why did it was nine? Because the sum of digits is divisible by nine if and only if the dig this number was divisible by nine. So after you guarantee it, it very quickly decreases and here it only can be value nine because it needs to be like smaller than 10 after twice applying this operation and it can smaller than 10 value that can be only divisible by nine must be nine. Rust language I have no idea. If those are the two first operations then you will have a number at most roughly 80 and I don't see how there can be any value of n such that one operation is now enough other than this I'm going to see number of exceptions. Okay, this this is harder.

1:30:03 Fewer way fewer people solved it. I agree. starting if you want to decrease the number down to something small then initially increasing it seems strange I wonder if we should divide or it was a red herring so far we don't use the division operation

1:31:26 It feels like only small values of n might be achievable. You know, maybe we should completely switch the strategy. Maybe this is not the optimal start. You got to stress test. Uh I mean stress testing is usually useful when you get wrong answer. Here what we can do is use some program to automatically test a lot of possibilities of sequences of operations. Maybe that would make some sense. It's not short code.

1:32:34 I I still need a dog camera. There should be second camera somewhere there. When did I participate in ICPC and I did not in II? ICPC I did 2018 and 2015 15 Morocco 18 China. Yes. f of n is at most four because we already have a strategy of four. We also we know that f of 9 is three because you can just stop here after those three comments you have the value of nine. The question is whether whether everything else is for well I'm not I'm sure that that's not the case because then the difficulty and number of accepted submissions would be similar.

1:33:37 Jungly took 40 minutes to solve C3. Sure. Reasonable. No, I don't have a full-time job. I don't know how physically strong tourist is right now. So I do not know generally if somebody has some street fighting experience or training they will beat me. So if tourist trains then I think he can beat me. I like the energy of the comment. Okay, fine. Fine. How to choose questions in code forces. Solve recent ones of proper difficulty. Something that is challenging to you but usually solvable. I have part-time job including teaching.

1:34:49 I teach algorithms. Come on. H how do I solve it? I What's the time of the stream? 1 hour 35 minutes. I think we have a decision here that I try to solve it as long as needed, most likely half an hour or I take a hint, solve it and then we move on to another problem.

1:35:23 Okay. I I want the following information from somebody who knows the solution. In the optimal solution for C3, do we always do these two operations first? That's my question. I want yes or no answer. Do we always first multiply by 9 and then do digit?

1:35:50 No. Okay. Okay. And that's enough. I don't want more hints. Okay. So there are a few possibilities. We can we can either multiply by something else that has similar properties or what was the logic of doing digit first then the number is up to 80. You do digit again the number is up to 16.

1:36:48 How can we join your classes? I will soon on code forces announce some summer classes. It will take longer because I'm reading comments and trying. I already counted them that in my half an hour estimation. And Ashwin one thing that how you can already start in some way being taught by by me is this thing. Here is the link. You can book a meeting, a call or a class with me.

1:37:40 Well, we want to do free comments. Everything from one to 1 billion needs to become the same thing. So that one needs to become the same as 1 billion. If we divide by something big, there will still be a big range of values that still are different. We can divide by square root. How how much is that useful? No, no, no. It doesn't divide with floor. It only does the operation if it's divisible. So that's not useful. But if this divided with floor, we would be able to do log of log of x operations. No, I don't teach machine learning and I don't do streams daily.

1:38:54 Okay. So what can be the first comment? If I do this still there will be a big range of different values. If I do this there will be a big range of different values. If I do this big range of different values. By that I mean there x can be very very different. This is the only operation that significantly decreases the range from 1 billion to like 80. It seems that I'm quite sure that digit needs to be one of the first two operations unless we can do those operations in such a way that then the digit operation will create something specific.

1:39:49 If we multiply by 11 that has some properties but not enough. We can multiply by three. What's what happens if we multiply by three? What does it imply? Multiply by by three. If you do digit then the number is up to around 80 digit number is up to nine. But now it can be three or six or nine. If you multiply it by 18 or it's multiplying by 90 that's useless. Multiplying by 99 does it have some properties? It's like 9 11

1:40:51 just to make sure. What I asked is do I always no matter the n I asked do I always first multiply by 9 and then do the digit operation. That was my exact question. The exact question was in this solution to C3, is it okay to always first print those two things?

1:41:28 11 is curious number because 11 has some of the divis but isn't for 11 like every second. So the sum of every second equals the sum of every second. So a moment ago what I investigated is multiply by three and then do digit but then I think we'll obtain three or six or nine. So that doesn't help. Let me check properties of divisibility. No properties of divisibility of sum of digits something like that. Divisibility rule. What do I do when I'm not live streaming or teaching? Live my life. I sometimes do some programming, sometimes freelancing. They participate in competitions.

1:42:32 Three months ago, I changed apartments. So, there was a lot of work with that. Odd versus evil. We can also do something like multiply by three or nine. Do the digit then divide. Yeah. Zero kits so far.

1:43:42 We can also multiply by something that is divisible by 9 but it will also give me some information if I multiply by I don't know this much something of this magnitude then no I think I wanted to do this I don't know about I'm not sure about the number of zeros but if I multiply by that and seven at the end it is divisible by nine al I will get also feedback oh but if I fail then my number is not divisible by nine never mind

1:44:42 topic wise problems you should mix you should sometimes solve problems by topic and sometimes at random it's best to mix those two strategies okay uh new hint question to you chat to those who know the solution is it optimal to always first multip multiply by something and then do the digit operation. So should I optimally uh wait internet is off? No, it works. So should I always do those two first operations where this value here just might differ. So should I always first multiply and then digit? Is that optimal?

1:45:37 Something went wrong with restream. Okay works. People are saying yes. Okay. What candidates do I have for multiplication? I have a three, nine, six, 18. other multiples of nine and other multiples of three. Maybe there are some other values that have properties like you know 11

1:46:41 number theory and discrete math. I think you need to grab a math book for, for example, high school and go through problems. If that's too easy, then something from university. Should I maybe use the feedback? Because so far I didn't care about that. I didn't use the vision. and I didn't use the value that they give me. But if I multiply and I get what if we multiply by something such that only few values fail? Uh does it make sense to multiply by 10 to the power 9 * + 8 this number is divisible by 9 and it's big for most numbers I will succeed I will also get a value that has 18 digits So that's I think bad because then 18 * 9 that's roughly 150. If I now do the digits I will have something that is of magnitude 20. So I don't have a nine.

1:48:21 No. So I cannot multiply by something so big. Something is wrong with restroom. Okay, now it works. There are also hints present in the editorial you may see. Okay, maybe I will and not that link. Oh, link doesn't work. Sorry, I did not update. Sorry. Sorry. Now the link will work. Try again.

1:49:09 You have enough hints to get the solution. You're really doing good. Thank you. Sometimes there is such value of nut. after m nine and digit I have something that is up to 80 something and and it's divis by 9 if I multiply by three and I do digit I will have something that is at most 80 something and it is divisible by three. So this is less information. So it seems strictly less useful. If I multiply by 18 and then do the digit I will have number up to 80 something. It is divisible by nine. What if I multiply? Does 27 have some properties?

1:50:59 Because it's 3 to the^ 3. I think I should join more contests. I also think so about me. Here's a piece of advice. When you train for something, when when you practice competitive programming and you're stuck on a problem, but you feel like you should be able to do it, it's actually a very good strategy to leave it for some time and get back to it. You can leave it for tomorrow. You can solve another problem and get back to it in half an hour. So, if I was just practicing and caring about the efficiency of my practice, this is what I would do here.

1:52:26 That does that also work with cleaning my room? If you are stuck and you don't know what to do next and you cannot come up with an idea, then yes. So summary what what we can do here is or summary of what I know in easier version of this problem we wanted four operations to always change the unknown value of x into the given value and the target value and the operations were to multiply the unknown value by 9 to guarantee that it sum of digits is divisible by 9. Then apply the digit operation which changes a number into its sum of digits. Then apply the digit operation again. Again it decreases the number by a lot and still the number is divisible by nine. And now it can be proven that the new value is now very small and divisible by 9. And the only such candidate is nine. So now it's guaranteed that the current counter the current value x is equal to 9. And the strategy here is if target is equal to 9

1:53:36 then do nothing. So stop else if it's anything else then add n minus 9 to the current value of x and that's it. That's what I have so far. I also was told that sometimes we should multiply by something else and then do the digit depending on the value of target n. That's what I know. It's not optimal to always do those operations first, but it is optimal to first multiply then digit

1:54:53 I'm giving myself five minutes before I want another hint. In five minutes, the stream will be exactly two hours. What else I can multiply by? 2 three four five 6 7 8 9 10 11 12 13 14 15 18. Makes some sense. 20 21 does does something like 25 make sense? Not likely. What about like 25* 9? Wait, no. No, no, that does not decrease the sum of digits. If you have a number divisive by 9, you multiply by 100, it just add zeros at the end. If you multiply additionally by five, well, it can add an extra zero or not, but then extends the number. No, that's I don't think that helps.

1:56:33 You then have 27, 81, 9, and zeros. Uh, are you ending the stream after this? Yes. Oh, no. I I've read a hint. I didn't want it. That was a timer to a hint. Well, I cannot unsee it. 99 has a property. You're saying what is the property of 99? I don't know. What is the property of multiplying by? I I know that it's 9 * 11 17 * 99

1:57:47 it's 18. So is it uh is this always divisible by 18 and then is this always divisible by 27? Is that the property? 9 3 10 15 is Is that it? So is 99 sum of digits of 99 * x is divisible by 18. Is this true? And then second is is this true?

1:58:46 Not true. If you multiply by 11, if you multiply by 11, you have the sum of digits that is even. So this is true right? I mean this first thing is true and second is false. So do we multiply by 99 then the digit then the digit and no no no no no no but after this it's divisible by 18 maybe try multiplying it with 101

2:00:07 by the way another thing that I came up with is multiplying by something like that but I think it doesn't help um if it's divisible by 18 it's not divisible by 99 anymore so it doesn't have many properties but after this the Only possibilities are 18 36 54 72 and that's it. So just just four possibilities and then maybe we can do something in one operation. Oh and then the digit sum will produce a nine.

2:01:05 999 is,000 - one. Okay. So the exact spoiler that Ahmed gave me is that s of something divisible by 9 * 6. Oh, there is no power. So 18 * x. Wait what? No, that doesn't make sense. If d is one then this claims that sum of 9 * x is equal to 9. That's not that's not true. Let's take x equal to this then sum of this is not nine. This is not nine. Okay. Uh, also timer is up. Okay, I give up. I wouldn't solve it during the contest. Clearly something with nines, right? So, oh, so now Ahmed provided the same thing with the power. So, that then will be something like this, right?

2:03:18 I'm reading the editorial. Um, sad ending today. Hints. Hint one. Uh, whoa. You need to do digit and then m 99. Interesting. Oh, for every x up to something. I see. I see. I I I see. Uh so use this number.

2:04:21 So you need to multiply. It's not independent. And then 81 is special case. Okay. To be honest, I don't like this. I don't know how much I'm biased because I couldn't solve it. But this is not an algorithms kind of problem. I don't know. I don't like it. I I I wonder if I should even code it. The code is of course simple, more like a guessing problem. I mean, I see how I were going closer to the solution. I analyzed some stuff like 11 came through my mind. I think without a hint from anybody in the chat. I thought about the value of 11 on my own and I discard it. If I analyze 99 exactly then it would lead to something.

2:05:34 But by the way this hint I think it makes sense but this one it's crazy. Try division 3 not today. H okay. Now philosophical question or maybe practical one. Do I want to now code it just so I would see in problem set that it's solved? It will be easier for me to find it later if needed. Not sure.

2:06:08 I mean, I don't care about statistics or stuff like that, but they want to mark it as green for myself. If I need to find it in the future, will that be better? I don't think so. I don't see a difference. Okay, what I'm going to do now is I'm going to completely forget this property. Like really, I mean to Okay, what about this? I claim the following. If there was a code forces pro problem that would rely on us knowing the property of divisibility by 11, it would be something and the sum of every second digit and you would need to know that if number is divisible by 11, it has that property and then something that would be an ugly problem. I don't like stuff like that. Some obscure math knowledge. Now this wasn't exactly that because I don't think most people who solved it they knew this property. You could go through maybe this sequence and I think you can come up with that but still I do not like it because it's kind

2:07:14 of similar to oh I know this crazy property also during the contest you would be tempted so much to just think oh maybe only for the value nine this is something I don't know uh So for small enough x if you multiply x by 999 then you will get sum of digits 27. That was the claim. I don't like it. And if you guys recommend some new problems for me in the future, I don't want something like this. Please. Still though, by the way, I did badly. I spent more than one hour, I'm sure, on this problem and I didn't get close to the solution. During a contest, I would not solve it.

2:08:10 I now wonder how the standings look. The dog changed the position of lying on the floor. C3. This doesn't count. I want people who solved in order. So you could solve in like 20 minutes. Well, there are red people who skipped this though. I should be high red. Uh, in terms of my rating, I should get place around this one. And some people here got this task and got it reasonably quickly. Well, what can you do? Uh, can you try one more problem? No, I think that's enough for me today. All right. Now, there might be a stream tomorrow in the morning, but no guarantees about that. If tomorrow in the morning it will be like 8:00 a.m.

2:09:27 Polish time maybe 8:30. If so it will be few easy problems and that's it. I think the plan uh for the next weeks is to alternate between So let's talk about the stream plan uh alternate between division two and division one streams and division one division one stream was today. So I solved problems that actually I struggled with. Maybe I don't know if it's a good idea to warm up with something easy like I did today or just immediately jump to something difficult and accept the fact that maybe a single problem I will keep solving for two hours. Not sure about that. For division two pro uh streams actually I'm not happy that yesterday at the end I were I was doing a quite difficult problem. I think that streams should be targeted at some audience and so like if you belong to division two you cannot approach her division one problems then it doesn't make too much sense for me to grab a division two contest and go

2:10:37 through like most of the problems. I think that's it's too big of a jump in diff in difficulty. So what what I did yesterday is I grabbed an educational round and I chose next problem, next problem and so on. But after I got when I got to E instead of doing it, I think I should have switched to another contest and again go from easy problems. So I think this one I want to do easier than yesterday last problem and division one maybe we should skip the division one a difficulty. Not sure. I will think about it. How to suggest problems? Discord.

2:11:18 There should be Twitch comment for that. Discord. For division one, I will accept suggestions in advance. For division two, it doesn't need to be in advance because I can just go from any problems. So maybe during a stream, I will accept suggestions. Not sure. Okay. So, this is stream plan. Sometime in summer I will maybe do also do interview so like lead code streams but not in the next week or two. What I have in mind is that maybe I will do like Sunday lead code classes paid not within the next week. And also during summer I want to do the same thing that I did last year which is weekday uh classes for competitive programming that will be announced on code forces.

2:12:18 Uh but back back to the stream plan so division two will be usually around 1.5 hours. Division one will be two plus hours. In the past when I had time and I did some adcoder problems, I could stream for more than three hours because sometimes you're just stuck on a problem. And this needs to be flexible because division two is more granular. I can I can solve a problem in 10 minutes. So I can stop the stream whenever I want. For division one, it's a bit bad to stop in the middle. So next stream maybe tomorrow morning.

2:12:58 And anyway the next stream will be next weekend right like so after that Saturday or Sunday after that few days I think I can stream in a row so roughly it will be July like maybe five maybe six 7 to 10 I think I have time to do it daily that's roughly the plan will I be doing at coder yes by division one here I don't actually mean exactly code forces it can be outcoder. I don't know what maybe what I should do for something like division one streams is I should try to solve all atcoder grand contest a problems or something like that or maybe possible goal solve all atcoder grand contest a problems or b but they can be already so difficult we'll see I'll think about it uh discord link It was on the Twitch. I I can copy.

2:14:05 I hope that this this still works. Uh no, I don't think code forces is ruined by any one nation. But what you might be seeing is if there are a lot of people from some country, then a lot of people from that country cheat. Okay. Uh that's everything for today. If you have some feedback uh you can other than write right now you can also reach me for example via code forces. So next stream maybe tomorrow morning if not see you this weekend. Thank you everybody.

Questions about this episode

What is discussed in "Codeforces algorithms problem-solving"?

In order: 1:30:00 Ashwin.

What is mentioned in this Errichto Hard Algorithms episode?

3 people, works and ideas are mentioned, including C3, Codeforces, Ashwin. Each one on this page links to its own page with every episode that mentions it.

How long is "Codeforces algorithms problem-solving"?

The episode runs 2 h 15 min; the transcript is about 11,715 words in 125 timestamped sections.

More from Errichto Hard Algorithms

• All analyzed episodes
• People mentioned on Errichto Hard Algorithms
• Topics mentioned on Errichto Hard Algorithms