geniucos's blog

By geniucos, history, 8 years ago, In English

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

Thanks in advance!

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by geniucos (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I remember there were several such problems on IPSC, although they are more of entertainment purpose than classical ACM.

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Aren't these the problems with the constructive algorithms tag?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Oh shit, yeah I forgot about that name. Still, most of them are asking you for achieving something with some moves (which is included in the kind I've talked about, but it still remains the category in which you have to build something with a very low or large cost which can't be said to be actually constructive) and some are completely unrelated. But yes, a part of these meet the criteria I was talking about, and there are really a lot. Thanks:)

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Do some IOI problems fit into this? (2012 Artclass, 2010 Maze, 2010 Languages, 2006 Forbidden Subgraph, 2004 Polygon, 2003 Reverse)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    I did IOIs from 2007 to 2016, but I don't find any of the 3 problems that I recognize: artclass, maze and languages in that category. I was talking about deterministic algorithms, as I said different from codechef long challenge ones (like the one problem in a contest that is called challenge and where you need to do some non-deterministic solution which is not proved to have any probability yo work either). Maze was indeed output only (still not enabling you to make a 100 points source that would work on any test up to a limit), but at least it was output-only term that I used in my statement. Still, I will add that, I want to be deterministic solvable. Sorry for misconfusion:( and thanks for the answer anyway:) I'll check out those up to 2006 to see wheter they fit in.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Is it just deterministic or no heuristics allowed?

      Artclass and Languages are technically deterministic, with 100% accuracy achievable with some near-perfect ML algorithm, but there's no strict definition of a valid input, so there's no concept of determinism as "works on all valid inputs". Forbidden Subgraph is also optimisation (AFAIK — there are some limits mentioned in the official solution, but I don't know if they're the best), just not human-based.

      Polygon has a 1/0 scoring per test with a deterministic (albeit slow) solution, it's not an optimisation problem. Reverse is... I dunno, there's no mention of a 100% solution anywhere (even in the official writeup), but the 100% limits are so crazy I think it wasn't intended as an optimisation problem.

      Output-only will usually be output-only precisely because there's no known optimal solution, anyway.

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        Yes, there shouldn't be a known solution to minimize somehting. But there should be some deterministing algortihm that is obtaing always a cost smaller or equal to N(even though not the best). I don't think you could consider machine learning to have 100% accuracy, but I don't know much about that. Still, that is part of AI which has nothing to do with competitive programming, partly because it can't be exaclty defined. The output only problems that I was talking about are just those which have one input given in the statement(not like maze) through some constants(not an array or a matrix). I know that it seems a stupid definition and is hard for me to express it. But I'm talking here about deterministic algorithms which find a solution, not neccesary optimal, but that fits in a fixed range which can be defined based on the input data.

»
8 years ago, # |
  Vote: I like it +29 Vote: I do not like it

You can find a collection of such problems at Project Euler site. Though the problems there also have a specific flavor.

»
8 years ago, # |
  Vote: I like it +38 Vote: I do not like it

There was a problem in OpenCup GP of Japan: Build an nxn binary matrix with at least 1700 '1' such that there is no rectangle with '1' in all corners.

I'm not sure if it is what you're looking for, but try this: http://acm.timus.ru/problem.aspx?space=1&num=2063&locale=en

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Wow, yes this is EXACTLY what I was aking for. I think I have a proved probabilistical idea on the timus one, and I'll think at the japanese for a while. Thank you a lot! Oh, and one more thing: what is OpenCup GP of Japan? The problem seems that nice that makes me wonder if all of them are similar as quality. Also, what is the limit of N for this one and could you please provide a link for it?

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      OpenCup is a series of regular ACM trainings for colleges, competing onsite (usually with every registered college being an onsite location); the contests are named "GP of X" and at least sometimes use recent problemsets (e.g. GP of Europe = CERC problemset a few days after CERC). It's quite popular in Russia. I don't know if they're public at online judges, but I can access past ones at opentrains.snarknews.info, a training aggregator — you need to ask someone for an account (snarknews? maybe some more involved people know whom).

      Are the problems you're looking for "single input" / "single test" problems? (= if there is an input, it may as well be hardwired in the statement instead of given as stdin/file, since solving one is as good as solving anything)

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Well not all of them are single input, but I think that checking a solution for the task mentioned by Um_nik is easy to do and doesn't need any online judge. Also, thanks for the prompt answer:) and didn't you get what style of task I am describing? It's something very similar to constructive algorithms but maybe applied to NP-hard problems for getting a result bounded to a interval of values (as it is the above example, having to obtain 1500 colored cells) I'm asking wheter you got the type or not because you asked if they have a single test-file. Sorry for the confusing definition I tried to enounce it as well as I could in different ways.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Oh, I forgot to mention: n should be not greater than 150.

      OpenCup is a series of contests held by snarknews. I don't know is there any information about it in English, here is site in Russian: opencup.ru

      I tried to find statements of previous rounds but didn't succeed.

»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Here is a task from recent contest.

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

TopCoder recently had a lot of constructive tasks like "construct a DAG with k extensions to linear order", "construct a formula from implications and parentheses with k valuations so that it evaluates to true", "construct a graph with k cliques as subgraphs". However exact constraints are important, so better look them up.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you, I'll read the recent tasks. I was going to do it even if they weren't this type(because topcoder has very cool problems that can learn you a lot of nice things), but I haven't participated recently so I couldn't see that they started to use more problems of this kind.

»
6 years ago, # |
  Vote: I like it -29 Vote: I do not like it

IOI 2017 nowruz

  • »
    »
    6 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I know this was meant as a joke:)). Still it doesn't fit the style: "determinist algorithms or proved probabilistical", "not an optimization task like codechef long challenge ones". Basically these things make the difference between nice tasks and nowruz. Unfortunately, at the time of writing the post I didn't know that problems where you get the input are so common (had never seen one). I was thinking of tasks that don't have an input at all to be output only

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

I am not sure you will like my problem from Serbia OI (actually orignal idea is from Shafaet), but I like to share:

You are given matrix with 0 and 1. You need to place some more 1's in matrix to get as much 0 components as you can ( one component is one lake, with adding 1 you can separate one lake to several smaller — maximize amount of lakes ).

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it possible to do it optimally in polynomial time? If so, I love it:))

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am not sure there is optimal solution, I provide 5 files and competitors should have better result than me(best had 61% of points, that is around 4% smaller amount of lakes than me).

      I see some strategies nearly to optimal, but there is no proof of correctness.

      You can try too :)

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

Problem A NEERC 2010 is one of my favorite constructive algorithms problems.