The first day of IATI 2021 has finished about half an hour ago. Please feel free to discuss the competition here!
Problems
- Day 1: https://drive.google.com/drive/folders/181qblYWJlQjkAUQaMtzxDwJnvh7zUeBO?usp=sharing
- Day 2: https://drive.google.com/drive/folders/18Sd24hOt6VmhdQgaUuak0804lj3bTnM8?usp=sharing
Results
- Seniors: https://cdn.iati-shu.org/files/standing_A12.pdf
- Juniors: https://cdn.iati-shu.org/files/standing_B12.pdf
Editorials
- A11-Heaps (unofficial)
- A12-Miners
- A13-News
- A21-Hint (unofficial)
- A22-Delivery (unofficial)
- A23-Rabbit (unofficial)
- B11-Pretty
- B12-Wall
- B13-Sum-prod
- B21-Monopoly
- B22-Cutting
- B23-Sss
^ Please feel free to provide links when they are available
Apologies for not being able to properly distinguish $$$O(n \log n)$$$ from $$$O(n \log^2 n)$$$ on miners — I'm bad at problem setting :,)
Does the author's $$$O(n \log n)$$$ use binomial heap?
Yes, binomial heaps are one option. There were two intended solutions — the first one just used randomised meldable heaps, as their constant is very low, while the second one builds a max segment tree on the dfs order, so now you don't need to do small to large merging.
Is it even possible to distinguish them?
When testing on polygon you could actually see the difference between the $$$log^2$$$ with priority queue, which is a quite low constant, and the $$$\log$$$ with segment tree, but unfortunately this wasn't the case on our system. So if we increased the constraint (and made it interactive so that the input doesn't matter), we would have been able to distinguish them.
How many participants are official in seniors?
Where can we see Day 1 problemsets ?
https://drive.google.com/drive/folders/181qblYWJlQjkAUQaMtzxDwJnvh7zUeBO?usp=sharing
A is for Senior, B is for Junior
Thank you
So what is the full solution for A in junior?
How to solve problem Heaps?
I wonder aswell how to solve heaps
I wonder as well how to solve heaps
Basically, we want to use the Sprague-Grundy theory.
So we've got a state that looks like $$$(b, s)$$$, and we've got edges from $$$(b, s)$$$ to $$$(b, s - 1), \dots, (b, 0)$$$ (as in classical Nim) as well as to $$$(b - 1, k), (b - 1, k + 1), \dots$$$, and to $$$(b - 2, 2k), \dots$$$, and so on. We're going to assign nimbers to every state, as usual.
The problem is that sometimes we've got edges to states with all nimbers from $$$0$$$ to infinity, so, strictly speaking, we can't compute $$$\mathrm{mex}$$$ to get the nimber of the current state.
That's where ordinals come in. We can now say that $$$\mathrm{mex}(0, 1, \dots) = \omega$$$. Similarly, $$$\mathrm{mex}(0, 1, \dots, \omega) = \omega + 1$$$, and $$$\mathrm{mex}(0, 1, \dots, \omega, \omega + 1) = \omega + 2$$$, and $$$\mathrm{mex}(0, 1, \dots, \omega, \omega + 1, \dots) = 2 \omega$$$, et cetera. Then there's also $$$\mathrm{mex}(0, 1, \dots, \omega, \omega + 1, \dots, 2 \omega, 2 \omega + 1, \dots, \dots) = \omega^2$$$, and so on.
Exempli gratia for $$$k = 0$$$:
It's a bit more complicated for $$$k > 0$$$ but the underlying idea is the same, and, more importantly, the nimbers never reach $$$\omega^2$$$, so every nimber is kind of a linear polynomial of $$$\omega$$$, i.e. $$$a \omega + b$$$. You can simply store two numbers for each state.
Computing $$$\mathrm{mex}$$$ is now relatively simple and intuitive; the xor-sum of two polynomials of $$$\omega$$$ is actually a coefficient-wise xor-sum (the proof is left as an exercise to the reader).
Now, notice that the nimber of $$$(b, s)$$$ equals the nimber of $$$(b, s - 1)$$$ plus 1 if $$$s > kb + 1$$$ (or something along these lines, maybe $$$\pm 1$$$ somewhere; I don't remember), so you can simply store the nimbers in a 2D table of size $$$\mathcal{O}(kb^2)$$$.
The final step is to notice that the nimbers are kind of discrete with respect to rapid changes of $$$b$$$, so the nimber of $$$(b, s)$$$ equals the nimber of $$$(b, s - s \mod k)$$$ plus $$$s \mod k$$$. That's how you reduce the complexity to $$$\mathcal{O}(b^2)$$$.
Reference materials:
[1] https://codeforces.com/blog/entry/85984
It was quite difficult for me to calculate the mex fast. Which way did you use for it?
Let us iterate through $$$(b, s)$$$ in increasing order and calculate the nimbers one by one.
For a fixed $$$b$$$, we compute the nimber of $$$(b, 0)$$$ first. It equals the $$$\mathrm{mex}$$$ of the nimbers of $$$(b-1, k), (b-1, k+1), \dots, (b-2, 2k), \dots, \dots$$$.
It's easier to demonstrate this graphically (I'm assuming $$$k = 1$$$ for simplicity):
The red cell is the nimber we're computing now, the blue cells are the cells we're $$$\mathrm{mex}$$$'ing together.
Now notice how this blue set changes when we increment $$$b$$$ by one:
Notice that $$$\mathcal{O}(b)$$$ numbers were added to or removed from the $$$\mathrm{mex}$$$'ed set. So, we can simply maintain the set of the $$$\mathrm{mex}$$$'ed numbers and update it when $$$b$$$ is incremented.
That's how $$$(b, 0)$$$ is computed; for $$$s > 0$$$, it's even simplier. When you move to $$$(b, s)$$$ where $$$s > 0$$$, you just add the nimber of $$$(b, s - 1)$$$ to the $$$\mathrm{mex}$$$-ed set and get the correct nimber automatically.
Ormlis has just explained an easier solution to me; sharing it here as per agreement.
So let's look at our familiar table. The only modification is that I added green and magenta cells, and that I actually computed nimbers (for $$$k = 1$$$).
For $$$b = 5$$$, the magenta cells are the computed as follows: the nimber of $$$(b, 0)$$$ is the $$$\mathrm{mex}$$$ of the blue cells; the nimber of $$$(b, 1)$$$ is the $$$\mathrm{mex}$$$ of the blue cells and the number of $$$(b, 0)$$$, and so on.
What Ormlis noticed is that, in fact, the union of green and blue cells is $$$\left\lbrace x \omega + y \mid x < b, y \in \mathbb{N}_0 \right\rbrace$$$, so the magenta row first lists the green nimbers, and when those are exhausted, proceeds with the next yet unused ordinal.
This can be proved by induction easily, because, the union of blue and magenta cells of $$$b$$$ equals the union of green and blue cells of $$$b + 1$$$.
This yields a very simple way to fill the $$$b$$$-th row: you take the green nimbers, sort them, put them starting with $$$(b, 0)$$$, and when those are exhausted, let $$$\mathrm{nimber}(b, s) = b \omega + (s - b)$$$.
Giga chad task
I was happy that I got 3rd subtask in problem Heaps and then they rejudged and took my 11 points :(
Auto comment: topic has been updated by purplesyringa (previous revision, new revision, compare).
i hate problems of juniors so much
like why does juniors have 3 too hard problems with not much subtasks. imo A should have a subtask when N is about 1000 for O(N ^ 2) solutions, but not N = 10, 15, 20 and then 1e6(((
Tasks for juniors were very strange for me. A is pure combinatorics, and it's not an easy problem at all, but it's OK compared to other two problems, but I would expect n <= 1000 subtask in this problem (there is quite easy 2-dimensional dp solution). In B there are only 3 groups of tests, which is too little for this problem, and also brute force solution for this task is hard, so I was able to write 42 point solution, but I couldn't write brute force quickly. Actually only 4 contestants were able to get more than 0 on this problem. And C is something inexplicable, I got only 5 points for this problem, and every person who I asked and who got got 15-25 points told, that they just spent about a half of the contest for trying to optimize brute force, so I guess nobody wrote something else. And I think that problem C had an influence on very low points on problem B.
Could you explain A solution?
I tried to explain my way to get to problem's solution.
Link
Well, the full solution on C is optimized brute force...
Auto comment: topic has been updated by purplesyringa (previous revision, new revision, compare).
55 points on juniors A2...
what happend
Auto comment: topic has been updated by purplesyringa (previous revision, new revision, compare).
Solution for B21-Monopoly: Basically, we have a directed graph and we want to transform it into a DAG by reversing the directions of some (possibly zero) edges. All we need to do is reverse the edges, for which the first node is bigger than the second one. This way, we assure that there won't be any cycles because every node can reach only a larger node.
Wow, I tested a div3 round few days ago and solved a task very similar to A22 :D So lucky...
Where can i upsolve problems if its possible?
I think this year contest was too strange. Two combinatorics problems in first day completely killed me.
Funny moment that we found during practice session. In problem about BinSearch you could make as much queries as you want and then do not call function to give answer, just cout it and 0. Checker will be looking for two integers and it will read your correct answer and zero queries. That gives you perfect score.
How to solve A21 Hint?
Here's a hint that leads to a full-score solution (almost certainly).
It is very strange, that A1 for juniors has subtask 10, 15, 20 and then 1e6. Why there is no subtask for 1000???
Where can I upsolve this tasks?
My solution for A23-Rabbit (I got 98.6 during the contest):
The scoring is complex, yet it's suffice to understand it's behavior in three states:
1) S is significantly bigger
2) S and C are close
3) C is significantly bigger
To receive a high score, we need to aim to:
case 1: K is around N/3
case 2: K is around 2N/3
case 3: K is around N/2
I'll present a solution for each case, it's not hard to merge those solutions together.
Case 2: The easiest case, we will pull the rabbit towards the Nth cell, while keeping track of the first cell the rabbit might be in. When the rabbit is scared, we will check this cell, if the rabbit is there we won, otherwise he will run further to the right, so we can increase the variable by 2. When the rabbit is curious, we will check the Nth cell, and increase the variable by 1. After ~2N/3 checks the rabbit has to be in the Nth cell, which we will check. Note that you can get partial score using only this case.
Case 3: If the rabbit is always curious, we will test the middle cell N/2 times. We will keep track of a segment [l,r], which might contain the rabbit. When the rabbit is scared, we will check the cell in index l, increase l by 2 and increase r by 1. When the rabbit is curious, we will check the middle of the segment, increase l by 1 and decrease r by 1. After /2 checks we will know where the rabbit is. I think merging those cases gives ~50 points.
Case 1: we will keep two segments — [1,l],[r,n]. at the beginning, l = r = N/3. we will run Case 2 on [r,n]; with only /3 checks since the rabbit is usually scared. If the rabbit was inside [r,n] we will find him. Otherwise, the rabbit was scared towards the first cell, which we will check afterwards. The rabbit is curious sometimes, so we have to pull the rabbit towards the Nth cell and increase l,r by 1. If I remember correctly merging those cases gives ~80.
In case 1, when C != 0 different values for l,r might lead to better performance. Therefore, we can try different values for l,r (around 700 to avoid TLE). With this improvement I got 98.6. In addition, you can pass everything with more tries (You will get TLE on some cases), so I believe you can get 100 by optimizing the solution or calculating the best value for l,r (I was too lazy to work for 1.4 points).
How to solve News task?
Firstly let us see how to solve a simpler problem: Count the number of nodes in the subtree of x(call it S(x)), that are at most k distance away from x. We will use the Euler tour array(tree flattening). In this array(call it E) for every x, S(x) corresponds to some subarray in E. Let D be an array such that for every i D[i] = depth of E[i]. Now the problem is reduced to: For given x with depth d and a number k, count how many numbers in the given subarray of D are <= d + k. This can be done with a segment tree over the array D. Every node in the segment tree will contain a sorted vector for the elements inside the range which that node covers, sorted in increasing order by the values(depths). Now when we need to answer the query (x, k): We find the corresponding subarray as well as the nodes in the segment tree that cover that range and we do a binary search on the vectors in these nodes — since every vector will have some prefix(possibly empty) of elements(values that correspond to depths) that are <= d + k.
Now for the original problem(but instead of counting how many elements do have the news we will count those that don't have the news), we have that some elements in this array D have true or false sub-values (if that element has or hasn't the news). If some element has a true value(has the news) we want to remove it from every vector from the segment tree that contains that element(there are log(N) such nodes\vectors). But removing from a vector is expensive and it will be insufficient in time. Instead of naively removing element from the log(N) vectors, we want to mark the corresponding positions of this element in the vectors, and then every time we do a query(counting) and find the prefix of some vector, we want to know the number of marked elements in that prefix. This can be easily done with BIT(so we need to store BIT for every node in the segment tree). Now it remains to show how to remove an element only the first time it gets the news(the first time when its sub-value changes from false to true). This can be done by storing a second vector in every node in the segment tree similar to the first one but this time elements should be sorted in decreasing manner with respect to depths, and every time when we do a first type query we will traverse the segment tree and we will check if the last element of this vector in this node of the segment tree is less than k + d, if yes we pop it from this vector and we update in the segment tree for all nodes that contain this element(we do the technique with BIT). Notice that we should keep track if some element is already updated since it is possible to pop the same element from different nodes and at a different time in the segment tree. But this does not slow down our algorithm since we will pop the same element from at most log(N) vectors.
I'm sorry for the first day of juniors. We didn't have many task proposals and were very limited to what we can do. We expected that many people won't spend so much time on problem 3 Sum_prod, which was pretty hard, and will have more time for the problem 2 Wall. As the author of problem 1 pretty, I didn't see n^2 solution and thus didn't made a subtask for it. Here are available analysis for some of the problems for juniors:
Will there be other analysises? Also, where we can upsolve these tasks?
Yes, there will be other analysis in a few days. We upload the tasks in our Bulgarian system: https://arena.olimpiici.com/#/catalog/572 (for the first day) and https://arena.olimpiici.com/#/catalog/507 (for the second day). We have planned to translate the interface to English in the future. The tasks for this contest will be uploaded soon.
Thank you!
so where are the other analysises?)
Here you go: http://www.math.bas.bg/infos/Shumen_2021.html
thanks!
Hi! I'm facing an issue right now, want to upsolve junior problems, but system tells me I should be registered, which then asks for email confirmation, but message with confirmation doesn't come. Do you know what can I do, or you're not responsible for that?
Use eolymp
Yep, thanks!
great solution for Pretty!
Can anyone offer a solution for the problem Miners?
5 of 6 senior problems can be upsolved on Eolymp.
UPD. Junior problems are now also available on Eolymp.
Are testcases available ?
Does anyone know where can you find editorials of problems from previous editions?
https://arena.olimpiici.com/#/catalog/507 — first day — for seniors the problems are at A
https://arena.olimpiici.com/#/catalog/579 — second day
You go to the problem you want to solve and download the zip, there you will find the solutions too.
Thanks!
A22 Delivery
I found this problem particularly interesting, or at least how I got to the final solution:
Let us first see that if one truck goes from delivery i to delivery j, then the following must be true:
(*) |h[i] — h[j]| <= T[j] — T[i]
Now we represent every delivery i as a point in the coordinate plane at (T[i], h[j]).
Imagine all the lines parallel to f(x) = x, i.e. all the lines f(x) = x + k for some integer value k. Then for (*) to be true then the following must be true: delivery i lies on some line p and j lies on some line q and the line q is on the right side of the line p, i.e. line p comes before line q. Now what we can do is translate every point that lies on some line l into the point on the x-axis that the line l intersect. After the translation, in order to be possible to go from delivery n to delivery m, n must be before m on the x-axis when these deliveries are translated.
The above also must be true for the lines f(x) = -x + k. So every delivery i translates in two points on the x-axis call them x1[i] and x2[i].
Now (*) can be writen as: x1[i] <= x1[j] & x2[i] <= x2[j]
Let us sort the deliveries according to x1 and put x2 values on their positions in the array.
Now the problem is: Given an array of elements find the minimum number of increasing subsequences such that every element in the array is in exactly 1 increasing subsequence. This is equivalent to the length of the longest decreasing subsequence in the array.
mesanu did your cp girlfriend help you at iati shumen 2021?
mesanu did your cp girlfriend help you at iati shumen 2021?
No, she has lower rating