Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Codeforces 1238 (Div 2) C - Standard Free2play】Let's understand the problem sentence!

Problem - C - Codeforces

The problem C in the div 2 contest is notorious for the problem sentence which is just difficult to understand that even a competitor ranked in yellow in AtCoder failed 5 times as he misunderstood the problem as found in twitter.

I couldn't understand the problem too. After 10 minutes of reading the sentence carefully, I couldn't even get how these undefined words like "moving platform", "moved out", "hidden" and "cliff" mean. The reason I couldn't understand the sentence is the lack of the simple drawings for explanation although the sentence is not abstract. Honestly, I prefer sentence in mathematical notations because it is more well-defined that there is no room to misunderstand, and quicker to grasp.

Let's understand the problem with nice drawings!

The goal is to reach the ground and initially you are in platform of height h. There are platforms from 1 to h but only in given sequence P is initially on the right side. Platform is either placed on the right side or the left side, and placing on the right side is called moved out or pulled out and hidden in the another case.

f:id:akiradeveloper529:20191009185239j:plain

To move down the platforms, you are only allowed to fall. To fall, you can change the state of platform of height x and height x-1. If the both platforms are initially on the right side and they are changed to the left side simultaneously, no need to say you fall a long distance. If the distance is greater than 2 you will be dead.

f:id:akiradeveloper529:20191009185249j:plain

To avoid the miserable death, you can buy a magical stone to change the state of an arbitrary platform. With this magical stone, you can eventually reach the ground and the question is how many stones you need.

f:id:akiradeveloper529:20191009185259j:plain