|
|
| Show all threads Hide all threads Show all messages Hide all messages | | Strange statement | 🦄imosk72🦄[GTGU] | 2181. Student, or There and Back Again | 9 Mar 2025 16:50 | 1 | > The student’s home is located at the coordinates (1, 1), and the university is at the coordinates (N, M).
It means, for example, if N == 1 && M == 1 then university have same coordinates as home. Of course we can not use any roads in such case. But according to the sentence:
> There are a total of N streets running from north to south and M streets running from west to east.
there are some roads that can not be used. I think there should be N - 1 streets running from north to south and M - 1 streets running from west to east. | | Wrong tests? | andreyDagger`~ | 2181. Student, or There and Back Again | 28 Jan 2025 19:01 | 6 | It seems like in test 7 n=300, m=300, k=0. Answer is obviously 709227659, but it gives WA. I also got answer 709227659 to this testcase. Yes, seems like incorrect tests or incorrect problem statement. Admins, please look at this issue. At least please check test 7. Also please, clarify order of N and M values in input data (if they go in M,N order then correct statement please). P.S. Also the problem is not so difficult as described in post-contest jury solutions. If problem statement is correct, it has got simple O(N*M) dp solution (based on https://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma principle). Yeah, jury solution is complicated. Mine solution is a bit different, but still straightforward O(N*M*(N+M)) dp, with simple O(1) transitions from each state Admins, any decision about this problem?
Is test 7 correct? We fixed wrong tests. Original author miswrote 10^9+7 as 10000007 in his code, that generated incorrect tests. We sincerely apologize for such an error
Edited by author 28.01.2025 02:06 Thanks a lot for solving the issue! Also, what about the original contest results ? ( https://timus.online/monitor.aspx?id=1568 ) Anybody now with correct tests has AC for problem M ? (suppose that such tests were on this contest too). Edited by author 28.01.2025 19:43 |
|
|
|
