Help with homework :)

general
, ,
1

Now I have one more homework to do now :). I’m very glad if someone help me :slight_smile:

This problem can be discribed:

The number X is called “Father of Y” if we delete some numbers in X, we have Y.

Having two non-negative numbers. Your task is finding the smallest number that can be called as “father” of two given numbers.

Example:

With input:

111999111 999111999

We must output: 111999111999.

More example:

12345 12341 => Output is: 123415.

Limitation:

Subtask 1: X,Y <= 10^100

Subtask 2: X,Y <= 10^1000

2

@betlista Can you help me :frowning:

3

I wanted to check it first, but I cannot in a job, check yourself if there is also solution - link, but it seems to me, like simple merge problem…

4

But in that problem, We can only solve subtask 1, is there anyway to solve subtask 2?
note: Le Minh Hoang is a very famous teacher in Vietnam :smiley: :smiley:
And in that book I didn’t see any solution :frowning: @betlista

5

Let assume you have all characters in two FIFO structres (q1 and q2).

By simple merge I meant something like:

res = ""
while ( q1 not empty and q2 not empty ) {
    char c1 = q1.top() // get reference on first item
    char c2 = q2.top()
    if ( c1 == c2 )
        res += c1
        q1.poll() // remove from structure
        q2.poll()
    else if ( c1 < c2 )
        res += c1
        q1.poll()
    else
        res += c2
        q1.poll()
}
add all from q1 to res if not empty // only one can be non-empty
add all from q2 to res if not empty
print res
6

@betlista If this test : 24 72. your code will output 2472, but the answer is 724.

7

I thought your question won’t be so easy, but I didn’t see that test case… Hm, is such case I’d try to use largest common subsequence together with this merging (updated) at the end…

8

Can you describe your idea more clearly?