Due to the installation of a new fire alarm in ITMO server room, the system may be occasionally unavailable on the 27-th of May between 06:00 and 15:00 (UTC). ×

### TripleM5da's blog

By TripleM5da, history, 5 weeks ago, ,

How to solve A and L?

Also what is D's judge solution, I am not sure if mine was the intended one.

•
• +38
•

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by TripleM5da (previous revision, new revision, compare).
 » 5 weeks ago, # |   +8 B or K anyone?We solved both but B included precalc for values from 80 to 100 and K was accepted by changing EPS value from $10^{-9}$ to $10^{-12}$, I don't think these were the intended solutions. :D
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 My B was: dp of order: i * n * 2^15 where we are to find i-interesting permutation of length n. And I assumed the coprime-prefix won't be more than ~30 [number of prime within 100].K: I kept a list of objects and then I went from left to right. With a new object, I pushed it into the list. Next, I checked (in a loop) if I can merge the last two objects of the list. If so I merged it (and then I kept checking the last two objects). Merging means, summation of the mass and summation of velocity (+1, -1s). Note, the real velocity of the object is: (sum of velocity)/(sum of mass). Two objects can be merged if they can ever be merged (it does not matter in which order they merge).
•  » » » 5 weeks ago, # ^ |   0 We thought of doing this mitm but all we've come up with is $3^{number~of~primes}$. Can you elaborate a bit more on your solution?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +16 B: The key is to use 2^15 instead of 2^25 (we can ignore all primes above 50).K: Suppose that the velocities are $v_1, \ldots, v_n$ from left to right. Plot points $(i, v_1 + \ldots + v_i)$. The solution corresponds to lower convex hull of these points.
•  » » » » 5 weeks ago, # ^ |   +8 Oh, true, 2^15 sounds much better, thanks.
•  » » » » 5 weeks ago, # ^ |   +27 Actually you only need to store mask for primes less than $\sqrt{n}$. For all bigger primes we can group numbers by that biggest prime divisor and make all transitions at once (thus we can take only one of them) and then forget about this prime because we can never encounter it afterwards.So actually this problem can be solved for much larger $n$ (up to 500 easily).
•  » » » » » 5 weeks ago, # ^ |   0 Could you please elaborate more about why we can store mask for primes less than $\sqrt{n}$?I understand why we can store mask for primes less than 50, but what about $\sqrt{n}$?Thank you!
•  » » » » » » 5 weeks ago, # ^ |   0 Each number have a set of small (smaller than $\sqrt{n}$) and maybe one big prime. Let's look at all numbers with given big prime. We can take one of them (or none). So we can do all transitions using numbers from this group at once and forget about this prime.
•  » » 5 weeks ago, # ^ |   +8 For $K$ we sorted all $X$ values and than use one stack for simulation whole process. We didn't use any double values, just save pairs $(a,b)$ — current element has speed $\frac {a}{b}$. codeFor $B$ we had around $2^{14} \cdot 11 * n^2$ operations. But the thing is that for all values $i>25$ answer is zero ( have $1$ + $24$ different primes). Even it can be reduced from $n^2$ to $n \cdot log(n)$.
•  » » 5 weeks ago, # ^ |   +8 And another solution for K is just straightforward simulation — maintain priority queue of all neighbour meeting times
•  » » » 5 weeks ago, # ^ |   0 Ye, that's what we did but somehow managed to face precision issues fixable by EPS.
•  » » » » 5 weeks ago, # ^ |   +16 I managed to get with EPS = 1e-9, one should calculate impulses instead of velocities.
•  » » » » » 5 weeks ago, # ^ |   +8 Nice idea!
•  » » 5 weeks ago, # ^ |   0 Hmm, how did you use precalc for different modules?
•  » » » 5 weeks ago, # ^ |   +8 We calculated without the modulo, the lengths of numbers are not that huge. It got to about 70kb for all answers from 80 to 100.
 » 5 weeks ago, # |   +8 My solution to D: Let's call following shape: revU .... .xx. The count for: revU = 6, count for two revU separated by a column of x is: = 2*(2 + 6) = 16, appending another revU separated by column of x = 2*(2 + 16) = 36. And so on.So I greedily take the largest number from this sequence. You will see that, 20 revU is the largest number less than 1e7. revU takes 4 columns and one separator, so total 5 column for single revU. 20 revU requires 20*5 = 100 columns.You can also put I shapes side by side separated by a column of x, to add some small number (base case).There is some minor details I am omitting.
•  » » 5 weeks ago, # ^ |   +3 My output looks like this..xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ...x...x...xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx .x.x.x.x.x.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xx.xxx.xxx.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ...x...x...x...x...x...x...xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx .x.x.x.x.x.x.x.x.x.x.x.x.x.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xx.xxx.xxx.xxx.xxx.xxx.xxx.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ...x...x...x...x...x...x...x...x...x...xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx .x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ...x...x...x...x...x...x...x...x...x...x...x...x...x...xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx .x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ...x...x...x...x...x...x...x...x...x...x...x...x...x...x...xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx .x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ...x...x...x...x...x...x...x...x...x...x...x...x...x...x...x...xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx .x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ...x...x...x...x...x...x...x...x...x...x...x...x...x...x...x...x...xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx .x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   0 my solution was a little differentI used :....xx and appended this shape to itself i times it turned out that it gets $Fibo_{i+4}-1$ each time so every I just searched for the most repetitions I can make such that they are less than $K$.
•  » » 5 weeks ago, # ^ |   0 Yeah, this is exactly the building block used in the jury solution as well (code). Sure, various other building blocks can also help.For both problems C (Blocking Crosses) and D (Exact Number of Calls), I started developing them with randomized solutions in mind, but ended up with constructive approaches. However, if anyone solved them with non-constructive algorithms, I'd love to hear about that in the comments!
•  » » » 5 weeks ago, # ^ |   0 More about problem D.Note that the checker is essentially written in the statement, and it's not at all hard to implement. Once you have the checker, you can actually try it on several small boards if you look for building blocks and ways to merge them. Or you can try constructing a large board with a large answer, and then remove its lower pieces to get a good approximation for the desired number of steps.The important thing is, all this stuff is way easier once you accept the thought of dedicating computer time to find the solution to the problem, as opposed to solving completely on paper or in your head, and start implementing only then. Just a few minutes are required to write a checker and run it on some inputs. Solving it on paper, and doing the simulation in your head, must generally consume more wall-clock time.
•  » » » » 5 weeks ago, # ^ |   +8 Actually that got me thinking that can not be the problem's actual checker, so i am interested how did you write the actual checker for the solution?
•  » » » » » 5 weeks ago, # ^ |   0 The checker should react properly to wrong input, yeah. There is also a polynomial speedup: maintaining a doubly-linked list of empty squares. Other than that, it's the same recursive function.The constraints were only up to $10^{7}$, both to make the checker simple and to allow using the checker in the solution.I believe there is actually a polynomial solution to this checking problem, based on some math involving Aztec diamonds, but it's a wholly different story.
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 oh I thought the constraints were up to $10^{11}$ my bad :"D.
•  » » » 5 weeks ago, # ^ |   +16 The following randomized solution for C passed.Let's start with some random placement. While there's at least one movable piece, repeat the following: Choose a movable piece at random. Let $(x, y)$ be its center. Remove all pieces whose centers are within the rectangle $[x-2, x+2] \times [y-2, y+2]$. Let $S$ be the collection of all cells in the rectangle $[x-4, x+4] \times [y-4, y+4]$ Shuffle $S$. For each cell in $S$, check if we can put a new piece such that the cell becomes the center of the piece, and put it if we can. code
•  » » » » 5 weeks ago, # ^ |   0 Yay, that's amazing! I'm glad it actually passed.Thanks for sharing!
 » 5 weeks ago, # |   0 contest link?
 » 5 weeks ago, # |   +44 Problem AIf there were only two persons A and B, the optimal solution would look like this: sort the cakes by $A_i / B_i$, A eats some prefix, then they share at most one cake, then B eats the rest. Similarly, if there are three persons A, B, C, there is at most one cake shared by A and B, by B and C, by C and A, so at most three shared cakes in total. In fact, it may be the case that there is a cake shared by all of them. Consider two cases: 1. There is no cake shared by all three peopleAnd there may be a cake shared by each pair of them. By writing down some math, we can conclude that only two of them actually exists, i.e. there are two persons that don't share any cake. Assume they are A and B. Binary search the answer, now we want to find out whether they can finish before time $X$. Sort the cakes by $A_i / B_i$, there must be some prefix of cakes that will be eaten by A or C, and the rest will be eaten by B or C. Let's sort the prefix by $A_i / C_i$, A will eat cakes one by one until the time reaches $X$, C will eat the rest. Similarly, sort the suffix by $B_i / C_i$, we will get the time for C to finish. This can be simulated easily when we iterate the prefix. (I used Fenwick Tree, got TLE, had to squeeze to get AC after contest. I think it could be done in $O(N)$.) 2. There is a cake shared by all three peopleActually, we don't have to do this case separately. Just duplicate all cakes from the start and divide the answer by 2, this way there is always an optimal answer that falls into case 1. It was actually hinted in the second sample.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +74 This problem can be solved using duality in linear programming (or, equivalently, Minimax theorem). Basic idea is the following: fix $\alpha, \beta, \gamma \geq 0$, $\alpha + \beta + \gamma = 1$, then minimize $\alpha \cdot (\text{time of the first}) + \beta \cdot (\text{time of the second}) + \gamma \cdot (\text{time of the third})$. It's clear that if the answer to the original problem was $A$, then the answer to this new problem is $\leq A$. The converse is also true: one can find $\alpha$, $\beta$, $\gamma$ so that the answer to the new problem is equal to $A$. So it suffices to do ternary search for $\alpha$, $\beta$, $\gamma$.
 » 5 weeks ago, # |   +44 Problem L: To partition a subtree, assume that its parent, its leftmost leaf and its rightmost leaf are already assigned to the same set. Now assign the 'left path' and the 'right path' to a new set, together with the lefmost and rightmost leafs of subtrees hanging of these paths. Now we can partition those subtrees recursively, since the assumption is satisfied for them.Below is a picture to make it more clear. The red nodes are already assigned to some set (the same set for all three). The green nodes are assigned to a new set. The purple subtrees are assigned recursively.
•  » » 5 weeks ago, # ^ |   +36 We can actually improve this construction so that each set has size $\leq 12$. To do this, subdivide the set above as follows:  1 | 2 / \ 3 3 / \ / \ 4(3) (3)4 / \ / \ ... (4) (4) ... / \ 3 3 / \ / \ 2 (3) (3) 2 / \ / \ 1 2 2 1 Here 1 is the initial color, 2, 3, 4, ... are new colors. (k) is a subtree with leftmost and rightmost leaves colored k; (k) is then colored recursively with new colors. One can see that the resulting compressed graph is a tree since the new edges are (1, 2), (2, 3), (3, 4), ...
•  » » » 5 weeks ago, # ^ |   +7 Oh, awesome! I knew that such decomposition exists but could not construct one explicitly! If anybody is interested, such decomposition is called tree-partition, it is connected with the standard treewidth: https://arxiv.org/abs/math/0602507.
•  » » » » 5 weeks ago, # ^ |   0 Bonjour tunyash, can you please share the problemset link? Thanks.
•  » » » » » 5 weeks ago, # ^ |   0 I think it is not allowed in order to make the problemset reusable.
 » 4 weeks ago, # |   +8 How to solve C?
•  » » 4 weeks ago, # ^ |   +6 Here is a constructive solution with a low number of cases.There is an obvious structure for sizes $(3 a) \times (3 b)$: Спойлер.|..|..|..|. -+--+--+--+- .|..|..|..|. .|..|..|..|. -+--+--+--+- .|..|..|..|. .|..|..|..|. -+--+--+--+- .|..|..|..|. Now, suppose the height is not divisible by $3$; if it's width instead, rotate the board. First we get solutions for odd width, that is, for $(2 k + 1) \times (3 t + 1)$ and for $(2 k + 1) \times (3 t + 2)$: Спойлер...|...|...|. .|...|...|... .|-+-|-+-|-+- -+-|-+-|-+-|. -+-|-+-|-+-|. .|-+-|-+-|-+- .|.|.|.|.|.|. ...|...|...|. .|-+-|-+-|-+- ...|...|...|. -+-|-+-|-+-|. .|-+-|-+-|-+- .|...|...|... -+-|-+-|-+-|. .|...|...|... Finally, to get solutions for even width, that is, for $(2 k) \times (3 t + 1)$ and for $(2 k) \times (3 t + 2)$, we can repeat the second step of the pattern once, just to increase width by an odd number: Спойлер...|..|...|...|. .|......|...|... .|-+--+-|-+-|-+- -+-|..|-+-|-+-|. -+-|..|-+-|-+-|. .|-+--+-|-+-|-+- .|.|..|.|.|.|.|. ...|..|...|...|. .|-+--+-|-+-|-+- ...|..|...|...|. -+-|..|-+-|-+-|. .|-+--+-|-+-|-+- .|......|...|... -+-|..|-+-|-+-|. .|......|...|... Here it is in code.