Thanks to johnathan79717 fo polish my words.
If Drazil chooses the shortest path from (0,0) to (a,b), it takes |a| + |b| steps.
So we know that all numbers less than |a| + |b| are impossible to be the number of steps that Drazil took.
Now consider when the number of steps is not less than |a| + |b|.
When Drazil arrives at (a, b), he can take two more steps such as (a, b) -> (a, b + 1) -> (a, b) to remain at the same position.
So we know that for all s such that s ≥ |a| + |b| and (s - (|a| + |b|))%2 = 0, there exists a way for Drazil to get to (a, b) in exactly s steps.
The last part we should prove is that it's impossible for Drazil to arrive at (a,b) in exactly s steps when (s - (|a| + |b|))%2 = 1.
We can color all positions (x, y) where (x + y)%2 = 0 as white and color other points as black.
After each step, the color of the position you're at always changes.
So we know that it's impossible for Drazil to get to (a, b) in odd/even steps if the color of (a, b) is white/black.
Conclusion: If s ≥ |a| + |b| and (s - (|a| + |b|))%2 = 0 print "Yes", Otherwise print "No".
Time Complexity: O(1).
You may notice that Drazil invites his friends periodically, and the period of invitation patterns is at most n * m (because there are only n * m possible pairs of boys and girls).
So if no one changes from unhappy to happy in consecutive n * m days, there won't be any changes anymore since then.
We can simulate the process of having dinner until there are no status changes in consecutive n * m days.
Because there are only n+m people, it's easy to prove the simulation requires O((n + m) * n * m) days.
But in fact, the simulation takes only O( n * m) days.(More accurately, the bound is (min(n, m) + 1) * (max(n, m) - 1) )
What happens? You can do some experiments by yourself. =) (you can suppose that only one person is happy in the beginning.)
In fact, this problem can be solved in O(n + m).
Let g be the greatest common divisor of n and m. If the i-th person is happy, then all people with number x satisfying will become happy some day because of this person.
So for each 0 ≤ i ≤ g - 1, we only need to check if there exists at least one person whose number mod g is i and is happy.
If it exists for all i, the answer is 'Yes', otherwise the answer is 'No'.
First, we transform each digit of the original number as follows:
0, 1 -> empty
2 -> 2
3 -> 3
4 -> 322
5 -> 5
6 -> 53
7 -> 7
8 -> 7222
9 -> 7332
Then, sort all digits in decreasing order as a new number, then it will be the answer.
We can observe that our answer won't contain digits 4,6,8,9, because we can always transform digits 4,6,8,9 to more digits as in the conclusion, and it makes the number larger.
Then, how can we make sure that the result is the largest after this transformation?
We can prove the following lemma:
For any positive integer x, if it can be written as the form (2!) c 2 * (3!) c 3 * (5!) c 5 * (7!) c 7, there will be only one unique way.
Suppose that there exists two ways to write down x in this form, we can assume that the two ways are (2!) a 2 * (3!) a 3 * (5!) a 5 * (7!) a 7 and (2!) b 2 * (3!) b 3 * (5!) b 5 * (7!) b 7.
We find the largest i such that a i ≠ b i, Then we know there exists at least one prime number whose factor is different in the two ways.
But according to the Fundamental Theorem of Arithmetic, there is only one prime factorization of each integer. So we get a contradiction.
After getting the result, we don't need to worry about other numbers being larger than ours.
Time Complexity: O(n).
Again we give conclusion first:
First, view each cell as a vertex and connect two adjacent cells by an edge.
Then, build a queue and push all vertices of degree 1 in it.
Finally, in each iteration, we pop a vertex from the queue until the queue is empty. If the vertex is used, go to the next iteration. Otherwise, we put a tile on the vertex and its adjacent vertex, and erase these two vertices from the graph. If it yields a new vertex with degree 1, push it into the queue.
When the queue is empty, if there are still some cells not covered by any tiles, the answer will be "Not unique."
It's easy to understand that if we can put tiles on all cells by the above steps, the result is correct. But how about the remaining cases?
We will prove that when the degrees of all vertices are at least two, the solution is never unique.
Suppose there is at least one solution.
According to this solution, we can color those edges covered by tiles as black and color other edges as white.
We can always find a cycle without any adjacent edges having the same colors. (I'll leave it as an exercise. You should notice that the graph is a bipartite graph first.)
Then we can move the tiles from black edges to white edges.
So if there is at least one solution, there are in fact at least two solutions.
Time Complexity: O(nm)
There are many methods for this problem. I'll only explain the one that I used.
Let's split a circle at some point (for example between 1 and n) and draw a picture twice (i. e. 1 2 3 ... n 1 2 3 ... n), thus changing the problem from a circle to a line.
Remember that if two trees Drazil chooses are x and y, the energy he consumes is d x + d x + 1 + ... + d y - 1 + 2 * (h x + h y).
Now rewrite this formula to (d 1 + d 2 + ... + d y - 1 + 2 * h y) + (2 * h x - (d 1 + d 2 + ... + d x - 1))
Denote (d 1 + d 2 + ... + d k - 1 + 2 * h k) as R k and denote (2 * h k - (d 1 + d 2 + ... + d k - 1)) as L k
When a query about range [a, b] comes (The range [a, b] is where Drazil can choose, but not the range where the children are playing), it's equivalent to querying the maximum value of L u + R v, where u and v are in [a, b] and u < v.
Another important thing is that L u + R v always bigger than L v + R u when u < v.
So we can almost solve the problem just by finding the maximum value of L u and R v by RMQ separately and sum them up.
However, there is a special case: u = v, but we can handle it by making RMQ find the two maximum values.
Time Complexity: O(n + m).
author's code (implement with )
More information about RMQ: editorial from Topcoder
We can use dfs twice to get the farthest distance from each node to any leaves (detail omitted here), and denote the longest distance from the i-th node to any leaves as d i.
Then we choose a node with minimum value of d i as the root. We will find that for any node x, d x isn't greater than d y for any node y in the subtree of node x.
Next, we solve the problem when there's only one query of L. In all valid groups of nodes, where node x is the nearest to the root, obviously we can choose all nodes with d i ≤ d x + L into the group. Now we want to enumerate all nodes as the nearest node to the root. We denote the group of nodes generated from node i as G i.
We can do it in using dfs only once. (if the length of every edge is 1, we can do it in O(n))
Imagine that G i will almost be as same as the union of all G j where node j is a child of node i, but some nodes which are too far from node i are kicked out. Each node will be kicked out from the groups we considered at most once in the whole process. Now we want to know when it happens. We solve it as follows: When we do dfs, we reserve a stack to record which nodes we have visited and still need to come back to. Yes, it's just like the implementation of recursive functions. Then we can just use binary search to find the node in the stack that when we go back to it, the current node will be kicked out (the closest node with |d x - d i| ≥ L).
So the time complexity of the above algorithm is
Now we provide another algorithm with O( qnα(n) + nlog(n)) by union find. (Thanks Shik for providing this method.)
First, sort all nodes by d i.
Then for each query, consider each node one by one from larger d i's to smaller d i's.
At the beginning, set each node as a group of its own. We also need to record how many nodes each group contains.
When handling a node x, union all groups of itself and its children. At the same time, for each node j with d j > d x + L, we minus 1 from the record of how many nodes j's group has.
By doing these, we can get the number of nodes j in x's subtree with d j < = d x + L. That's exactly what we want to know in the last algorithm.
author's code (implement with O( qnα(n) + nlog(n))))
Simplifying this question, suppose that n and m are coprime. If n and m are not coprime and the gcd of n and m is g, then we can divide all people into g groups by the values of their id mod g and find the maximum answer between them. Obviously, If there is at least one group of friends which are all unhappy in the beginning, the answer is -1.
Now we determine the last one becoming happy, for boys and girls separately.
In fact, there's an easy way to explain this problem — finding the shortest path! View all friends as points, and add another point as the source. For all friends, we will view the distance from the source as the time becoming happy. And define two types of edges.
There is a fact: If a girl x become happy in time t, then the girl (x + n)%m will become happy in time t + n. So we can build a directed edge from point x to (x + n)%m with length n. Similar for boys.
If the i-th boy/girlfriend is happy originally, we can connect it to the source with an edge of length i. At the same time, we also connect the source to i%n-th boy( i%m for girl) with an edge of length i. You can imagine that the same gender of friends form a cycle. (eg. the (i * m)%n-th boy is connected to the ((i + 1) * m)%n)-th boy for i from 0 to n - 1)
With these two types of edges, we can find that if a friend is unhappy originally, he/she will become happy at the time value which is the length of the shortest path from the source.
The only question is that there are too many points and edges!
We can solve this problem by considering only some "important" points.
- Points connected by the second type of edges.
- Points connected to important points in 1., by the first type of edges.
And we can combine some consecutive edges of the first type to a new edge. The group of edges is the maximal edges that contain deleted points.(These deleted points always form a line).
Finally we find the maximum value of the shortest path from the source to these friends which is unhappy originally in the reduced graph.