Problem 141 description
Back to Problem Solutions forum
It seems to be wrong implementation of described algorithm.
If we use the example from description we have to pick the nearest find result in block:
an 20-2
d_ 10-2
he to 58-5
l 19-1
d_ 7-2
u 0-0
So the answer should be '2014 200A 503A 1013 2007 0000'.
But the checker accept another solution - we have to use the first find result from the very beginning of block:
an 20-2
d_ 27-2
he to 58-5
l 38-1
d_ 35-2
u 0-0
So the answer is '2014 201B 503A 1026 2023 0000'.
in the town where i was born live[d ]a man who saile[d ]to sea
^ ^
27-2 10-2
an[d ]he told us of his life in a land of submarines
^ `
substring
P.S. Sorry for my terrible English. My native language is C++.
Oh, you are right - it is my mistake that checker searches from the wrong side.
I'm going to change its behaviour now - could you please do me a favor and test it once more?
I've added the line to problem statement:
If more than one prefix of the same length could be found, please choose the smallest offset.
UPD: I've updated the "example" at the bottom also.
I think that I missed something.
I got this as test-cases:
40
22255 22947 36587 9700 31780 21915 4676 25611 34708 13155 7630 46121 20855
And I don’t know what length has to be tested.
OMG, I'm extremely stupid today, I'm sorry. These awkward data appeared because after changing the checker I tested it myself and saved with predefined test data. %)
I'm quite sorry! Hope this is fixed now...
I still don’t know what length has to be tried: why not 1, the only letter encountered at the given position? Is it the string "and he told "?
You have to find the best length between 1 and 15 (encoded as 1..F in the result). Once you find a letter that matches, check if the next one matches the second one from your original position. Then a 3rd and so on.
Nicolas and Serge - thanks for pointing this out - I'll try to improve the problem statement now!
The offset should be calculated from Pi of from the position of the matching string? Does the "\n" count?
Actually, I find a longer match (7) for the first test case (22255) that is line 534 and the match is line 456.
You can only go back 4096 bytes from the search position (since you only have 3 hex bytes to encode the distance 000..FFF)
Hi! I'm sorry for being slow to answer.
Let's see. The file have substring kable, save that at position 22255. The answer given in the example refers to offset 215 (i.e. position 22039) - here is a single letter k.
>3498 bytes before 22255.
This places us somewhere at 18757 - here are words have that photograph - nothing like the substring we are searching for.
Probably it is worth checking that you did not convert file somehow (for example substituting CRLF with single LFs while reading or something like this). Hope this may help...
I see "ave that ".
Ha, the substring must begin like the other one? OK, the second problem bring the answer.
Got it but there is still a bug in my code somewhere.
Ah, thanks for explaining the cause of bewilderment! Seems I should add explanation of example to the problem statement!
The byte string has to contain '\r'. So if you are using linux machine make sure you replace '\n' with '\r\n'