About 1804F: Curious about the problem's checker&generator

Revision en4, by L_Wave, 2024-09-14 16:18:11

I solved 1804F recently. It was a cute problem! But what made me curious was how the checker and generator works. It is clear that the $$$d(G)$$$ in the problem cannot be calculated by the checker every time when judging a submission, or the checker would a TLE.

So there are extra lines in the input. They must be encoded and used to determine every $$$d(G)$$$. I guess that the checker&generator would work as one of the following two ways:

Method 1

  • Determine every $$$d(G)$$$ in the beginning.
  • Generate a graph satisfying the $$$d(G)$$$ constraint.
  • Encode $$$d(G)$$$ and print them into the input.

Method 2

  • Generate a graph randomly, and use brute force to calculate $$$d(G)$$$. If there is a way in $$$O(qn\text{polylog}n)$$$, it will cost only about $$$500s$$$ for every test case.
  • Encode $$$d(G)$$$ and print them into the input.

For the checker, just read the encoded $$$d(G)$$$ from the input and decode them.

But for either of them I don't know the details (how to generate a graph according to $$$d(G)$$$, how the brute force works, ...). Anyone can explain to me? Maybe I should mention the author GlebsHP.

Tags checker, generator, 1804f

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English L_Wave 2024-09-14 16:20:51 2 Tiny change: 'ker would a TLE.\n\nS' -> 'ker would TLE.\n\nS'
en4 English L_Wave 2024-09-14 16:18:11 47 (published)
en3 English L_Wave 2024-09-14 16:17:29 81
en2 English L_Wave 2024-09-14 16:16:35 16 Tiny change: 'ssion, or it would give a TLE.\n\' -> 'ssion, or the checker would a TLE.\n\'
en1 English L_Wave 2024-09-14 16:16:13 1110 Initial revision (saved to drafts)