Блог пользователя L_Wave

Автор L_Wave, история, 3 месяца назад, По-английски

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 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.

  • Проголосовать: нравится
  • +41
  • Проголосовать: не нравится

»
3 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

GlebsHP is inactive for 8 months , Lol

»
3 месяца назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

It is written in the editorial, it is option 2.