"run code" gives false, and "submit" gives either true or false.
I think it's a broken testcase; it is not even a "simple polygon" As far as I understood.
Leo Lai
@leo.lai.944
enthusiastic C++ programmer.
performanceaware design specialty.
Posts made by leo.lai.944

RE: Why is this case a convex?

stress test on OJ's testcase suite
Recently I reviewed this problem and I tried a buggy solution, and it passes OJ. The corner case reminds me of taking any possible troubles into account and not assuming your program to be always true, so I wanna share with you guys:
string toString(int lo, int hi) { char tmp[25];//11 for lo, 11 or hi, 2 for ">", 1 for zerotermination if(lo == hi) sprintf(tmp,"%d",lo); else sprintf(tmp,"%d>%d",lo,hi); return tmp; } vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) { if(nums.empty())return {toString(lower,upper)}; vector<string> ret; for(int i=0;i<nums.size();++i) { if(i!=0) { if(nums[i] > nums[i1]+1) { //> suffer from overflows ret.emplace_back(toString(nums[i1]+1,nums[i]1)); } } else { if(nums[i] != lower) { ret.emplace_back(toString(lower,nums[i]1)); } } } if(upper != nums.back())ret.emplace_back(toString(nums.back()+1,upper)); return ret; }
This solution use the statement
if(nums[i] > nums[i1]+1)
to test missing ranges, but when it comes to nums[i1] also to be INT_MAX, the code is screwed up. Let's try this testcase.[2147483648,2147483648,0,2147483647,2147483647] 2147483648 2147483647
And you got
["2147483647>1","1>2147483646","2147483648>2147483646"]
Likewise,
if(nums[i]1 > nums[i1])
causes problems on the other side of integer boundary.So what's the solution? I proposed this one:
if(nums[i] != nums[i1] && nums[i] != nums[i1]+1)
. When there are 2 consecutive identical numbers, the test filtered the corner case first.Just for the record, I think current OJ's testcase suite is pretty awesome; it tests lost of situations, like consecutive numbers, duplicates, extreme values. Thanks the author's effort to push me to think so many corner cases.

[testcase too weak] Abviously wrong solution passes the judge
bool searchMatrix(vector<vector<int>>& matrix, int target) { for(int i=0, j = matrix[0].size();i<matrix.size();++i) { auto it = lower_bound(matrix[i].begin(), matrix[i].begin()+j,target); if(it == matrix[i].begin()+j) continue; if(*it == target)return true; j = it  matrix[i].begin(); } return false; }
this solution fails against this test case:
[[1,1000,1000,1000],[2,3,4,5],[3,10,11,12]]
11
But it passes OJ.

RE: [testcase too weak] Some shared binary search solutions are buggy.
@MarathonRush the solution I posted still passes OJ.
And yes, upper bound can be initialized as sqrt(INT_MAX), but you cannot use builtin sqrt(x), so you have to do some pencil&paper work to know that. 
RE: share my fast C++ solution using std::map (99~100%, 40+ ms)
@simonwoo Thanks for letting me know.
I think what is wrong is the testcase, not my solution, which I have pointed out. so please check my new post:
https://discuss.leetcode.com/topic/69785/newtestcasesareinconsistentwithproblemconstraint

New testcases are inconsistent with problem constraint?
This is the start of the problem description:
"Given an m x n matrix of positive integers..."
and at the ends it said that again:
"The height of each unit cell is greater than 0 and is less than 20,000"And a new testcase is:
[9,9,9,9,9,9,8,9,9,9,9],[9,0,0,0,0,0,1,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,9,9,9,9,9,9,9,9,9,9]]
Am I missing anything?

[testcase too weak] Some shared binary search solutions are buggy.
(Not sure if anyone brought this up before, though)
The code like this is pretty common in some solution sharing and also passes judge, but it is actually buggy:bool isPerfectSquare(int num) { if(num<=0) return !num; int lo = 1, hi = num; while(lo <= hi) { auto mid = lo + (hilo)/2; if(mid*mid == num) return true; // do you see the problem??? if(num/mid < mid) hi = mid1; else lo = mid+1; } return false; }
The code like this doesn't take overflow into consideration; try to run the code with input
131073
, and you will see the mismatch.2 ways to solve the issue. One is to use
long long
instead of justint
:long long lo=1, hi = num;
This is not a general solution; which is not gonna work if the problem input is
long long
already.The second one is to change the first
if
statement like this:if(num/mid == mid && num % mid == 0) return true;//C++03 paragraph 5.6 clause 4
Maybe I'm too picky? But I don't think 7~8 incorrect result per million integers is a reliable code.

RE: Simple 16 ms,10 line C++ solution. 1.use new bool array 2. only traverse odd numbers 3.count and sieve at the same time
@qeatzy your array is not even initialized.

RE: Simple Solution : onepass, using only array (C++ 92ms, Java 16ms)
@coder2 Thanks for your reply.
It is actually not 'visited', more like 'verified' or "matched", though it is still not really precise either.
Before I gives a explanation, define
the predecessor of x
for an integerx
is the integer right "left" tox
int he problem inputorg
.
(If you know Java, it meansorg.indexOf(x)
==org.indexOf(predecessor of x) + 1
).(Despite of the data type I uses, I stored only Boolean values in there.)
An Boolean valueflags[x]
istrue
if and only if the integerx
and its predecessor are also in appearance in a certain given subsequence adjacently with the same relative position (i.e. the order is alsopredeccessor then x
).The naming also bothers me; I cannot figure out a precise name for such a complicated meanings so I decides to leave an extremely meaningless name for it so that everyone knows I don't know how to name it LOL.
Do you have any suggestion? Thanks.

RE: Simple Solution : onepass, using only array (C++ 92ms, Java 16ms)
@jeffery Sorry for late reply and thanks for your questions.
I am not really confident to give a purely formal proof because Im not really a good speaker, but I will try to show some examples and let you know how I think.
There are 3 things needed for full proof:
 All characters in the supersequence form the same set of all characters in all subsequences.
 the order relation, i.e. "Which characters a character should be placed after," is a transitive relation. (see https://en.wikipedia.org/wiki/Transitive_relation) You can think this property of the fact " a dependency graph is a directed acylic graph.". This property also guarantees that evey given subsequence is really a legal one of the given supersequence.
 the supersequence is unique "if and only if" every two adjacent elements in the supersequence also appears adjacently in a certain subsequence.
Because I'm not a native English writer, I am gonna skip 1. and 2. and leave them to better resources:
Leetcode OJ problem algorithm 207: https://leetcode.com/problems/courseschedule/
Leetcode OJ problem algorithm 210: https://leetcode.com/problems/coursescheduleii/So, let's assume property 1. and 2. stand, and let's start with an subsequence example:
ab, ac, bc,
And we can establish a dependency graph with 3 vertices a,b,c and three edges b>a, c>b, c>a.Note that I put the element with higher order near the graph source and lower order near the graph sink.
When we do the postorder traversal, the sequence can determine a legal order relation.(please check the OJ problem listed above for correctness of this statement.)
Now we can talk about "IF" part, with a longer example
abcde....z
:
Because all adjacent pairs in the supersequence also appears in a certain subsequence, you will get something like this:
a<b<c<d<e......z.
Oh, yes: there might be some other edges, like a<e, b<z....etc. BUT, no matter how many other edges are there,a
is guaranteed the lowest(i.e. the first) element in postorder traversal. Now recorda
, removea
and all its inedges, and we reduce it to a subproblem like this
b<c<d<e......z
.
So now you still have the one and only one lowest element; by proceeding the postorder traversal, you have an unique result:abcde.......z
."Only if" part:
Suppose the dependency graph looks like this:
a b<c<d<e......z
, andabcde.....z
is still a legal relation. However you can always find a way to traverseb
first beforea
and produce another legal sequence, making the supersequence loses uniqueness. What if the broken link appears in the middle instead of tail? Proceed the postorder traversal described in "IF" part and you will pull the broken link to tail eventually.Hope this can help you think.