ReachingPoints [source code]
public class ReachingPoints {
static
/******************************************************************************/
class Solution {
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
while (tx != ty) {
if (tx > ty) {
if (tx % ty > 0)
tx %= ty;
else
tx -= ty;
if (sy == ty)
return (sy == 1 && tx > sx) || sx == tx || Math.abs (sx - tx) == sy || (sy > 1 && (sx - tx) % sy == 0);
} else {
if (ty % tx > 0)
ty %= tx;
else
ty -= tx;
if (sx == tx)
return (sx == 1 && ty > sy) || sy == ty || Math.abs (sy - ty) == sx || (sx > 1 && (sy - ty) % sx == 0);
}
}
return sx == tx && sy == ty;
}
}
/******************************************************************************/
public static void main(String[] args) {
ReachingPoints.Solution tester = new ReachingPoints.Solution();
int[] inputs = {
1,1,3,5,1,
1,1,2,2,0,
1,1,1,1,1,
1, 7, 999999995, 7, 1,
9,5,12,8,0,
9, 10, 9, 19, 1,
1, 8, 4, 15, 0,
2,9,5,11,0,
1,1,4,17,1,
};
for (int i = 0; i < inputs.length / 5; i++) {
int sx = inputs[5 * i], sy = inputs[5 * i + 1], tx = inputs[5 * i + 2], ty = inputs[5 * i + 3];
boolean ans = inputs[5 * i + 4] > 0;
System.out.println (Printer.separator ());
boolean output = tester.reachingPoints (sx, sy, tx, ty);
System.out.printf ("(%d, %d) to (%d, %d) -> %s, expected: %b\n",
sx, sy, tx, ty, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
上次LR那个题目关键是理解了move本身的本质, 而不是代办的按照机器人的思路真的去走move; 既然是一个hard的题目, 单纯的DFS未必能够成功; 这种情况尤其容易出现的是, 这个move search的题目, 居然最后的返回值居然是boolean; 如果真的只是一个DFS的题目, 一般让你返回的是一个最值, min或者max, 因为假定是肯定能找到的, 但是如果存在不能成功的情况, 尤其是只关注是否能成功(也就是假如能成功, 也不关注最值), 这个时候格外暗示, 要你理解move本身的本质, 然后找到一些特别的observation;
好歹有一个正确的代码, 但是这个代码TLE了!!! 不亏是hard, 看来要更深层的挖掘;
break掉的是这个case: 1, 7, 999999995, 7. 看看能不能针对这个test本身提出的现象找到什么优化;
这题是我第一次在contest时间限制内完成的hard题了; 最后实际上我也不知道这个算法到底代表了什么, 基本上就是不停的被break最后出来这个代码的; contest记录一共有6个bug, 你想吧; 速度是13ms (NA).
editorial
Approach #1: Exhaustive Search [Time Limit Exceeded]
Intuition and Algorithm
Each point has two children as specified in the problem. We try all such points recursively.
class Solution {
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
if (sx > tx || sy > ty) return false;
if (sx == tx && sy == ty) return true;
return reachingPoints(sx+sy, sy, tx, ty) || reachingPoints(sx, sx+sy, tx, ty);
}
}
Approach #2: Dynamic Programming [Time Limit Exceeded]
Intuition and Algorithm
As in Approach #1, we search the children of every point recursively, except we use a set seen so that we don't repeat work.
import java.awt.Point;
class Solution {
Set<Point> seen;
int tx, ty;
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
seen = new HashSet();
this.tx = tx;
this.ty = ty;
search(new Point(sx, sy));
return seen.contains(new Point(tx, ty));
}
public void search(Point P) {
if (seen.contains(P)) return;
if (P.x > tx || P.y > ty) return;
seen.add(P);
search(new Point(P.x + P.y, P.y));
search(new Point(P.x, P.x + P.y));
}
}
虽然加了一个memo, 但是毕竟是hard题, 不可能那么轻松就AC了;
注意这里不需要用Map: 如果seen了但是我们还没有return, 那么肯定是一个失败案例; 我们最后要找的是只要有一个就行了, 所以真的到了seen里面有success的时候, 我们早就应该直接返回了;
Approach #3: Work Backwards (Naive Variant) [Time Limit Exceeded]
Intuition
Every parent point (x, y) has two children, (x, x+y) and (x+y, y). However, every point (x, y) only has one parent candidate (x-y, y) if x >= y, else (x, y-x). This is because we never have points with negative coordinates.
Looking at previous successive parents of the target point, we can find whether the starting point was an ancestor. For example, if the target point is (19, 12), the successive parents must have been (7, 12), (7, 5), and (2, 5); so (2, 5) is a starting point of (19, 12).
Algorithm
Repeatedly subtract the smaller of {tx, ty} from the larger of {tx, ty}. The answer is true if and only if we eventually reach sx, sy.
class Solution {
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
while (tx >= sx && ty >= sy) {
if (sx == tx && sy == ty)
return true;
if (tx > ty) tx -= ty;
else ty -= tx;
}
return false;
}
}
我一开始也是这么写的, 上面也说过了, 这种move search的题目, 一个很关键的不是单纯的去simulate这些move, 而是要理解这些move背后的性质; 没有多少人面试你就是为了看你会不会写一个DFS暴搜;
当然, hard题嘛, 绕一个弯还不够, 后面想到了用mod来加速, 但是mod毕竟不如减法那么容易控制, 带来了更多的复杂性, 最后时间都花在debug上面了; 这个题目contest当时好像大家debug的都比较辛苦;
Approach #4: Work Backwards (Modulo Variant) [Accepted]
Intuition
As in Approach #3, we work backwards to find the answer, trying to transform the target point to the starting point via applying the parent operation (x, y) -> (x-y, y) or (x, y-x) [depending on which one doesn't have negative coordinates.]
We can speed up this transformation by bundling together parent operations.
Algorithm
Say tx > ty. We know that the next parent operations will be to subtract ty from tx, until such time that tx = tx % ty. When both tx > ty and ty > sy, we can perform all these parent operations in one step, replacing while tx > ty: tx -= ty with tx %= ty.
Otherwise, if say tx > ty and ty <= sy, then we know ty will not be changing (it can only decrease). Thus, only tx will change, and it can only change by subtracting by ty. Hence, (tx - sx) % ty == 0 is a necessary and sufficient condition for the problem's answer to be True.
这个观察还是挺到位的; 感觉他这个算法最后做的还算比较简练, 是因为他注意到了, 一旦t和s的坐标不同向了(!tx >= sx && ty >= sy)的时候, 就没有必要继续了; 事实上, 他下面代码, 两个else return的地方, 应该是只可能是ty == sy, 因为既然能够进入这个循环, 就首先要满足while header的条件;
The analysis above was for the case tx > ty, but the case ty > tx is similar. When tx == ty, no more moves can be made.
class Solution {
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
while (tx >= sx && ty >= sy) {
if (tx == ty) break;
if (tx > ty) {
if (ty > sy) tx %= ty;
else return (tx - sx) % ty == 0;
} else {
if (tx > sx) ty %= tx;
else return (ty - sy) % tx == 0;
}
}
return (tx == sx && ty == sy);
}
}
复杂度是O(log(max(tx, ty)));
The analysis is similar to the analysis of the Euclidean algorithm
https://leetcode.com/problems/reaching-points/discuss/114726/C++-Simple-iterative.
If sx,sy occurs in the path of Euclidean method to get GCD (by subtracting lesser value from greater value) of tx,ty, then return true.
To see why this is true, consider how the tx, ty could have been formed if tx > ty. Let ax, ay be the pair in previous step. It cannot be ax, ax+ay because both ax and ay are greater than 0. So the only other possibility is ax+ay, ay. This means ay = ty and ax = tx-ty. Now we can optimize this subtraction a bit by doing ax = tx % ty since we will keep subtracting ty from tx until tx > ty.
One special case we need to handle during this optimization is when tx=9,ty=3,sx=6, sy=3 which can be covered using the condition if(sy == ty) return (tx - sx) % ty == 0;
Similar argument applies for tx <= ty.
bool reachingPoints(int sx, int sy, int tx, int ty) {
while(tx >= sx && ty >= sy){
if(tx > ty){
if(sy == ty) return (tx - sx) % ty == 0;
tx %= ty;
}else{
if(sx == tx) return (ty - sy) % tx == 0;
ty %= tx;
}
}
return false;
}
这个代码比awice的版本还要简练一些;
Basic idea:
If we start from sx,sy, it will be hard to find tx, ty.
If we start from tx,ty, we can find only one path to go back to sx, sy.
I cut down one by one at first and I got TLE. So I came up with remainder.
这里介绍这个问题的思考方式类似一个tree; s是最开始的root, 然后按照DFS的思路, 我们其实有最后很多的子node; t就是其中的一个; 如果从s开始找t, 那么就有无限多种可能性, 但是如果从比如一个leaf的位置向上找parent, 就只有一种可能性;
当然, 这个只是一个抽象概念上的对这道题的理解, 这道题就算认识到这个思路, 后面的计算处理也并不trivial;
First line:
if 2 target points are still bigger than 2 starting point, we reduce target points.Second line:
check if we reduce target points to (x, y+kx) or (x+ky, y)Time complexity
I will say O(logN) where N = max(tx,ty).
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
while (sx<tx && sy<ty) if (tx<ty) ty%=tx; else tx%=ty;
return sx==tx && (ty-sy)%sx==0 || sy==ty && (tx-sx)%sy==0;
}
这个代码逻辑写的更加简单; 感觉这帮人分析起来都一套一套的, 但是我认为这个题目的算法的一个核心问题是, 怎么知道写这个while的header: 要求x和y都同向; 我自己写的算法里面就因为我没有意识到如果x, y不同向就没有必要继续判断, 导致最后代码非常的冗杂;
另外, mod的复杂度好像是digit/bit的数量, 所以是log;
class Solution {
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
if (sx == tx && sy == ty) {
return true;
} else if (tx == ty || sx > tx || sy > ty) {
return false;
} else if (tx > ty) {
int subtract = Math.max(1, (tx - sx)/ty);
return reachingPoints(sx, sy, tx - subtract * ty, ty);
} else {
int subtract = Math.max(1, (ty - sy)/tx);
return reachingPoints(sx, sy, tx, ty - subtract * tx);
}
}
}
用除法来写也是衣一个比较不错的思路; recursion写法不难理解;
We can solve this problem recursively from tx and ty.
In each recursive call, if tx > ty, it should derive from (tx % ty, ty), otherwise, from (tx, ty % tx) because the bigger one must come from last transformation from (tx - ty, ty) or (tx, ty - tx) until it is less than the smaller number.
We only need to care about the situation where (sx, sy) transforms to (sx + n sy, sy) or (sx, sy + m sx) in the first time because sx > sy is not the result of (sx % sy + m sy). Hence, if sx > sy, (sx + n sy) % sy will give a smaller number which is wrong.
这个人从base case的角度来分析了为什么需要保持同向;
class Solution {
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
if (sx > tx || sy > ty) return false;
if (sx == tx && (ty - sy) % sx == 0) return true;
if (sy == ty && (tx - sx) % sy == 0) return true;
return reachingPoints(sx, sy, tx % ty, ty % tx);
}
}
submission没有;
Problem Description
A move consists of taking a point (x, y) and transforming it to either (x, x+y) or (x+y, y).
Given a starting point (sx, sy) and a target point (tx, ty), return True if and only if a sequence of moves exists to transform the point (sx, sy) to (tx, ty). Otherwise, return False.
Examples:
Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: True
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)
Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: False
Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: True
Note:
- sx, sy, tx, ty will all be integers in the range [1, 10^9].
Difficulty:Hard
Total Accepted:1.2K
Total Submissions:6.4K
Contributor:awice