AugustAmes's blog

Any Alternate Approaches to Problem B of Educational Codeforces Round 69
By AugustAmes, history, 5 years ago, In English

The problem seemed similar to the Nim game, so are there any alternative approaches?

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My approach is not based off the game of Nim, but it is still quite different than the Editorial's solution. You can read my solution here.

First, notice that since all disks $$$a_i$$$ are distinct and $$$1 \leq a_i \leq n$$$, all of the $$$a_i$$$ are simply a permutation on the integers in the interval $$$[1, n]$$$. This means that, because when placing the disk, the new disk must have radius less than that of the currently topmost disk, in order to place all $$$n$$$ disks on one pillar simultaneously, you have to be able to place them in a way such that $$$n$$$ is on the bottom, and $$$n-1$$$ is second-to-bottom, and $$$n-2$$$ is third-to-bottom, etc. until $$$1$$$ is at the top.

Thus, all $$$n$$$ disks will eventually end up on the pillar $$$m$$$ where $$$a_m=n$$$ since the disk of value $$$n$$$ must stay on the bottom and can not be moved to any other pillar. Then, we have to be able to place $$$n-1$$$ on top of $$$n$$$. This can only happen if $$$n-1$$$ is a neighbor of $$$n$$$, so if it is not, then output NO.

Then, we need to be able to place $$$n-2$$$ on top of $$$n$$$. This can happen only if $$$n-2$$$ is a neighbor of $$$n$$$ OR if $$$n-2$$$ was previously a neighbor of the pillar containing $$$n-1$$$, which is now an empty pillar. If $$$n-2$$$ is a neighbor of this empty pillar, then we can move $$$n-2$$$ from its current pillar onto the empty pillar and then from the empty pillar to the pillar containing $$$n$$$ on the bottom.

From these two cases, we can see a pattern: After disks $$$n-1$$$ down to $$$x+1$$$ have been placed on top of disk $$$n$$$, disk $$$x$$$ will only be able to be placed on top of $$$n$$$ if it is a neighbor to the pillar containing $$$n$$$ or if all of the pillars between $$$x$$$ and $$$n$$$ are empty pillars. Thus, to determine if disk $$$x$$$ can be placed on top of disk $$$n$$$, we can, at all times, keep pointers to the leftmost and rightmost empty pillars. If disk $$$x$$$ is a neighbor to either of these pillars, then it can be placed on top of disk $$$n$$$ by moving it across the empty pillars. Otherwise, it can not been placed on top of disk $$$x$$$ so we break the loop and output NO. Then, once we put disk $$$x$$$ on top of disk $$$n$$$, we need to decrement/increment the leftmost/rightmost empty pillar pointer accordingly. This process keeps repeating until we are able to place all disks $$$1$$$ through $$$n-1$$$ on top of disk $$$n$$$, in which case we output YES.

I know this may seem a little more complicated than the editorial solution, but two-pointers is the first thing that came to mind when I saw this problem and, if you read my solution, you will see that it is still $$$O(n)$$$ and does not really require that much code to implement.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is my approach same as yours?

    My approach : Repeat the following steps $$$n$$$ times:

    1. Find the minimum of the first and the last element of the sequence.

    2. Write it down.

    3. Erase that element from the sequence.

    If the final sequence that we write down matches with the sequence $$$1$$$ $$$2$$$ $$$3$$$...$$$n$$$, then the answer is "YES", else answer is "NO".

    Link to my submission : 57520416

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually, your approach is quite different from mine. My approach uses two pointers which start at the position where disk $$$n$$$ is located and work their way outwards to the two ends of the array. However, your approach uses two points which start at either end of the array and work their way inwards to the position where disk $$$n$$$ is located.

      However, I think your solution is still valid, although it is different from my approach. Your approach is valid because, as explained by the editorial, the sequence of disks is always increasing up to the position containing disk $$$n$$$, and then decreasing afterward. This property implies that the minimum disk still left after erasing some disks will always be either at the beginning or the end of the array, which is how your algorithm works.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Find the position of highest no. Then, every other element has a target direction. If there is an element that lies between the target and current element and is smaller than the current element, then the answer is no.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Find highest number position then just loop from that position till n and from position till 0 and check that it's a decreasing sequence always Code

→ Reply