yeputons's blog

By yeputons, 5 years ago, In English,

Hello everyone.

Right now I'm settings up APIO 2011 contest for training purposes. It seems to me like test data (answers, to be precise) in problems 'Guess My Word' and 'Table Coloring' are broken. I have three solutions from three different people for the latter problem and they produce the same answers for tests 10, 12, 14, 16 and 18 — zero, while the reference answer is non-zero. For the 'Guess my Word' problem I have two solutions: one fast and one brute-force with memoization which I wrote by myself several minutes ago. These two solutions produce same output on tests 1-16, but they both produce 'No' on some test cases where official test data says 'Yes'.

Does anyone have information about validity of this test data or some solutions which I can test with too?

Thank you.

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

..answers, to be precise?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Yep, thank you. I think it's better to report such mistypos and misspellings via PM (personal messages), because this information becomes outdated very fast.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yep, that would've been better :) (Actually, I was embarrassed to PM for such silly thing... :s)

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Checked mine and outputs for test 10, 12, 14, 16, 18 are all zeroes (downloaded a couple of weeks after the contest ended). Do you want to take a look at it?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, sure. Would you mind sharing your solutions and/or downloaded archive?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      This is my test data. I coded 2 of them in the past but can't find the codes on my laptop at the moment.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It looks completely the same as mine, except the fact that in your data answers to tests I mentioned (in problem 'color') were replaced by zeros and the archive itself has another format — several folders with two files (stdin and answer) in each of them, while another archives contain 20 files *.in and 20 files *.out without any wrapping.

        Thank you! If you could find your solutions too it'd be great.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can try your solution of 'Table Coloring' here.

The 'Hint' section on the above page said test data was fixed by sevenkplus, it is possible offical datas are broken.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you!

    Isn't there similar note on this page for problem 'guess'? My 'naive bruteforce' still gets wrong answer.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      For 'guess' the note just said test data is 'national + international merged', but not patched.

      Notes on 'national': Chinese staff generate some tests by themselves during APIO, and give some (national) awards based on judge results of their unofficial data.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The test data for the problem 'Table Coloring' from the actual contest was found to be incorrect and a corrected archive was sent out to team leaders some time later, however the actual test data on the website was only updated very recently (due to this post).

There were no similar notices for 'Guess My Word', but since very few people have attempted the problem, it may be the case that the errors are yet still undiscovered.

I do have an unverified solution that passes the official tests. If you send me your solutions or output, I can take a look.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Here are some solutions:

    1. Link, full score.
    2. Link, brute-force solution, 20 points in our system.
    3. Link, brute-force with memoization, 80 points.
    4. Link, another full score.

    All of them are considered correct (no 'Wrong Answer)', but second and third are slow.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hi there, any luck with that?

»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

problem Guess My Word

I have spent several days and find official test cases says Yes as soon as the characters under the line is n+1 no matter if there is a valid word last..(original problem test cases)

but on bzoj : https://www.lydsy.com/JudgeOnline/problem.php?id=2305 some one has added 10 another stronger tests for these 10 cases(C==20 for all of them,original tests there is no tests C==20).it says No when characters under the line is n+1 if there is no valid word last. I got AC by write two kind of reading comprehensions for these two kind of test cases