INQU2001 - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Prakhar Kulshrestha
Tester: Vivek Rathi
Editorialist: Prakhar Kulshrestha

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Recursion and Modular Arithmetic

PROBLEM:

Note : I would honestly recommend to read the actual problem statement

A round i of musical chair game requires T_i rotation of positions of n people in a circle around m
chair (n>m) in the clockwise direction . At the start, some people are in control of exactly one chair and others have no chair. All chairs are immediately adjacent ,so people holding these chairs are also immediately adjacent thus forming a segment of a circle. Rotations will cause this “in control of chair” segment to move in anticlockwise direction. After the rotations end , this segment will be safe and other people not part of this segment will be eliminated and we will move on to the next round while removing some chairs too for it.

The first round has 2*N people and N chairs. Initially first N people are part of the safe segment and others are not (P_1 -> C_1 , P_2 -> C_2 ....... P_N->C_N). After every round of eliminations with m chairs, \lceil m/2 \rceil chairs from the higher index end will be removed making safe people with those chairs unsafe.

Given no of rounds and rotation for each round, Tell who’s the winner (last person standing before rounds end).

QUICK EXPLANATION:

Recursively keep calling the winner for the next round and rotate positions in recursion unpacking.

EXPLANATION:

Our solution follows basic recursion and modular arithmetic. Each round and its next round can be seen as a transition between three parameters.

Each round and its next round can be seen as a transition between three parameters.

  1. Round No : i , to track some edge cases for the most part, becomes i+1

  2. No of chairs in current round m , becomes ⌊m/2⌋

  3. No of people in current round n , becomes m

Let’s say we recursively get to know that a subproblem for the next round will grant X as the winner. We pickup the fact that the next round was formulated after rotation by T_i positions. So the winner X here was someone who was at a position X from the perspective of person 0/1(index ambiguity, basically the person with the first chair) after circling in this round. So , the real identity of X has been revolving around in the round and we basically will have to undo that . Thus, for this round , in the recursion unpacking phase, we can return our winner by going back T_i positions.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std; 
#define ll long long int
#define fi first
#define se second
int t;
long int n,x;
ll rt[40];
ll solve(ll chairs,ll people,ll roundno){
      if(people==1){
         return 0;
      }
      if(roundno==x){
         return -1;
      }
      int curinc = (rt[roundno])%people;
      
      //Person at index 0
      ll person0 =  (people-curinc)%people;
      if(chairs == 1){
         return person0;
      }
      int winner = solve(chairs/2,chairs,roundno+1);
      if(winner==-1){
         return -1;
      }
      return (person0+winner)%people;
}
int main(){
   cin>>t;
   for(int a0=0;a0<t;a0++){
      cin>>n>>x;
      for(int i=0;i<x;i++){
         cin>>rt[i];
      }
      ll z = solve(n,2*n,0);
      if(z==-1){
     cout<<z;
  }else cout<<z+1;
  cout<<"\n";
   }
   return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

ll a[100001];
ll n,x;
ll solve(ll round,ll peoples,ll chairs)
{
	if(peoples==1)
		return 0;
	else if(round==x)
		return -1;
	ll effective_time = (a[round])%peoples;
	ll start = (0-effective_time+peoples)%peoples;
	if(chairs==1)
	{
		return start;
	}
	ll position = solve(round+1,peoples/2,chairs/2);
	if(position==-1)
		return -1;
	return (position+start)%peoples;
}
int main()
{
	ll t;
	cin>>t;
	while(t--)
	{		
		cin>>n>>x;
		for(ll i=0;i<x;i++)
		{
			cin>>a[i];
		}
		ll temp = solve(0,2*n,n);
		if(temp==-1)
			cout<<temp<<endl;
		else
			cout<<temp+1<<endl;
	}
	return 0;
}
3 Likes