USACO 2023 January Platinum Problem 2 — Possible implementation issue in model solution?

Правка en6, от alexlikemath007, 2023-03-16 09:03:45

The Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=1285

The Editorial: http://www.usaco.org/current/data/sol_prob2_platinum_jan23.html

I was stress testing against the model solution, and I think I found an error in the provided solution.

I ran this test case on the model solution as shown in the editorial:

3 6
4 6 4 
1 2 3
1 3 3
2 1 1
2 3 2
3 1 3
3 2 2
10
1 3
8 1
1 2
8 1
3 3
5 2
10 1
8 3
1 2
8 1

It appears to be a valid test case adhering to the problem. However, when ran against the solution, I got a runtime error. The following was printed to standard error.

Assertion failed: (a.f > b.f) && (a.s < b.s), file d:/C++ programs/usaco/jan/B/brute.cpp, line 36

However, the correct answer to the test case is:

4
94
6
94
18
42
122
80
6
94

Needless to say, I don't think this is correct.

Can the USACO staff please investigate this?

Edit: I have another test case which doesn't set off the assert, but sometimes gives either 7 (WA) or 12 (AC). (Perhaps it depends on the version of C++?), which means that the model solution also exhibits some strange undefined behavior.

3 6
6 6 5 
1 2 2
1 3 3
2 1 2
2 3 1
3 1 1
3 2 2
1
2 2

Edit 2:

I believe there may be a typo which caused that: On line 39, the model written:

    ll addOne = ((addOne%slopeDif)==0)?1:0;

When it should be

    ll addOne = ((addDif%slopeDif)==0)?1:0;

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский alexlikemath007 2023-03-16 09:03:45 236 The bug?
en5 Английский alexlikemath007 2023-03-16 08:36:34 325 another test case?
en4 Английский alexlikemath007 2023-03-16 08:08:08 9 more specific
en3 Английский alexlikemath007 2023-03-16 07:53:15 1 minor typo (again) (published)
en2 Английский alexlikemath007 2023-03-16 07:52:15 4 minor typo (saved to drafts)
en1 Английский alexlikemath007 2023-03-16 07:50:26 1040 Initial revision (published)