szawinis's blog

Output-only tasks
By szawinis, history, 6 years ago, In English

Output-only tasks have become quite popular in the OI scene, although less so than interactive tasks. Sometimes, a good score on such tasks is crucial in determining which medal you get (take IOI 2017 Nowruz, for example). How does one prepare to face such tasks? Is it recommended to learn evolutionary algorithms, ML, etc? I found it very difficult to find nice, clean implementations of them that can be modified to suit each problem.

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

»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Output-only tasks are often constructive problems which are NP-Complete. I'll describe how I usually deal with them.

For small inputs, you can usually solve them by hand. This will give you a better understanding.

Then you may want to find whether there are any special properties for each input (for instance, whether the given graph is a tree). You may write codes for special inputs.

For general cases, a smart brute-force or randomized program may be needed. I would recommend Simulated Annealing to deal with some problems. You need to make sure that your program finishes before the contest ends.

I'm not really good at solving these tasks (but I'm not bad at them either :). Hope this helps.

P.S. I've heard that a randomized program with BFS would get 80-90pts for IOI 2017 nowruz.

→ Reply