Author: Jaskaran Singh
Tester: Rahul Sharma
Editorialist: Rahul Sharma
DIFFICULTY:
EASY
PREREQUISITES:
Strings, observation, basic math
PROBLEM:
Beeds Arranging game is described by a string of length nn consisting of characters “.” (empty space) and “*” (beed). In one move you can shift beed to one unit left or one unit right, only if the corresponding place exists and is empty. The game ends up as soon as the beeds are lined up, that is, there should not exist any empty cells between any beeds.
FInd minimum number of moves.
EXPLANATION:
Let’s denote k the number of beads in the string, and x_q,x_2,...,x_k (1 \leq x_1<x_2<...<x_k \leq n) their positions in the string.
Note that in the optimal solution the beed with number m=ceil(n/2) will not make moves. This can be proved by considering the optimal solution in which the beed with the number m makes at least one move and come to the conclusion that this solution is not optimal. Consider beed with numbers from i=1 to n. Then the final position of the $i^{th} beed will be x_m-m +i, and the answer will be \sum|xi−(x_m−m+i)| where i runs from 1 to k.
COMPLEXITIES:
Time Complexity: O(N) for each test case
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
int cnt = 0;
for(auto x : s)
cnt += (x == '*' ? 1 : 0);
int pos = -1;
int cur = -1;
for(int i = 0; i < n; i++)
{
if(s[i] == '*')
{
cur++;
if(cur == cnt / 2)
pos = i;
}
}
long long ans = 0;
cur = pos - cnt / 2;
for(int i = 0; i < n; i++)
if(s[i] == '*')
{
ans += abs(cur - i);
cur++;
}
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int tc = 1;
cin >> tc;
for(int i = 0; i < tc; i++)
{
solve();
}
}