Generating string with n non-repeatable subsequences

Question

1.00/5 (1 vote)

See more:

The task is to write a program, which for every given natural number n will generate not so long text made of not so big number of signs, which has exactly n different subsequences. But remember that subsequence with 0-length is also the subsequence. We consider subsequences to be different if their text is different. For instance sequence "ioi" has seven subsequences (i,o,ii,io,oii,ioi and empty subsequence).

I have no idea, how to start biting this.
Does anyone have an idea how to solve it?

Thank in advance

What I have tried:

I've already tried to determine some kind of relation between the number of subsequences and a number of appearances of each letter, I also tried to do a brute force solution, but finally, everything, which seemed to work didn't have any sense.

Posted 2-Nov-18 3:12am

Member 14041718

Updated 11-Aug-22 6:55am

Add a Solution

2 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

KarstenK · Answer 1 · 2018-11-02T03:40:00

You have to create subsequences which you may create, need to compare, so you need a class SubSequence or Sequence which has an "equal" function. This "equal" function may be something like:

C++

bool operator==(const SubSequence &op)
bool isSubsequence(SubSequence *seq);//some test if seq is in object
//other functions
SubSequence(string text);//create instance
SubSequence* allSubsequences();//function which returns an array of all subsequence

Tip: even if not all works some parts will do, and you get hopefully enough points ;-)

Member 14042680 · Answer 2 · 2018-11-03T07:04:00

Solution 2

This is a problem from an ongoing competition (https://sio2.mimuw.edu.pl/c/oi26-1/p/pod/). Please do not answer this question until November 13.

Posted 3-Nov-18 7:04am

Member 14042680

Generating string with n non-repeatable subsequences

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Generating string with n non-repeatable subsequences

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us