Codeforces Round #361 (Div. 2) Editorial

Правка en13, от I_Love_Tina, 2016-08-29 20:22:51

A.Mike and Cellphone


We can try out all of the possible starting digits, seeing if we will go out of bounds by repeating the same movements. If it is valid and different from the correct one, we output "NO", otherwise we just output "YES".

C++ code
Another C++ code
Another C++ code
Python code

B. Mike and Shortcuts,I_Love_Tina


We can build a complete graph where the cost of going from point i to point j if |i - j| if ai! = j and 1 if ai = j.The we can find the shortest path from point 1 to point i.One optimisation is using the fact that there is no need to go from point i to point j if j ≠ s[i],j ≠ i - 1,j ≠ i + 1 so we can add only edges (i, i + 1),(i, i - 1),(i, s[i]) with cost 1 and then run a bfs to find the shortest path for each point i.

You can also solve the problem by taking the best answer from left and from the right and because ai ≤ ai + 1 then we can just iterate for each i form 1 to n and get the best answer from left and maintain a deque with best answer from right.

Complexity is O(N).

C++ code with queue
C++ code with deque
Python code

What if you have Q queries Q ≤ 2 × 105 of type (xi, yi) and you have to answer the minimal distance from xi to yi.

C. Mike and Chocolate Thieves,I_Love_Tina


Suppose we want to find the number of ways for a fixed n.

Let a, b, c, d ( 0 < a < b < c < d ≤ n ) be the number of chocolates the thieves stole. By our condition, they have the form b = ak, c = ak2, d = ak3,where k is a positive integer. We can notice that , so for each k we can count how many a satisfy the conditions 0 < a < ak < ak2 < ak3 ≤ n, their number is . Considering this, the final answer is .

Notice that this expression is non-decreasing as n grows, so we can run a binary search for n.

Total complexity: Time ~ , Space: O(1).

C++ code
Another C++ code

D. Friends and Subsequences



First of all it is easy to see that if we fix l then have . So we can just use binary search to find the smallest index rmin and biggest index rmax that satisfy the equality and add rmax - rmin + 1 to our answer. To find the min and max values on a segment [l, r] we can use Range-Minimum Query data structure.

The complexity is time and space.

C++ code O(N)
C++ code O(N log N)
C++ code O(N log ^ 2 N)
Another C++ code

What if you need to count (l1, r1, l2, r2), 1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n and .

Hint:Take idea from this problem.

C++ code for Bonus

E. Mike and Geometry Problem



Let define the following propriety:if the point i is intersected by p segments then in our sum it will be counted times,so our task reduce to calculate how many points is intersected by i intervals 1 ≤ i ≤ n.Let dp[i] be the number of points intersected by i intervals.Then our answer will be . We can easily calculate array dp using a map and partial sum trick,here you can find about it.

The complexity and memory is and O(n).

C++ code
Another C++ solution

what if where l, r are given in input.

I'm really sorry that problem A was harder than ussually.


  Rev. Язык Кто Когда Δ Комментарий
en13 Английский I_Love_Tina 2016-08-29 20:22:51 343 Reverted to en11
en12 Английский I_Love_Tina 2016-08-29 20:20:18 343
en11 Английский I_Love_Tina 2016-07-16 17:57:54 27 Tiny change: 'e can use a simple Segment Tree or a Range-Min' -> 'e can use Range-Min'
en10 Английский I_Love_Tina 2016-07-09 14:40:24 1612
en9 Английский I_Love_Tina 2016-07-08 12:27:35 936
en8 Английский I_Love_Tina 2016-07-07 10:51:20 2 Tiny change: '[Mike and C' -> '[A.Mike and C'
en7 Английский I_Love_Tina 2016-07-07 10:50:58 12
en6 Английский I_Love_Tina 2016-07-06 23:38:47 3421
en5 Английский I_Love_Tina 2016-07-06 23:29:51 672
en4 Английский I_Love_Tina 2016-07-06 23:09:25 1174
en3 Английский I_Love_Tina 2016-07-06 22:51:58 158 Tiny change: ' sum trick [here you ' -> ' sum trick,[here you '
en2 Английский I_Love_Tina 2016-07-06 22:39:45 18
en1 Английский I_Love_Tina 2016-07-06 22:30:52 12785 Initial revision (published)