Sort of output only problems

Revision en5, by geniucos, 2016-11-02 13:52:50

Hello, everybody!

I'm writing this entry for asking for your help. It is a special kind of task, that I like the most and, however, I can't say am very good at. I'm talking about output only problems, or tasks similar to them, or some sort of puzzle tasks. I'm talking generally about tasks that require generating something (maybe an array or a matrix) as a input to a source that is given in the statement explicitly or implicitly (maybe they don't give you the source but they want the number of pairs of indices with who-know-what property to be large or small) to generate a number as high or as low as possible (not necessarily minimum or maximum). The worst is that I don't have any example to give at the moment (I don't exactly remember any such problem or where to find it). I'll try to give a short example (not necessarily solvable): Generate an array with N numbers smaller or equal than M so that the number of values that can be obtained by summing some of the initial values (each can be used at most one time) to be as large as possible. And I want a solution to generate for N = 10 and M = 100 a set whose size will be 500 (this may be an output only problem), or I am simply giving you N and M as input and the scoring is computed someway to let a strategy get 100 points (it's not an optimization task like codechef long challenge ones). Something like if you get a size of NlogM you get 100 or who knows.

I'd also like to include in this category the problems that ask for generating something with a certain property (like paving a matrix with some sort of puzzle pieces for example). These two types of problems are not that linked, but both of them require constructing of something.

One more important thing: I want the problems to be solvable by determinist algorithms or proved probabilistical solutions. Also, I don't ask for you to know their solution, even though that would help, but just for the problems and after a while I hope I'll get them done, or if not, I think I'll ask either here in the comments or in some separate post.

As generating a covering of someway of something, I have a link to a problem in Romanian that asks for paving a matrix whose corners are cut, with L shape pieces. Even though the statement is in Romanian, you can check the sample to see what it's asking for.

LE: I remember one of the problems I was talking about. It is almost what I wanted to say through this post, but the best representative of this category, I guess, is the one mentioned by Um_Nik

#### History

Revisions

Rev. Lang. By When Δ Comment