Sort of output only problems

Revision en3, by geniucos, 2016-11-01 18:22:21

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.

I especially like these sort of tasks and I want to train to become able to solve more of them. But they are hard to find (usually because such problems have a very big variety of scores and wouldn't be good as ACM tasks and most of the competitive programming resources that I know are targeting ACM training, and also because, as you can see, I don't know what is their generic name, so I can't google it or even see wheter there is already such a topic). So I wanted to ask: do you know where to find such tasks? Every single link may help. I also hope that I'm not the only one who appreciate such tasks, so that the topic will not be helpful just for me. As soon as I remember those problems of this kind that I've seen, I'll edit the post and add some links.

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

History

Revisions

Rev. Lang. By When Δ Comment