How to solve A and L?

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

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).
×

# | User | Rating |
---|---|---|

1 | tourist | 3698 |

2 | mnbvmar | 3379 |

3 | Benq | 3339 |

4 | Vn_nV | 3330 |

5 | wxhtxdy | 3329 |

6 | LHiC | 3303 |

7 | sunset | 3278 |

8 | V--o_o--V | 3275 |

9 | Um_nik | 3247 |

10 | ecnerwala | 3245 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 185 |

2 | Errichto | 183 |

3 | rng_58 | 162 |

4 | PikMike | 159 |

5 | Vovuh | 157 |

6 | Petr | 156 |

7 | 300iq | 154 |

8 | majk | 148 |

9 | Um_nik | 147 |

10 | Swistakk | 145 |

How to solve A and L?

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

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/27/2019 07:14:36 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by TripleM5da (previous revision, new revision, compare).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

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).

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?

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.

Oh, true, 2^15 sounds much better, thanks.

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).

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!

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.

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}$$$. code

For $$$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)$$$.

And another solution for K is just straightforward simulation — maintain priority queue of all neighbour meeting times

Ye, that's what we did but somehow managed to face precision issues fixable by EPS.

I managed to get with EPS = 1e-9, one should calculate impulses instead of velocities.

Nice idea!

Hmm, how did you use precalc for different modules?

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.

My solution to D: Let's call following shape: revU

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.

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`

my solution was a little different

I 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$$$.

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!

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 solutionto 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.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?

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.

oh I thought the constraints were up to $$$10^{11}$$$ my bad :"D.

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:

code

Yay, that's amazing! I'm glad it actually passed.

Thanks for sharing!

contest link?

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 mostone 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.

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$$$.

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.

We can actually improve this construction so that each set has size $$$\leq 12$$$. To do this, subdivide the set above as follows:

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), ...

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.

Bonjour tunyash, can you please share the problemset link? Thanks.

I think it is not allowed in order to make the problemset reusable.

How to solve C?

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.