FEMA2 - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Avinish Kumar
Tester: Istvan Nagy

DIFFICULTY:

Easy

PREREQUISITES:

Queue

PROBLEM:

Chef loves to play with iron (Fe) and magnets (Ma). He took a row of N cells (numbered 1 through N) and placed some objects in some of these cells. You are given a string S with length N describing them; for each valid i, the i-th character of S is one of the following:

  • ‘I’ if the i-th cell contains a piece of iron
  • ‘M’ if the i-th cell contains a magnet
  • ‘_’ if the i-th cell is empty
  • ‘:’ if the i-th cell contains a conducting sheet
  • ‘X’ if the i-th cell is blocked

If there is a magnet in a cell i and iron in a cell j, the attraction power between these cells is P_{i,j} = K+1 - |j-i| - S_{i,j}, where S_{i,j} is the number of cells containing sheets between cells i and j. This magnet can only attract this iron if P_{i, j} \gt 0 and there are no blocked cells between the cells i and j.

Chef wants to choose some magnets (possibly none) and to each of these magnets, assign a piece of iron which this magnet should attract. Each piece of iron may only be attracted by at most one magnet and only if the attraction power between them is positive and there are no blocked cells between them. Find the maximum number of magnets Chef can choose.

QUICK EXPLANATION:

We will try to collect an iron at an index with the least possible magnet’s index which has yet not been used to collect any other Iron.

EXPLANATION:

First thing is whenever we encounter a Wall it divides the string into two parts. And those parts can not have any relation or attraction between themselves.

Sheet reduces the magnetic strength by an additional one so simply add an extra position near the sheet. This will automatically reduce the strength by one. So create a new string adding an additional sheet whenever it is encountered. We will now work on the new string.

We will try to collect an iron at an index with the least possible magnet’s index which has yet not been used to collect any other Iron. As higher we will go in the index, the chance of using the magnet with less index will get less as its range is limited. So try to find the minimum index of magnet that can collect the iron and increment the ans if such magnet is found.

Create two empty queues (one for the magnets (qm) and other for the iron (qi)). qi will contain the iron indexes and qm contains magnet indexes found till current index and yet not used by any Magnet and Iron respectively. Start reading the characters from the 0th index.

If a magnet is found try reading qi for an index that is in the range of magnet until qi gets empty. If such iron is found increase the ans counter else insert this index to qm. And vice versa if iron is found.

SOLUTIONS:

Setter's Solution
/*
    * @authr AVINISH KUMAR
    * @college BIT MESRA    
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t;
    cin >> t;
    while (t--)
    {

        ll n, k;
        cin >> n >> k;
        string s;
        cin >> s;

        string new_s = "";

        //sheet reduces the magnetic strength by an additional one so simple 
        //add an extra position with sheet. This will automatically reduce the
        //strength by one.
        for (auto i : s)
        {
            if (i == ':')
            {
                new_s += i;
            }
            new_s += i;
        }

        //Queues to store index of Magnet and Iron found till the index
        //and yet not used
        queue<ll> qi; //iron indexes
        queue<ll> qm; //magnets indexes

        //the current index of string
        int j = 0;

        //it stores the number of iron collectible by magnet
        int ans = 0;

        for (auto i : new_s)
        {
            //If current character is Iron, we will check the queue for the Magnet whose
            //index is in range of K. If no such Magnet is found we push the Iron's index
            //to qi queue. If there is such Magnet, we will pop the Magnet out of queue qm and
            //increment the ans as the Iron can be collected by that Magnet.
            if (i == 'I')
            {
                while (!qm.empty() && qm.front() + k < j)
                {
                    qm.pop();
                }

                if (!qm.empty())
                {
                    ans++;
                    qm.pop();
                }

                else
                {
                    qi.push(j);
                }
            }

            //vice versa if magnet is found.
            else if (i == 'M')
            {

                while (!qi.empty() && qi.front() + k < j)
                {
                    qi.pop();
                }

                if (!qi.empty())
                {
                    ans++;
                    qi.pop();
                }

                else
                {
                    qm.push(j);
                }
            }

            //if there is a wall then simply remove all the previous magnets and irons
            else if (i == 'X')
            {
                while (!qm.empty())
                {
                    qm.pop();
                }
                while (!qi.empty())
                {
                    qi.pop();
                }
            }

            //increment the index of string
            j++;
        }

        //output the final answer
        cout << ans << endl;
    }
}
Tester's Solution
#include <bits/stdc++.h>

using namespace std;

//FEMA2
uint32_t calc(const string& s, int K)
{
	int N = s.length();
	int i = 0, m = 0, res = 0;
	while (i < N && m < N)
	{
		while (i < N && (i < m - K || s[i] != 'I'))
			++i;
		while (m < N && (m < i - K || s[m] != 'M'))
			++m;
		if (i < N && m < N && abs(i - m) <= K)
		{
			++res;
			++i;
			++m;
		}
	}
	return res;
}

int main(int argc, char** argv) 
{
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	for(int tc = 0; tc < T; ++tc)
	{
		int N, K;
		string s;
		cin >> N >> K;
		cin >> s;
		string z;
		uint32_t res = 0;
		for(auto c: s)
		{
			if (c == '_')
				z += ' ';
			else if (c == ':')
				z += "  ";
			else if (c == 'X')
			{
				if (z.length())
					res+=calc(z, K);
				z.clear();
			}
			else
				z += c;
		}
		if (z.length())
			res += calc(z, K);
		cout << res << endl;
	}
	return 0;
}

VIDEO EDITORIAL (Hindi):

VIDEO EDITORIAL (English):

2 Likes

better quetions, tricker than previous ones

1 Like

Solution link https://youtu.be/HtT9bexr1SA

1 Like

Can we bipirate matching…?(iron to magnet matching)
I have used it…
https://www.codechef.com/viewsolution/39556856
FYI, the solution is only for subtask 1.
Please tell me, what is wrong with my solution…

I used a binary search approach did same like adding 2 underscore in place of : and similarly for X I put its index and for every magnet i specified their range using 2 d array a afterward for every iron i search whether this index is in range of any ( magnet having least position ) afterwards i increase the low value if magnet found. i trie so many testcases on my own but not getting where i getting wrong please help.
solution:
https://www.codechef.com/viewsolution/39559782

Hi. I used two pointers one for iron and one for tracking magnet. Using prefix sums I calculate the no. of sheets between the two pointers and also check if there are any blocks in between them. Still getting WA on both subtasks, can anyone please tell me what’s wrong with my approach? Thanks in advance.

Here is my submission with the above approach - https://www.codechef.com/viewsolution/39576665

Hi, According to the given constraints the code should work for time complexity of O(n^2) right??

I have a doubt and I am stuck at it. What I am trying to do is I am taking two sets st1 (it will contain indices of all magnets) and st2 (it will contain indices of all irons). Then I am iterating over st1 and and trying to find the iron which is at the longest distance w.r.t current magnet. For ‘X’ and ‘:’, I am using prefix sum for pre-computation. Then between any two index, we can find that how many ‘:’ and ‘X’ is there.
My question is, how can I implement binary search function for set such that I can find the iron at longest distance w.r.t current iron?

my solution why this is wrong?

there is simple mistake i did . i resolved it
in line 92 i have to put low=ans+1 instead of low=mid+1, that’s all.
Correct solution:https://www.codechef.com/viewsolution/39664454

There is an error in the code for second loop in the solution provided. Instead of checking the contents of string l, the code is checking the contents of string s. This is quite misleading as it is shown in the video that on the same code we get AC, which is not true. I was stuck on it for about 20 minutes. Kindly check the contents before the videos go public. I believe that the video solution should not contain any mistakes as we have already spent a lot of time solving a problem during the contest.
Please look into it.

4 Likes

Wht is the time complexity of the editorial solution?

The java code is getting TLE any idea why?

YES bro if we are using ONE loop for managing the conducting sheets before performing actual logic then I am also getting TLE. I Guess its because of String concatenation.

Kindly use stringBuilder class for the first loop while building new String where there is some adjustment for the : (conducting Sheets)

#include <bits/stdc++.h>
int main()
{
   // solution for fema2
    //two pointer approach  :)
   // j for iron and i for magnet
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
   {
        int n;
        int k;
        cin>>n>>k;
        string s;
        cin>>s;
        int ans=0;
        int count=0;
        int i=0,j=0;
        int pre[n];
        if(s[0]==':')pre[0]=1;
        else pre[0]=0;
        for(int i=1;i<n;i++)
        {
            if(s[i]==':')pre[i]=1;
            else
            pre[i]=0;
            pre[i]=pre[i-1]+pre[i];
        }
        while(i<n && j<n)
        {
            if(s[i]=='M')
            {
                if(s[j]=='I')
                {
                   
                    int power=k+1-abs(i-j)-(pre[max(i,j)]-pre[min(i,j)]);
                    if(power>0)
                    {
                        ans++;
                        i++;
                        j++;
                     
                    }
                    else
                    {
                        if(i<j)i++;
                        else j++;
                        
                    }
                }
                else if(s[j]=='X')
                {
                    i=j;
                    i++;
                    j++;
                }
                else
                {
                    j++;
                }
            }
            else if(s[i]=='X')
            {
                if(i<j)
                i++;
                else
                {
                    j=i;
                    j++;
                    i++;
                }
            }
            else
            {
                i++;
            }
        }
        cout<<ans<<endl;
    }
 
 
 
 
 
 
 
  return 0;
}

any doubt in solution please ask :blush:

For the test case:
1
7 2
M_I_M_I
The answer should be 1 right? Since the first I removes the option of choosing both Ms. So the moment we choose one M, the other M becomes unavailable to choose. But the editorial answer is 2, which should be wrong. Can someone please clarify where I am wrong? Thank You

for I(2)u can choose M(0) or M(4) but if u choose M{4) ur I(6) willl be useless similarly M(0) so for I(2) go for M(0) and for I(6) go For M(4) to use all magnet

The moment you choose I(2), M(0) and M(4) both are in I(2)'s range, so you can only choose one of them(since the condition is 1 iron can only have 1 magnet attracting it). That’s why I am saying the answer is 1.

Can anyone help me why my code is giving WA?

#include<bits/stdc++.h>
#define int long long int
using namespace std;

int32_t main(){
/* code */
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

int t; cin >> t;
while(t--){
	int n,k; cin >>n >> k; 
	string s; cin >> s;

	int I,M;
	I=M=-1;
	k +=1;

	bool f1=false,f2=false;
	int ans=0;

	for(int i=0;i<n;i++){
		if(s[i]=='I' && !f1){
			if(I<=i){
				I=i;
				f1=true;
			}					
		}
		if(s[i]=='M' && !f2){
			if(M<=i){
				M=i;
				f2=true;
			}
		}
		if(s[i]=='X'){
			I=i;
			M=i;
			f1=false;
			f2=false;
		}
		if(f1 && f2){
			int l ,r,sheet = 0;
			l = min(I,M);
			r = max(I,M);
			for (int q = l; q <= r; ++q)
			{
				if(s[q]==':')
					sheet++;
			}

			int temp = k - abs(I-M)-sheet;
			if(temp>0){
				ans++;
				I++;
				M++;
				f1=false; f2=false;
			}
			else if(I<M){
				I++;
				f1 = false;
			}
			else{
				M++;
				f2 = false;
			}
		}
	}
	cout << ans << endl;
}
return 0;

}