IOI 2025 day 2 problems

What is discussed, and when

1. 0:00 – 5:00: Pelterator
2. 15:00 – 20:00: Pelterator
3. 25:00 – 30:00: Bolivia, Pelterator
4. 35:00 – 40:00: Pelterator
5. 40:00 – 45:00: Pelterator
6. 45:00 – 48:43: Pelterator, Volleyball

Notable quotes from "IOI 2025 day 2 problems"

• Would make this stream longer, but I then when I wanted to schedule the stream, I noticed that Pelterator already scheduled his and often his streams are 3 hours long. So, it's…

  about Pelterator · at 3:39

• Also, there were finals of volleyball, the Vienn and Poland won. That's nice.

  about Volleyball · at 45:56

Who and what is mentioned in this episode?

People

• Pelterator — Person · 7 mentions · first at 3:44

Companies & orgs

• Codeforces — Company · 5 mentions

Concepts & topics

• Volleyball — Concept · 1 mention · first at 45:56

Places & events

• Bolivia — Place · 1 mention · first at 25:32

Full transcript with timestamps

0:00 Sound test. Let's see if everything works. Okay, that works. Not great. One Romanian guy was doing that well. Why are you surprised? I think Romania uh always Romania was never weak. They weren't that good, but I think it's I eventually I got four gold medals, right? So that's surprising. But the fact that one guy was really in the top, not really a surprise.

2:44 uh last streaming problem E I I will focus on only IOI problems today actually I didn't even read the third task from the first day okay top so top five is unexpected but somebody needs to get to top five it.

3:14 But the fact that he beat Rainboy is sad actually. All right. So, I think here's the plan. Uh we will do uh those four tasks. For each of them, I want to spend 10 minutes on it. just read the problem, share my thoughts, maybe my idea to start and that's it. I would make this stream longer, but I then when I wanted to schedule the stream, I noticed that Pelterator already scheduled his and often his streams are 3 hours long. So, it's not that I was okay waiting for this stream to end because that would be too late for me today.

3:58 So, if I was to stream today at all, it needed to be now and only for a short time and that's fine for me. So, should we start with world map? Uh plus uh one more thing that I will mention today during the stream is that this is the last day you have a discount for my code forces problem solving classes. So if you want here's a link but you need to register today if you want that discount.

4:48 Okay. So, world map from day one. There is an archaeologist who blah blah blah and countries numbered from 1 to n. Uh there is list of m different pairs of adjacent countries. So there are edges We need to create a map satisfying those adjacent edges. We need to draw it as a map like this. Every country needs to exist. If there is a requirement for a pair of uh countries to touch, they need to touch and only those. Okay. So a constructive problem where we need to satisfy some neighborhood and what are the limits? 40 countries and there exists a map that satisfies such conditions because sometimes some requirements cannot be satis satisfied by a planer graph.

6:13 You cannot have a click with 10 elements. Hi Costka. Here we have something like a tree. We minimize the value of K, right? Let R be the maximum value of K / N and you get this. So perfectly if there are 10 countries, you want a map of size 20 by 20. And if you want partial score, it's okay if it's like 50 by 50. Well, this is hard to start, but let's try

7:27 Day one world map. This is the only day one problem I want to try. Hi humble zebra. If I have some requirements like one needs to be next to two, next to three, let's say next to one, next to four and so on. How do I pack this into a map? Actually did they say that there is a tree or just m is up to n minus one. What was the thing here? So here is a path for five points. We need to create a path versus here. It's not necessarily a tree is it? There can be cycles but still the number of edges is very small. If something has a lot of edges then it needs to be long.

8:34 I think it's hard to start from the middle. So I would start from here but then I might block myself from doing something. Maybe it's a good idea to start to say that we are it uh on the infinite grid and we start let's say here if we have neighborhood with two three five and six well depending on how those are neighbors with each other it might be hard to fix that other than creating a path I'm not sure what to do here because the the first subtask, the one worth five points, I would just say 1 2 3 4 5 6 7 8 9 10 11 and so on.

9:34 But here doing this might be incorrect even if I can add more twos, threes, five, sixes because maybe later they will tell me that three is connected to six, five is connected to two and that's impossible here. I would need to swap this neighborhood.

9:54 Country one is adjacent to all other countries. Oh, and here we have a click. I think I would hear try to think about general case uh for some time, but it's very likely that I would then give up and go here. What about the ranking? So 100 points was possible. 86 was also possible. 72 a lot of people got 72 which means uh 72. Oh. Uh that depends on the R.

10:52 I have no idea how I can get 72 in particular. Even if I had access to infinite grid and there was no limit on the size. How do I exactly change this graph into such a planner graph on a grid for very small n? I can experiment exponentially. Interesting. I'm puzzled.

11:41 Unless I misunderstood something in the statement. I don't think so. Good problems. Uh I think I generally has high quality of problems. I don't remember in the past few years anybody complaining that uh some II problems that was a total miss. And usually if I'm stuck on how to start a problem then it's a good one. I generally like problem like this.

12:29 What I wanted to do today was to if I if I'm interested in the solution to to just look at code versus comments to see how people solve it. No, was the optimization problem about what was it? Also creating a grid, some kind of labyrinth. Was that it?

12:58 Hi Crush. Mhm. Yeah. Some kind of grit. one simple path I think seems to be something like a tree on a grid with some properties. I don't remember the problem now but I remember discussing with some students during one of the camps and I recall that this is good example of a problem where uh people should practice it before their II or this you could download the test here right and you submit the output file. Yep. Uh, so I was saying that I wanted to check the code forces comments in this case when I'm stuck, but actually I want to think more about it. So maybe I will leave this for another day and it might be beneficial if I think for half an hour about the problem. I don't want to waste it for myself. So let's move on. Day to first task festival.

14:17 Use tokens to buy coupons. Talking about coupons, I I need to wait. I need to set this up like this. Done. Does this work? I guess it works. Uh, I just need to add the link. So there is this thing I'm starting group classes you can consider joining

15:13 All right. Uh, what would be the point of giving out a problem in the test before an event? I'm missing something. It's after the event. I day 2 happened. And what happened there with input output in the problem we're talking about is that during the contest you were given access to the tests and that was unusual because usually you have the problem statement you submit your program and you get feedback whether it's correct or not on hidden tests versus in some problems you get access to tests and it's still difficult how to solve them. But yeah th this is a problem from a contest that happened yesterday.

16:11 Or was it two days ago? Uh, two days ago, right? What day is it today? Yeah, two days ago. Friday. Did, by the way, was there already II closing ceremony or are we still waiting for that? And the official winners

16:42 My room is closed, but my dog knows how to open doors and he has just entered the room. Uh, yesterday was the closing ceremony. Okay. At the airport. Got it. We have eight tokens and coupons. We need to pay that many tokens to buy coupon and there is type from one to four. Uh so every coupon is a multiplier saying that the remaining tokens get multiplied by that much.

17:34 We should maximize the money at the end. Okay, let's try to figure out what's the optimal order and what are the constraints. Uh is the final answer with model? No, we we return the order not the final value. All right. So is it generally better? This is II day 2 uh task festival. We're not exactly solving problems today. Just checking them out. I I don't want to collide with per pelterator's stream about segmentries. So I will finish when he starts. The dog wanted to leave the room. Let's see if I have a lot of money, let's say, and I'm looking at two couples costing the same cost five and multiplier two, cost five, multiplier 4.

18:44 What should be the order how I do operations? Which one do I go with first? I think that this multiply also works for the money I already spent. So, it's not good to do this first and then that. Then I'm guessing that we should do things in this order. But let's verify. 100 - 5 * 4 - 2 * sorry - 5 * 2 that equals 750 versus 100 - 5 * 2 - 5 * 4 740. So this is better. It's better if we do this first. Okay. First, second. Now, what should be the difference of costs so that it would be equivalent? I'm guessing that this cost should be twice or four times higher, right? Because here the this min -5 gets multiplied by the both anyway this minus 5 we prefer to to multiply it here. So I think that if this is the case if this wait which one should cost 10 if something costs a lot you want to do it at the end.

20:18 So now I think we have a tie where it doesn't matter which one you do first. Uh let's verify 100 - 10 * 4 - 5 * 2 versus 100 - 5 * 2 - 5 * - 10 * 4. No. Oh, because it also the order of those two things change. They are in two different places. Okay, then what should it be? So, we would get equality. 100 minus x times this and y this this. I want those two things to be equal. By the way, this smells a little bit like geometry. Also, there is something called exchange argument or arguments technique. Uh this might be related though. Usually what follows that is DP and here we want to do everything.

21:24 Show the dog on stream. He's already gone. So later if he's back then I will show uh so what do we have here? 400 - 4x - y * 2 = 200 - 2 y - x * 4. 800 - 8 x - 2 y = 800 - 8 y - 4x increase both sides by stuff. 1800 800 is removed. uh 6 y = 4x. Okay, x is this and this is bigger. So if we have like 15 versus 10, 15 versus 10, right? I think so.

22:47 dog. You want to show yourself? Sorry. Lying on the floor over there. Okay, so there is some formula for two multipliers when one of them is better. Now if this was an easy code forces problem I would just sort with comparator that checks for given two elements which one of them should go first and from examples here it's they show that how much money you have right now doesn't matter. That being said we need to be able to afford. So maybe what we need is a set/multi set sorted by this comparator and we always insert elements that we can afford right now. But this will give some other drawbacks. Maybe some elements are available first and then they are not available anymore actually. Do we have sub should we use everything or subset of elements?

24:19 Oh, which we should buy? and up to this for smaller ends. It might be exchange argument plus some kind of DP. There might be geometry involved there. Okay, that's another cool task. Actually, I very much like something like this. Uh once more, I'm tempted not to look at any editorial now and just spend more time on it another day.

25:02 There are subtasks with only multiplayers one and two. Those might be easier to compare. Okay, let's move on. Again, I want to finish before Pelterator starts there. His stream migrations some optimization problem. We have dinosaurs in Bolivia. Interesting. And different sides. Uh, site zero has oldest stuff. The last site has youngest stuff. There was specific order there. Oh, so there they form a tree. We have a tree. Let's say directed. The root is not zero. Actually, not directional. Distance is the path length.

26:11 We want to find pairs of sides. a pair of sides with maximum possible distance. Okay, easy. So, so far it just said you're given a tree. Find diameter of the tree. There can be multiple such pairs. We don't know the tree. For every note, we figure out the parent and we might might send a message. We can send at most 50 messages and always it needs to be an integer like this.

27:03 Okay, as we go, we need to decide about sending parts of a message. And the message needs to uh in total become info about diameter of a tree. At every note, we immediately decide to send a message or not. Is it an interactive problem? Yes, it is. And there is a subtask where the we care about just biggest depth into node zero.

28:05 For the full score, we need to always send a message with an integer from one to four. Only 50 such messages. Okay. How do we possibly send stuff? Only 15 messages. It seems that when we are close to the end of this simulation, then we mostly know what's going on. If I understand this task correctly, this is uh what's the name? Migrations. I also here I actually don't like the statement the dinosaurs migrations it has so much nothing to do with the actual problem. So I'm not a fan of this whoever created the statement.

29:02 Uh it's just doesn't fit at all. But let's see if I we have node zero and then for various nodes we get information about what is a parent maybe. Then for a three we get info that the parent is one. For four we get information that parent is eight and so on. When we get close to the end it seems we should start sending messages. And in this subtask where we care about the longest path from zero just close to the end what we will have is a lot of such connected components. Maybe what happens just before the last message arrives.

30:00 We we know that there are few remaining values and for those values we do not know the edges up. I think that for each connected component with the root here of to zero something can already be connected like this. For each connected component I want to know the deepest note. So which is here value three here value five or two either one of them here value six here value 9 right and I need to send encoded values of those 6 539 and as new things happen so for example now seven will get connected to something it will I will need to merge two trees.

31:00 I need to merge it fast, of course. And now for the full thing rooted at eight. What is now the deepest leaf? Can we do something like small to large here? If this is small, then easily if this is large versus this is small, we need to increase everything here by some offset. Can I avoid stuff like trips here? I wonder what is the simplest data structure that can achieve that that we create a new edge which merges two trees and because of them what becomes way deeper everything here because later something can be connected to this guy and it's I care about the depth

32:04 I think without trips what I can do is maintain links up by one, up by two and so on. So I think I would go with binary jumping or jump pointers and I would lazily update them. Whenever I need to jump from something up and get to know the route, I would follow the links and if I cannot jump by four, then I would look at the jump by two and I would see if from there I know how to jump by two again and from this I would create a bigger jump by four and I would remember it. The total amortiz time complexity is n login because total size of building all the jump pointers up is n login.

32:55 Yeah, I think I will go with that. So then trips are not necessary. and we need to close to the end start sending the messages. We can do it with small values. For example, if n is up to 200,000, then by using if the limit is for example four for a single value, then we've I don't know 10 messages, we can send one value.

33:37 And we want to slowly send information about the deepest for each of those. Sometimes it gets destroyed. Well, I'm sure that I'm far away from the solution still, but I see how to I I see roughly what to do here. Why do you want to avoid trips? Uh I wonder what is the simplest possible data structure that can handle this and I think that lazy binary jumping is still simpler than trips. Also I don't remember what data structures are recommended by the IOI syllabus. So I think very heavy stuff like linkat or play is it allowed for trips? I do not know. Some kind of balanced binary search tree should be allowed, but I don't know if trips specifically are allowed. Binary jumping for me is just simple.

34:41 Uh what is the scoring again? Oh, and there I I only thought here about this subtask. For this one, for every connected component, we need to know its diameter. And when it gets connected to something else, I have two diameter points, two new diameter points. And I believe we can only have longest path between those. Okay. But then maybe binary jumping doesn't work anymore and we need some other data structure. So binary jumping is available here, but maybe not there. some harder data structure. But the idea remains that we close to the end want to start sending messages here. It's just wait eight messages each with value up to four.

35:45 Four to the power eight. Wait, what? No. No. I'm misunderstanding something. Oh, n is very small. N is very small. Okay, I wanted to say that this I have no chance of doing something for those limits because it's smaller than N, but that's not the case. But what do we output? Do we output? I thought that we need to find the diameter. I I find both notes.

36:36 The museum aims to identify a pair of sites with the maximum possible distance and can deterine a pair of sites with maximum distance. Oh yeah. Okay. We return the pair. Well, n equal to 10,000 suggests that maybe we don't care about those data structures and I can just update in linear time. Uh this is my understanding. Hope uh hopefully the time limit isn't very tight. So forget about trips, jump pointers and so on. Just run a new DFS. The task actually is only about encoding and being efficient with sending bits.

37:42 uh but still how do I encode two values? Oh, it's also important that what note I'm that's also information. Uh the optimal solution will not just send when we are at those few last notes but with the information of what is the note I'm using. So if I am at node n minus 5 and I send a value from one to four, let's say three, actually this node can provide more information than just this value. Okay, got it. Uh if somebody here knows the solution and you know that I'm talking some something incred incredibly incorrect, then tell me. But I think that now I'm getting there.

38:33 Why can't I open problems? You should be able to coloring trick. I don't know what you mean exactly but uh but yeah for example I can treat the distance to n as a value that we're sending or maybe for example I will start sending starting at this. So only in this range I send stuff and I can say that my distance to n together with this value from 1 to four in total they will create a value from 1 to n but so far from the end I don't yet know what to And

39:32 well, interesting for sure. Interesting. That was task migrations and the last task because in few minutes Pelterator starts uh obstacles for a llama. Are you asking me whether I need help with an IOI problem and what version of C++? The implementation here doesn't matter much. It's about coming up with an algorithm. Uh okay, last task. Obstacles for llama. Uh we have a grid. Each all cells in each row of the map have the same temperature. All cells in each column have the same humidity. So for every row you're given temperature. For every column you're given some other value.

40:43 If the row value is bigger than column value then there is the cell is empty and you can travel through such cells. You check if there is a path. Oh, nm up to 200,000. I expected that we can iterate the grid. Okay. So if column value is bigger than uh row value let's say or the other way around then this cell is available and we need to check for reachability from one cell to the other.

41:38 I think we will sort for example columns by value. We have some kind of ranges of availability. Then we iterate row. So it's like two pointers. As we iterate the other dimension, we always know what kind of areas in the other dimension are available. So it's like monotonic. I wonder if the it's true that paths will be always very simple. Like if you may, it's a wild guess, but maybe if you're that you're here, you want to get there. Maybe always the path only looks like this.

42:30 Uh calendar, stop spamming. Time out for now. Next time bun. Well, this for for this one without writing down stuff, it's hard to do anything. Okay, from the first look, the problems seem nice. Uh now I think that Pelterator will start the stream. His streams are very nice. So I strongly recommend that in code forces on the right you can find this or I will also give you a link. Uh, here's the link. It get pasted here. There you go. When I'm streaming again within the next few days. just the last uh days were a little bit crazy for me because uh of the II plus I started the group classes. So today for the last day you can use the discount 12% for that uh link is in the description but and it was in the chat plus this is the thing.

44:05 Uh it's so far the cheaper classes I ever organized. So maybe you will be interested. Uh doesn't mean that they are least valuable. I feel now some disappointment that I don't have time today to try more with the IOI problems. But good for the organizers that they created something where there isn't a single problem that after reading I can say such a standard or ugly problem. Yeah, maybe I problem solving. Maybe one of the next few days I will start the stream for like three hours and I will think about some of those problems.

44:51 Not necessarily with coding. I think that coming up with a solution here is way more fun than implementing. at least trying to get like scores of around 70 in most tasks. I'll consider that. Okay. So, do uh check out the classes. Uh thank you everybody for watching. Go watch Pelterator. Uh he he hasn't yet started but I guess any minute now I will remain online uh before he as long as he doesn't start. Uh any more questions then

45:52 I still have a lot of stuff to do today. Also, there were finals of volleyball, the Vienn and Poland won. That's nice. They beat Italy 320 to zero. Impressive performance. It's a pity though that Slovenia did not win against Wait, what did I So, we beat Italy. It's a pity that Slovenia didn't beat Brazil today. I cheered for Slovenia as underdogs.

46:33 So, while we wait here, maybe I will spend a minute more on this So if this is a small value, let's say that row needs to be bigger. We start here. This needs to be bigger. Maybe this is even smaller than I can freely go there. This is even bigger. So I can freely go there. But this is smaller. So I cannot go there. If I need to cross this, I need to go to the left or to the right to something that is smaller than one. So eventually a zero. The first zero that I see though values in between need to be smaller than four. If this is a five, I cannot cross. Though I can go here.

47:33 It needs to be smaller than seven. If this is eight, then doesn't work. But if eight is not here, then I should be able to go there. Then I think the path will not be as simple as I drew first. Oh, he's live. I didn't notice for a few seconds already. Okay, go go go go watch Pelterator. His stream lectures are extremely high quality. Lot of preparation time clearly. So this is the link. If I get your course later in the month, will the earlier courses be available? Yeah, I am. Uh the recordings from the past few weeks will be available though the discount III discount 12% will not be available. What about lead code streams?

48:38 Not in the next week. Maybe afterwards. Okay.

Questions about this episode

What is discussed in "IOI 2025 day 2 problems"?

In order: 0:00 Pelterator; 15:00 Pelterator; 25:00 Bolivia, Pelterator; 35:00 Pelterator; 40:00 Pelterator; 45:00 Pelterator, Volleyball.

What is mentioned in this Errichto Hard Algorithms episode?

4 people, works and ideas are mentioned, including Pelterator, Codeforces, Bolivia, Volleyball. Each one on this page links to its own page with every episode that mentions it.

How long is "IOI 2025 day 2 problems"?

The episode runs 49 min; the transcript is about 4,549 words in 49 timestamped sections.

More from Errichto Hard Algorithms

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