Connector's blog

By Connector, 11 years ago, translation, In English

Problem A.

Let's define a half-filled square of size k as an empty square of size k after adding a cookie of the biggest posible size.

Notice, that if we add a cookie of the biggest possible size into the half-filled square of size 2n × 2n, it will be divided into three half-filled squares of size 2n - 1 × 2n - 1 and one filled square. After performing the same actions with the three half-filled squares we will get nine half-filled squares of size 2n - 2 × 2n - 2 and so on. It's easy to get the formula f(n) = 3 * f(n - 1), f(0) = f(1) = 1. 3n - 1 (for n > 0) and 1 (for n = 0).

Problem B.

It's obviously, that sentences should be added into the SMS greedily. Really, if we put the sentence into the new message, when it's possible to add into previous, the number of messages may be increased. The only thing you should pay attention is correct processing whitespaces between the sentences.

Problem C.

Will be added soon.

Let's learn how to solve more easy problem: it's need to count a number of lucky tickets with 1 ≤ a ≤ x and 1 ≤ b ≤ y. Rewrite sentence a * b = rev(a) * rev(b) as a / rev(a) = rev(b) / b. Brute all a and count a number of irreducible fractions a / rev(a) using, for example, map from STL. Now for every b you should count the number of fractions a / rev(a) equal to rev(b) / b and add to answer.

Come back to our problem. 

If the number of lucky tickets with 1 ≤ a ≤ maxx and 1 ≤ b ≤ maxy less than w, it should be printed  - 1. If the solution exist, let's use the method of two pointers. 

We need to keep up the quantity of lucky tickets with 1 ≤ a ≤ x and 1 ≤ b ≤ y for some state (x, y) an change it to (x,y+1), (x+1,y), (x,y-1), (x-1,y). That's why we create two structures of type map (named m1 and m2). Let's learn how to change state from (x,y) to (x,y+1), (x+1,y), (x,y-1), (x-1,y). If we want to increase  (decrase) the value of x, we should add (subtract) m2[x/rev(x)] to (from) the number of lucky tickets and increase (decrease) m1[x/rev(x)] by one. In the case of changing y you should do the similar actions.

Let's set the state (x, y), where x = maxx, y = 1 and count the quantity of lucky tickets for it. We will be increase y, while the number of lucky tickets is less than w. Obviously, that it will be the least y for x, such as it will be enough lucky tickets in the range. Relax the answer. You had to decrease x by one and do the same actions while x is greater than one.

The anser have the least value of x * y because we relaxed it with the optimal state for every x.

So, the x was equael to every value between 1 and maxx not more than once. The similar is correct for y because it was only increasing. The time need for change the value in map is O(log(map_size)), that's why the algorithm lave an asymptotic form as O(maxx * log(maxy) + maxy * log(maxx)).

Problem D.

Notice, that any point from the triangle based on first three points will be into the area bounded with the convex hull in the future. Let choose one of these points ad set it as the origin. All points of convex hull will keep in structure like map in C++, where the key is the angle of vector from the origin to a point. No two points from the hull will have the same angle.

How to answer the second-type queries? For the point from the query (A) let's find the closest point clockwise (B) and the closest point anticlockwise (C). If the vectors AB and AC make up a clockwise rotation, then point A doesn't lay into the convex or on it's bounds. 

How to answer the first-type queries? If the point from the query (C) lays into the convex hull, then do nothing else let's find two closest points clockwise relative to point C (the closest will be named A, tho other will be named B). If rotation from the vector AB to the vector AC is a counterclockwise rotation then processing points laying clockwise relative to point C in ended, else you have to delete point A from the structure and repeat the same actions. The similar actions you should apply to points anticlockwise relative to point C.

All points will be added and deleted in the structure not more than once. These operations need O(log(h)) time, where h is a number of point in convex hull. Total  asymptotic form is O(q * log(h)).

Problem E.

Notice next facts. If we have the fixed state of some regional centers then for every city will be assigned the nearest regional center. The regional center of some city will be assigned for all cities between this city and it's regional center. It means that tree should be divided into some subtrees. Also define d[0] = 0.

Let's solve the problem using "crossed" Dynamic Programming.

First function of DP. D1(T, g, x, s) will be responsible for forming the subtree with the regional center g. T is somme subtree of tree from the input defined with edge uv. regional center g must be situated in T. Let's consider that g is assigned to v. The aim will be considered in choosing edges which will bound our subtree. Picture:

Green and red edges connect cities which g was assigned. Purple edge bounds the set of such cities. Notice, that vertexes laying on the red pass cannot be bounding, because g is assigned to v. 

Let xs edge be bounding, then for subtree T' (vertexes of it's subtree are into the circle) call the secnod funtion of DP D2(T').

The second function of DP will brute every point of subtree T' as a regional center and call D1.

D1 have O(n3) states, because the number of subtrees T is O(n), number of options to choose g is the same and pair (x;s) makes up an edge, number of edges is 2*n-2. The second function of DP has O(v) states and transition need O(v) iterations. Thats why solution need O(n3) memory and have asymptotic form O(n3).

  • Vote: I like it
  • +65
  • Vote: I do not like it

11 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it
thank's for your very good Analaysis. ;)
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry, I dont really understand the analysis and have a few questions. Hope that you can help me out. Thanks!

Problem D:

May I know why the first three points of the input will definitely be in the convex hull? Is such an input impossible?

1 1 0
1 0 0
1 0 1
1 -1 2
1 2 -1
1 -1 -1

In such an input, the convex hull will be (-1,2) (-1,-1) (2,-1).

Also, for the queries B and C, how do you find the nearest point anti-clockwise and clockwise? Which line of reference do you take to determine whether a point is clockwise or anti-clockwise? And may I know how do you find the nearest point efficiently?

Problem E:

I am not too sure about the DP state definition :(.

I think that what you are saying that first, you root the tree. Then, suppose the edge uv is bounding. Then you are going to get a subtree T, which is bounded by the edge uv. In this subtree, you choose g as the regional centre. Then you try each edge and try to set it as a bounding edge for the next subtree. Suppose you have chosen the edge xs. Then you recursively work on this new subtree. You call DP 2 to bruteforce which vertex should be regional centre be located at. Then you call DP 1 again. So say you call the next subtree T' and the node you are building regional centre p. Then you will call DP1 (T', p, x, s).

Is this what you are saying? Please correct me if I am wrong.

Also, may I know how do you represent a subtree in your DP state? And it seems to me that given any tree, there are a lot more than N different subtrees (for example, given a line graph I think there are about N^2 different subtrees. There are about N^2 different sets of endpoints you can choose from, and each set defines a unique subtree). Am I missing something here?

Sorry, I am new to this kind of DP, so my questions might sound a bit obvious XD. Thanks a lot!
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it


UPD: any point from the triangle based on first three points will be into the area bounded with the convex hull in the future.

To find the nearest point efficiently use binary search tree (if you write in C++ you can use map class).


Yes, you understood what I mean. You should recursively bruteforce xs edge. T is represented in next way: edge uv divides tree into two subtrees, T is one of these subtrees containing vertex v.

  • 11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your reply! I think I understand how to do problem D now.

    But I am still not too sure about problem E. I dont quite understand the function DP 2. What does it store? Does DP 2[x] store the min cost if you build a regional centre at x? But won't the answer be different if your subtree is different? What is the recursion for DP 2 like?

    Thanks in advance again!
    • 11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      D2[T'] store the minimum cost of the maintaining the subtree T'. Let's T' be represented with the edge uv using the way described in previous post. Bruteforce all the vertexes in the sebtree T'. Let the vertex g will be fixed, let's say that it is some regional center assigned to v. Call the D1(T',g,g,0 (the first neighbour)) and relax the answer for the D2[T'] with the returned value.