STONE_PILE - Editorial

editorial
, ,
1

Problem Link: Stone Pile

Problem Statement:

Aman and Akshat are trying to solve a task given to them by their teacher. They are given a pile of stones containing N stones with an integer written on each of them. There are two different kinds of moves that can be performed on the pile :

  1. Player will remove a stone from the top of the pile and put it back on the bottom of the pile
  2. Player will remove a stone from the top of the pile and throw it away.

Aman in his turn will perform move 1 once and then move 2 once. Akshat in his turn will perform move 1 twice and then move 2 once.
They will stop making moves when there is only 1 stone left in the pile.
Both of them gets turn alternatively with Aman going first. Find the person performing the last move and the number written on the last stone left in the pile.
The stones at index i-th is located higher than the stones at index j'th , such that (i<j).

Approach:

The key idea of the code is to simulate alternating operations on the queue, where the operations differ depending on whether the current turn is even or odd. Here’s a breakdown:

  1. Initialization:

    • We start by reading the number of test cases t.

    • For each test case, we read the number of elements n and then insert these elements into a queue called answer.

  2. Turn-based Operations:

    • We simulate a process where, in each round (determined by turn), we perform different operations depending on whether the current turn is even or odd:

      • For even turns: We remove the front element of the queue, push it back to the rear, and then remove the next front element.

      • For odd turns: We rotate and remove two elements, similar to the even turn, but with an extra step.

    • The turn variable increments after each round, ensuring we alternate between even and odd operations.

  3. Final Output:

    • Once only one element remains in the queue, the loop terminates.

    • If the original number of elements n was odd, we print 0 and the last remaining element. If n was even, we print 1 and the last remaining element.

Time Complexity:

  • Queue Operations: Each push and pop operation on the queue takes O(1) time.

  • Overall Time Complexity: The complexity for each test case is O(n) since each element is pushed and popped from the queue multiple times.

Space Complexity:

  • The space complexity is O(n) for storing the queue of integers.