Click here to Skip to main content
15,936,850 members
Please Sign up or sign in to vote.
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
Updated 11-Aug-22 6:55am

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 ;-)
 
Share this answer
 
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.
 
Share this answer
 

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900