Why am I getting stack overflow? + Weird Java behavior + Custom invocation differs from Judge
Difference between en1 and en2, changed 2,401 character(s)
[submission:102615607] gets stack overflow but runs fine locally. I'm generating input according to [this comment](https://mirror.codeforces.com/blog/entry/86004?#comment-737940) ([user:bleddest,2020-12-28] correct me if I'm wrong), and I'm using vm arguments `-Xmx1024m -Xmss64m`, as suggested by the memory limit and [this blog](https://mirror.codeforces.com/blog/entry/79). Just in case testcase 50 was generated differently, I also tried generating input using n = 1e8 which worked fine, albeit taking 150 seconds and requiring a lot more memory. So now I am somewhat confused: Why am I getting stack overflow?↵

<spoiler summary="Input generation">↵
```java ↵
private String generateInput() {↵
StringBuilder ans = new StringBuilder();↵
ans.append("1").append("\n");↵
int n = (int) 1e8, k = 100000;↵
ans.append(n).append(" ").append(k).append("\n");↵
BigInteger bi = new BigInteger("1".repeat(k), 2);↵
for(int i = 0; i<n; i += k) {↵
ans.append(bi.toString(2));↵
bi = bi.subtract(BigInteger.ONE);↵
}↵
return ans.toString();↵
}↵
```↵
</spoiler>↵

**Edit:** Things take an interesting turn... <br>↵
For the past ~6 months, I've always been setting the stack size to a large amount in order to avoid stack overflow [javadoc](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Thread.html#%3Cinit%3E%28java.lang.ThreadGroup,java.lang.Runnable,java.lang.String,long%29). The behavior of the method had always been consistent, and it worked fine for a long time. However, the behavior changed **during** the last contest. [submission:102588854] was fine, but [submission:102610828] 40 minutes later gave MLE on test 1. I changed the stack size from `1<<28` to `1<<27`, which fixed the problem for [submission:102611202] and [submission:102612993]. However, [submission:102615154] which was submitted only 5 minutes later gave an unexpected MLE on test 6, which is quite strange, considering it had previously worked fine for 5 tests.↵

Now it seems that `1<<27` is fine again [submission:102660282]. However, it gives a strange error message, leading me to suspect there's an issue with the grader. I then tried setting the stack size to `1<<29`, which gave an unsurprising MLE on test 1 [submission:102714946]. What particularly interests me is that setting the stack size to `1<<29` works fine on custom invocation. In addition, [submission:102660282] also works on custom invocation (once again, assuming that the testcase is generated according to BledDest's comment). I think this strange behavior calls for some investigation [user:MikeMirzayanov,2020-12-29]? Although JavaDoc doesn't make any guarantees to the method, I think it should remain fairly consistent, especially during contests. In addition, custom invocation should produce the same results as the grader, since the whole point of it is to simulate the grader.↵

<spoiler summary="Faster input generation for TC 53">↵
```java ↵
private String generateInput() {↵
StringBuilder ans = new StringBuilder();↵
ans.append("1").append("\n");↵
int n = (int) 1e6, k = 500000;↵
char[] arr = new char[k];↵
Arrays.fill(arr, '1');↵
ans.append(n).append(" ").append(k).append("\n");↵
for(int i = 0; i<n; i += k) {↵
ans.append(arr);↵
int j = k-1;↵
for(; arr[j]=='0'; j--) {↵
arr[j] = '1';↵
}↵
arr[j] = '0';↵
}↵
return ans.toString();↵
}↵
```↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English skittles1412 2020-12-29 22:00:55 2401
en1 English skittles1412 2020-12-28 21:34:29 1101 Initial revision (published)