October 24, 2017 TCO17: Analysis of Algorithm Semifinals, Pt. 1

In my previous posts I have barely covered the Algorithm part of the competition, but I have an excuse. The thing is that spectators cannot read the tasks in the arena or anywhere else during the onsite competition. The only source of information about the tasks participants are solving are the monitors with screencast of what each competitor is doing. Some skilled members, like those participating in another semifinal, can manage to read the task statements by looking at these monitors. For me, however, these guys are reading way too fast and all I manage to read is a few first lines of each problem.
Hopefully I got some help from the participants themselves after and during the two semifinals.

The First Semifinal

First of all, the tasks are now available in practice rooms and at the website. The Easy, how they call it, was pretty solvable this time. At least I could understand the solution after kuniavsky answered all my questions on how it works. Let me describe it here.
The 250-pointer was asking you if it is possible to make number t out of number s by applying a sequence of two operations: reverse the order of digits in the current number, or increment the current number by 1. Numbers fit into 64-bits. Additionally, reverse operation cannot be applied if the last digit of the current number is zero.
The solution idea is as follows: first, make the current number as small as possible, and then increment it up to the target number t. The only question that remains is how to determine the smallest possible number that we can make out of the starting number s.
It is clear that you cannot decrease the amount of digits in the current number, because of the requirement for last digit of a number to be rotated must be non-zero. Also, incrementing a number never decreases its amount of digits. Obviously. Another easy case is when the target number t is greater than start number s.
Then how to solve the hard case when the target number t is less than the start number s, and the answer is positive? The competitors were supposed to do the following statement: “you cannot get a number less than 1000[…]002”. Let us say you have a number x. Increment it until you get digit 1 at the end of it. Now add a restriction that we can do something useful only if a number x has one or more non-9 digits, then the number of digits will not increase because of this operation. Now it is clear that you can rotate the number to get most profit out of this digit 1 at the end. Once we have 1 in front, increment the number until you get 2 in front, then increment once again. Rotate. You will receive the 1000[…]002.
I have no proof for the why number cannot be 1000[…]001 or 1000[…]000, but I assume it can be done by contradiction.
Let us consider an example execution where consequential increments are marked with + sign:
98765+ → 99001 → 10099+ → 20001 → 10002.
Try to play with more example executions to get a better idea.

The Second Semifinal

The tasks are available here. Like in the first semifinal, solving of 250-point task was not enough to qualify.
As I mentioned in my previous post, 3 competitors advance out of every semifinal. Thus, in today’s finals we will see xudyh, scott_wu, rng_58, tourist, ikatanic, and bcip.
In order to not make this post too long, I will stop here right now. If you are eager to get the ideas for the second semifinal, watch Petr’s broadcast, and yesterday’s interview with scott_wu.
Thanks for reading and do not miss today’s algo final broadcast at TCO17 main page.