Editorial for CCC '22 J3 - Harp Tuning

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

There is a lot to consider when attempting to solve this problem. The biggest challenge is to break the input into pieces. This is known as tokenizing the input and the pieces are typically called tokens.

Specifically, the first subtask requires breaking a single instruction into a sequence of letters, the character + or -, and the number of turns. The focus of the second subtask is to break the input into different instructions, but each instruction has a simpler form. The third subtask combines these two objectives. The final subtask adds an extra layer of difficulty by allowing the number of turns to be a multi-digit number.

One elegant way to tokenize the input is to iterate through the input character by character while also remembering the last character read. This allows you to recognize when and where one token begins and another token ends. An alternative is to keep track of the current "state" which is an indication of which of the three types of token is currently under consideration.

Outputting the translation of each instruction as it is tokenized, rather than storing up all the translations until the end, removes the need for any extra data structures.

Comments


  • -8
    aijulianjason  commented on Feb. 18, 2024, 4:51 a.m. ← edit 3

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 3
      Viv_CCGS  commented on Feb. 18, 2024, 9:20 a.m.

      Please refrain from sharing solutions in the comments section of both the editorial and the main problem section. I, for one, have a hard time trying to solve the problem myself if there is a ready made solution for me to copy paste in for full marks. I am sure there are others out there just like me, so please, respect the system of DMOJ and let the users solve it for themselves. Thank you for your consideration.