I like the idea of Endagorion to supplement the problems analysis with small challenges, somehow related to the problem preparation, it's generalization, or more effective solution. Following this, some problems in this analysis are also complemented with this sort of tasks.
Div. 2A (Wizards' Duel)
Idea of the problem: Roman Gusarev, development: timgaripov.
Let's start with determining the position of the first collision. Two impulses converge with a speed p + q, so the first collision will occur after seconds. The coordinate of this collision is given by the formula .
Note, that the distance one impulse passes while returning to it's caster is equal to the distance it has passed from the caster to the first collision. That means impulses will reach their casters simultaneously, and the situation will be identic to the beginning of the duel. Hence, the second collision (third, fourth, etc) will occur at exactly the same place as the first one.
Code example: 13836780.
Div. 2B (Rebranding)
Idea of the problem: glebushka98, development: thefacetakt.
Trivial solution will just emulate the work of all designers, every time considering all characters of the string one by one and replacing all x _{ i} with y _{ i} and vice versa. This will work in O(n·m) and get TL.
First one should note that same characters always end as a same characters, meaning the position of the letter doesn't affect the result in any way. One should only remember the mapping for all distinct characters. Let p(i, c) be the mapping of c after i designers already finished their job. Now:
- p(0, c) = c
- If p(i - 1, c) = x _{ i}, then p(i, c) = y _{ i}
- Same, if p(i - 1, c) = y _{ i}, then p(i, c) = x _{ i}
This solution complexity is O(|Σ|·m + n) and is enough to pass all the tests.
Challenge: improve the complexity to O(Σ + n + m).
Code examples: 13837577 implements O(|Σ|·m + n) and 13839154 stands for O(|Σ| + n + m).
Div. 2C\Div. 1A (Median Smoothing)
Problem idea and development: Sender.
We will call the element of a sequence stable, if it doesn't change after applying the algorithm of median smoothing for any number of times. Both ends are stable by the definition of the median smoothing. Also, it is easy to notice, that two equal consecutive elements are both stable.
Now we should take a look at how do stable elements affect their neighbors. Suppose a _{ i - 1} = a _{ i}, meaning i - 1 and i are stable. Additionaly assume, that a _{ i + 1} is not a stable element, hence a _{ i + 1} ≠ a _{ i} and a _{ i + 1} ≠ a _{ i + 2}. Keeping in mind that only 0 and 1 values are possible, we conclude that a _{ i} = a _{ i + 2} and applying a median smoothing algorithm to this sequence will result in a _{ i} = a _{ i + 1}. That means, if there is a stable element in position i, both i + 1 and i - 1 are guaranteed to be stable after one application of median smoothing. Now we can conclude, that all sequences will turn to stable at some point.
Note, that if there are two stable elements i and j with no other stable elements located between them, the sequence of elements between them is alternating, i.e. a _{ k} = (a _{ i} + k - i)mod2, where . One can check, that stable elements may occur only at the ends of the alternating sequence, meaning the sequence will remain alternating until it will be killed by effect spreading from ending stable elements.
The solution is: calculate max(min(|i - s _{ j}|)), where s _{ j} are the initial stable elements. Time complexity is O(n).
Challenge 1: hack the solution that just applies median smoothing until something changes.
Challenge 2: think of how to speed up the algorithm from challenge 1 using bitmasks (still gets TL).
Code examples: 13838940 and 13838480.
Div. 2D\Div. 1B (Chip 'n Dale Rescue Rangers)
Problem idea and development: StopKran.
If the velocity of the dirigible relative to the air is given by the vector (a _{ x}, a _{ y}), while the velocity of the wind is (b _{ x}, b _{ y}), the resulting velocity of the dirigible relative to the plane is (a _{ x} + b _{ x}, a _{ y} + b _{ y}).
The main idea here is that the answer function is monotonous. If the dirigible is able to reach to target in seconds, then it can do so in seconds, for any x ≥ 0. That is an obvious consequence from the fact the maximum self speed of the dirigible is strictly greater then the speed of the wind at any moment of time.
For any monotonous function we can use binary search. Now we only need to check, if for some given value it's possible for the dirigible to reach the target in seconds. Let's separate the movement of the air and the movement of the dirigible in the air. The movement cause by the air is:
- (x _{ n}, y _{ n}) = , if ;
- (x _{ n}, y _{ n}) = , for .
The only thing we need to check now is that the distance between the point (x _{ n}, y _{ n}) and the target coordinates (x _{2}, y _{2}) can be covered moving with the speed v _{ max} in seconds assuming there is no wind.
Time complexity is , where C stands for the maximum coordinate, аnd ε — desired accuracy.
Challenge 1: think of the solution in case it's not guaranteed that the dirigible is faster than the wind.
Challenge 2: can you come up with O(1) solution?
Code examples: 13838659 and 13842505.
Div. 2E\Div. 1C (Three States)
Problem idea and development: haku.
Affirmation. Suppose we are given an undirected unweighted connected graph and three distinct chosen vertices u, v, w of this graph. We state that at least one minimum connecting network for these three vertices has the following form: some vertex c is chosen and the resulting network is obtained as a union of shortest paths from c to each of the chosen vertices.
Proof. One of the optimal subgraphs connecting these three vertices is always a tree. Really, we can take any connecting subgraph and while there are cycles remaining in it, take any cycle and throw away any edge of this cycle. Moreover, only vertices u, v and w are allowed to be leaves of this tree, as we can delete from the network any other leaves and the network will still be connected. If the tree has no more than three leaves, it has no more than one vertex with the degree greater than 2. This vertex is c from the statement above. Any path from c to the leaves may obviously be replaced with the shortest path. Special case is than there is no node with the degree greater than 2, meaning one of u, v or w lies on the shortest path connecting two other vertices.
The solution is: find the shortest path from each of the chosen vertices to all other vertices, and then try every vertex of the graph as c. Time complexity is O(|V| + |E|).
To apply this solution to the given problem we should first build a graph, where cells of the table stand for the vertices and two vertices are connected by an edge, if the corresponding cells were neighboring. Now we should merge all vertices of a single state in one in order to obtain a task described in the beginning. Time complexity is a linear function of the size of the table .
Code examples: 13843265 — the solution described above that uses 0-1 bfs instead of merging, 13840329 — another approach that tries to different cases.
Div. 1D (Top Secret Task)
Problem idea and development: glebushka98.
If , than the sum of k minimums is obviously an answer.
Let i _{1} < i _{2} < ... < i _{ k} be the indices of the elements that will form the answer. Note, that the relative order of the chosen subset will remain the same, as there is no reason to swap two elements that will both be included in the answer. The minimum number of operations required to place this k elements at the beginning is equal to — .
T ≤ S ≤ . .
Calculate the dynamic programming d[i][j][p] &mdash minimum possible sum, if we chose j elements among first i with the total indices sum no greater than p. In order to optimize the memory consumption we will keep in memory only two latest layers of the dp.
Time complexity is O(n ^{4}), with O(n ^{3}) memory consumption.
Code examples: 13845513 and 13845571.
Div. 1E (Birthday)
Problem idea: _meshanya_, development: romanandreev.
The given problem actually consists of two separate problems: build the directed graph of substring relation and find the maximum independent set in it. Note, that if the string s _{2} is a substring of some string s _{1}, while string s _{3} is a substring of the string s _{2}, then s _{3} is a substring of s _{1}. That means the graph of substring relation defines a partially ordered set.
To build the graph one can use Aho-Corasick algorithm. Usage of this structure allow to build all essential arc of the graph in time O(L), where L stands for the total length of all strings in the input. We will call the arc essential, if there is no w, such that and . One of the ways to do so is:
- Build Aho-Corasick using all strings in the input;
- For every node of the Aho-Corasick structure find and remember the nearest terminal node in the suffix-link path;
- Once again traverse all strings through Aho-Corasick. Every time new symbol is added, add an arc from the node corresponding to the current string (in the graph we build, not Aho-Corasick) to the node of the graph corresponding to the nearest terminal in the suffix-link path;
- The previous step will build all essential arcs plus some other arcs, but they do not affect the next step in any way;
- Find the transitive closure of the graph.
To solve the second part of the problem one should use the Dilworth theorem. The way to restore the answer subset comes from the constructive proof of the theorem.
Time complexity is O(L + n ^{3}) to build the graph plus O(n ^{3}) to find the maximum antichain. The overall complexity is O(L + n ^{3}).
Congratulation to ikatanic — — the only participant to solve this problem during the contest. View his code 13851141 for further clarifications.
Challenge: solve the problem with the same asymptotic, if we are to find the subset with the maximum total length of all strings in it.
UPD: sorry something was wrong on my side.
You're going to take us places, GlebsHP. Great round!
Has anyone been able to come up with an O(1) solution for Div 1 — B?
Accepted solution: http://codeforces.com/contest/590/submission/13860359
Explanations: http://codeforces.com/blog/entry/21185?#comment-258444
Thanks!
check this out...(http://codeforces.com/contest/591/submission/13839965)
self explanatory O(n) :-)
Here's another solution in O(1) for Div1 — B:
Without loss of generality suppose x _{1} = y _{1} = 0. Clearly when the wind is the same, it is optimal to keep the velocity the same.
First, we check if we can get from start to finish in time <= T.
If we could, then there is a constant k (where the units of k is ) such that (here I am using vector notation so (a, b) denotes vector) |k(x _{2}, y _{2}) - (v _{ x}, v _{ y})| = v _{ max}.
We can simply square this equation, and this results in a quadratic in k, which we can solve.
If then we are done and we can simply take that value of as our answer.
Otherwise, our solution is as follows:
Going from our starting point, the locus of points we can reach within time T is a circle which contains all the points of the form t(v _{ max} cos θ + v _{ x}, v _{ max} sin θ + v _{ y}). This is a circle with center ( - tv _{ x}, - tv _{ y}) and radius tv _{ max}.
Say that we take g extra time to reach the end, where g is in seconds.
Going from our ending point, the locus of points we could have started at time T is a circle which contains all the points of the form (x _{2} + gv _{ max} cos θ - gw _{ x}, y _{2} + gv _{ max} cos θ - gy _{ x}). This is a circle with center (x _{2} - gw _{ x}, y _{2} - gy _{ x}) and radius gv _{ max}.
Now our job is simply to check whether these two circles intersect; that is, if (distance_between_centers <= sum_of_radii). This results in a quadratic equation in g which we can also solve.
My code: 13927040
EDIT: Included submission. Also changed < to <=)
How do you solve those equations without known values for theta? Did you write four equations (two circles, two coordinates), then solve that as a system of four equations with three variables (theta1, theta2 and g)? I'm probably overcomplicating but I don't see how else I can fill in the blanks :D
θ is a parameter that I use to describe the geometric shape that I am talking about; it is not actually a variable I am solving for. For example, I could describe the unit circle as points of the form (cos θ, sinθ). Nice catch!
g is a variable that I am solving for.
In the quadratic equations that I mention in my explanation, I only have one unknown value ( k and g).
Actually, why do Div 1 and Div 2 always share 3 problems? Why not share 1 or 2 problems only? I think this can make the Div 1 and Div 2 rounds easier for Div 2 participants.
Div.2B English alphabet size denoted as |Σ|, what sort of notation is that?
How to calculate upper limit for time in Div1 B?
Wait, so in the problem, Median Smoothing, there is not a single situation where the sequence will never become stable?
590D - Top Secret Task I try to approach the problem as to find a sequence of K numbers out of N number that has minimum sum (minsum DP?) but keep noting that the total difference between its index in the minsum sequence and its index in the input array to be still <=S. but I still get a WA verdict and i don't know why. this is my code : 14179833
is my approach wrong or my code that has bugs?
The tutorial for problem E gives a link to Dilworth theorem in Wikipedia. A few minutes ago I have read the inductive proof in Wikipedia and realized that it is wrong, and I've marked it in that article in Wikipedia. So, as the link is wrong, could you please give us an aditional hint on how to solve this independent set problem. Thanks.
My previous comment is wrong.
Can someone explain me the Div.1 A problem... I have been trying it for long now and after making observations,cant solve the problem as a whole,cant put those observations together.. Also,in the author's solution,they say that it's impossible for a series to be never stable..How can we proof that?!
Observations: 1) If value at i is equal to either value at i-1 or i+1,value at i will never change 2)Let p[i] denote the number of steps taken to make value at i stable.And we will use the above observation to mark all such pts 0,i.e p[i]=0.And p[1]=0 and p[n]=0.Let's call i with p[i]=0 as hinge,as it never changes. 3)At every step, hinges influence its surrounding pts and tries to make their value equal to it's. 4)So,calculate the nearest hinge for every point,i will be equal to the value of nearest hinge.
Lol, you explain better than the editorialist.
lol,after solving the problem,I read the editorial and I myself couldn't understand.
How to solve the challenge of Div1E i.e. how to find the maximum weight antichain of a POSET? I tried googling but couldn't find a reasonable solution for this specific challenge.