Weak testcases in problem 1038E

Правка en2, от Be_dos, 2021-02-11 18:12:40

Hello Codeforces!

Today I was solving 1038E - Maximum Matching during practice. I made submission 107130992. To my big surprise, it got AC with time 951 ms (less than half of TL). However, I have an easy-to-generate test which makes it work around 3000 ms! This indicates that the testcases are extremely weak.

The test is very simple: we can just distribute the 100 blocks evenly between all 6 kinds of pairs with distinct elements.

It's also interesting that it is possible to make that submission work fast enough even on that test (see 107131735). This means that one can wrongly get AC while being on the right track.

I know that this is quite an old problem. However, it might still be worth to throw in a few more tests so that submissions like my first one do get TLE in the future.

Tagging the problem author: Ashishgup

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Be_dos 2021-02-11 18:12:40 50 (published)
en1 Английский Be_dos 2021-02-11 18:08:24 904 Initial revision (saved to drafts)