All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Leaving a maximal result (Posted on 2017-08-25) Difficulty: 3 of 5
Imagine a concatenation of first 100 positive integers i.e. 12345678910111213...979899100.

You are given a task to erase 96 digits of your choice, without changing the original order, then shrink the final sequence to eliminate blank spaces, striving to achieve largest possible result.

What is this maximal value and how was it derived?

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution algorithm Comment 1 of 1
The initial concatenation is 9 + 2*90 + 3 = 192 digits long, so erasing 96 will leave 96 as well.

At each point as we proceed from left to right we need to keep track of how many of the remaining digits we need to keep. For the given digit we are looking at in this sweep, we need to look ahead to see if any digit beyond is both higher than the one we're looking at and, if we wait until we get there to keep that one, there are enough digits remaining to satisfy the number still needed to complete the 96 we need to keep; if there is such a higher number then discard the digits until that number is reached; otherwise keep this one.

When you get to that higher number (if that's the decision made), the same decision procedure must be done again. That is, don't automatically assume this one is good just because it is higher than the one first looked at.

If, however, the decision was to keep the given digit being looked at, do so, subtracting 1 from the number still needed and advance to the next position and continue from there.

The program below follows that procedure and produces the following output:

I split up the original number below, with a row of carets (^) underneath each half to show which digits are kept. Below that is the resulting number that remains.

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525
        ^                   ^                   ^                   ^                   ^^      
354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

999995657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

Note that in this particular case it doesn't really matter that the 5 chosen was the one immediately following the last 9. However, the algorithm is written so that this 5 is chosen so as to allow more choice for subsequent tests, in cases, for example where everything after the given 5 (say) is lower than 5, as in ...54444451111111111111. Depending on how many more are required to be kept, choosing the second 5 instead of the first might (without further code) preclude continuing with the 4's, or actually including both 5's.


DefDbl A-Z
Dim crlf$


Private Sub Form_Load()
 Form1.Visible = True
 
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
 Open "leaving a maximal result.txt" For Output As #2
 
 s$ = ""
 For i = 1 To 100
   s = s + LTrim(Str(i))
 Next
 
 ReDim kept(96)
 ptr = 1: need = 96: keep$ = ""
 Do
   cmp$ = Mid(s, ptr, 1)
   found = 0
   For i = ptr + 1 To Len(s) + 1 - need
     If Mid(s, i, 1) > cmp Then
       ptr = i
       found = 1
       Exit For
     End If
   Next
   If found = 0 Then
     keep = keep + cmp$
     need = need - 1
     kept(Len(keep)) = ptr
     ptr = ptr + 1
   End If
 Loop Until need = 0
 
 Text1.Text = Text1.Text & s & crlf
 Print #2, s
 prev = 0
 For i = 1 To 96
   Text1.Text = Text1.Text & Space(kept(i) - prev - 1) & "^"
   Print #2, Space(kept(i) - prev - 1) + "^";
   prev = kept(i)
 Next
 Text1.Text = Text1.Text & crlf & keep & crlf
 Print #2,
 Print #2, keep
 
 Text1.Text = Text1.Text & crlf & " done"
 
 Close 2
  
End Sub


  Posted by Charlie on 2017-08-25 10:47:40
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information