Disclaimer: I didn't actually sit this contest live because the alarm I set for 3.30 am (time it started) didn't go off (zzz) and I woke up the next morning both disappointed but happy I got more than 2 hours of sleep.
Imagine a flat line (practically a number line, think one where you learn integer addition on) and Z beginning at 0.
Z may move left, L, changing his position by -1.
Z may move right, R, changing his position by +1.
Line 2 is a string, the string of commands M gives to Z.
For example: LRRL, RRLLR, LLLLL, RRRRL
The catch is that not all of these commands may be executed and i commands can be ignored, 0 <= i <= n.
E.g
LRRL == RRLL == LLRR == LRLR == 0
This is easily proved by replacing L with -1 and R with +1, with the final sum of the changes in position being the final position. As addition is commutative, order does not matter.
(-1) + 1 + 1 + (-1) = 0
Then as we rearrange the actions to have the L's sorted to the left and the R's on the right, the solution begins to look clear.
LLRR
Suppose all L's were ignored, then our final actions would be: RR (+2)
Suppose all R's were ignored, then our final actions would be: LL (-2)
Suppose all L's AND R's (all actions) were ignored, then we would remain at 0.
Hence our range of possible locations Z ends at is: -2 <= i <= +2
And generalised: (-1)*number of L's <= i <= (1)*number of R's
So therefore, if we include 0 (as Z can end up at the start), then the number of possible places he may end up at is:
number of L's + number of R's + 1
The 1 being position 0 possibility.
The question reinterpreted:
We are given a character, Zoma (Z), who recieves commands from Mezo (M).Imagine a flat line (practically a number line, think one where you learn integer addition on) and Z beginning at 0.
Z may move left, L, changing his position by -1.
Z may move right, R, changing his position by +1.
Input:
Line 1 is an integer, I will denote by N.Line 2 is a string, the string of commands M gives to Z.
For example: LRRL, RRLLR, LLLLL, RRRRL
The catch is that not all of these commands may be executed and i commands can be ignored, 0 <= i <= n.
Solving the problem:
Notice that the order of the actions Z executes for each particular case does not matter, and does not determine his final end point.E.g
LRRL == RRLL == LLRR == LRLR == 0
This is easily proved by replacing L with -1 and R with +1, with the final sum of the changes in position being the final position. As addition is commutative, order does not matter.
(-1) + 1 + 1 + (-1) = 0
Then as we rearrange the actions to have the L's sorted to the left and the R's on the right, the solution begins to look clear.
LLRR
Suppose all L's were ignored, then our final actions would be: RR (+2)
Suppose all R's were ignored, then our final actions would be: LL (-2)
Suppose all L's AND R's (all actions) were ignored, then we would remain at 0.
Hence our range of possible locations Z ends at is: -2 <= i <= +2
And generalised: (-1)*number of L's <= i <= (1)*number of R's
So therefore, if we include 0 (as Z can end up at the start), then the number of possible places he may end up at is:
number of L's + number of R's + 1
The 1 being position 0 possibility.
Comments
Post a Comment