### TripleM5da's blog

By TripleM5da, history, 6 months 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

 » 6 months ago, # |   0 Auto comment: topic has been updated by TripleM5da (previous revision, new revision, compare).
 » 6 months 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
•  » » 6 months 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).
•  » » » 6 months 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?
•  » » » 6 months 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.
•  » » » » 6 months ago, # ^ |   +8 Oh, true, 2^15 sounds much better, thanks.
•  » » » » 6 months 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).
•  » » » » » 6 months 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!
•  » » » » » » 6 months 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.
•  » » 6 months 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)$.
•  » » 6 months ago, # ^ |   +8 And another solution for K is just straightforward simulation — maintain priority queue of all neighbour meeting times
•  » » » 6 months ago, # ^ |   0 Ye, that's what we did but somehow managed to face precision issues fixable by EPS.
•  » » » » 6 months ago, # ^ |   +16 I managed to get with EPS = 1e-9, one should calculate impulses instead of velocities.
•  » » » » » 6 months ago, # ^ |   +8 Nice idea!
•  » » 6 months ago, # ^ |   0 Hmm, how did you use precalc for different modules?
•  » » » 6 months 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.
 » 6 months 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.
•  » » 6 months 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
•  » » 6 months 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$.
•  » » 6 months 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!
•  » » » 6 months 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.
•  » » » » 6 months 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?
•  » » » » » 6 months 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.
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 oh I thought the constraints were up to $10^{11}$ my bad :"D.
•  » » » 6 months 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
•  » » » » 6 months ago, # ^ |   0 Yay, that's amazing! I'm glad it actually passed.Thanks for sharing!
 » 6 months ago, # |   0 contest link?
 » 6 months 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.
•  » » 6 months 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$.
 » 6 months 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.
•  » » 6 months 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), ...
•  » » » 6 months 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.
•  » » » » 6 months ago, # ^ |   0 Bonjour tunyash, can you please share the problemset link? Thanks.
•  » » » » » 6 months ago, # ^ |   0 I think it is not allowed in order to make the problemset reusable.
 » 6 months ago, # |   +8 How to solve C?
•  » » 6 months 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)$: Spoiler.|..|..|..|. -+--+--+--+- .|..|..|..|. .|..|..|..|. -+--+--+--+- .|..|..|..|. .|..|..|..|. -+--+--+--+- .|..|..|..|. 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)$: Spoiler...|...|...|. .|...|...|... .|-+-|-+-|-+- -+-|-+-|-+-|. -+-|-+-|-+-|. .|-+-|-+-|-+- .|.|.|.|.|.|. ...|...|...|. .|-+-|-+-|-+- ...|...|...|. -+-|-+-|-+-|. .|-+-|-+-|-+- .|...|...|... -+-|-+-|-+-|. .|...|...|... 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: Spoiler...|..|...|...|. .|......|...|... .|-+--+-|-+-|-+- -+-|..|-+-|-+-|. -+-|..|-+-|-+-|. .|-+--+-|-+-|-+- .|.|..|.|.|.|.|. ...|..|...|...|. .|-+--+-|-+-|-+- ...|..|...|...|. -+-|..|-+-|-+-|. .|-+--+-|-+-|-+- .|......|...|... -+-|..|-+-|-+-|. .|......|...|... Here it is in code.