FEMA2 - Editorial

I am getting WA on subtask 2.
Can anyone help?
Here is my submission with two pointer approach-
https://www.codechef.com/viewsolution/39516783

I have used String and StringBuilder both and also used string.replace method too but still TLE ://

Can anyone help me why my code is giving WA for subtask 2 @a_coder_hack
https://www.codechef.com/viewsolution/39691536

Hey can you check my solution CodeChef: Practical coding for everyone?
Its very similar to your approach

Bro your code is giving wrong answer for this test case
1
7 5
XM:::MI

1 Like

bro i think you are complicating it a little bit. You are first checking the presence of the M and I . Then you are looking for the no. of sheets and the block between them. Instead of that try to go through my approach.
First, Store the index of the M and I in two different arrays. and also check that either you get a block or you just finish the string without getting any block.
Second, when the above condition hold true then just apply the power formula to the indexes from the arrays you got above.
this approach is much simpler.

1 Like

yeah I added stuff unnecessarily. Thanks!

@corack
This might be a silly question but how did you come up with this testcase?
I was trying to find the same for a couple of days.

    #include <bits/stdc++.h>

using namespace std;


void solve() {
	vector<int> ans;
	int n, k;
	cin>>n>>k;
	vector<char> a(n);
	for(int i=0;i<n;i++) {
		cin>>a[i];
	}
	unordered_map<int, int> magnets;
	unordered_map<int, int> iron;
	unordered_map<int, int> conductor;
	int flag = 0;
	for(int i=0;i<n;i++) {
		if(a[i] == 'I') {
			iron[i] = i;
		} else if(a[i] == 'M') {
			magnets[i] = i;
		} else if(a[i] == ':') {
			int prev;
			if(a[i] == a[i-1]) {
				conductor[prev] = i;
			} else {
				prev = i;
				conductor[i] = i;
			}
		} else if(a[i] == 'X') {
			for(auto j:magnets) {
				for(auto h:iron) {
					pair<int, int> cond;


					for(auto g:conductor) {
						if(g.first >= j.first && g.second <= h.first) {
							cond = make_pair(g.first, g.second);
							break;
						}
					}


					int s = k+1-(abs(j.first - h.first))-((cond.second - cond.first) + 1);
					ans.push_back(s);
					flag = 1;
				}
			}
			magnets.clear();
			iron.clear();
			conductor.clear();
		}
	}

	if(flag == 0) {
		int prev = -1;
		for(auto j:magnets) {
			for(auto h:iron) {
				pair<int, int> cond;


				for(auto g:conductor) {
					if(g.first >= j.first && g.second <= h.first) {
						cond = make_pair(g.first, g.second);
						break;
					}
				}
				int curr = j.first;
				int s = k+1-(abs(j.first - h.first))-((cond.second - cond.first) + 1);
				if(curr != prev)
					ans.push_back(s);
				prev = j.first;
			}
		}
	}
	
	int as = 0;
	for(int i:ans) {
		if(i>0) as++;
	}
	cout<<as<<endl;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin>>t;

	while(t--) {
		solve();
	}

}

Why I am getting WA?

as this test case covers almost every check and balances of your approach. So i tried to make that case and fortunately i hit it at the very first time.
Tip: Whenever your code gets WA and you have gotten the correct answer for the given sample test case then just keep calm and look at your codes approach and try to make different and unusual test case. If you try it several time i believe you will get the bug. As, I do this when this happen to me, and it works.

1 Like

Cool.
Thanks for the tip :100:

Can someone please explain why am I getting TLE for my java code : - CodeChef: Practical coding for everyone

bro i dont know java much so i dont know if i’m 100% correct but what i can see here is your have two different loops.

  1. for calculating the sheets.(which should be removed unnecessarily increasing time complexity).
  2. main while loop where you are calculating the real problem.
    so I think you should remove the first for loop.
    you should calculate the number of the sheets only and only when you get one magnet and one iron. it will reduce the time taken.

@corack bro can you give link to your solution?

No

For those who are getting WA in second subtask.
https://www.codechef.com/viewsolution/39736536

since the condition is 1 iron can only have 1 magnet attracting it so for first iron go for first magnet and for second iron go for second magnet to maximize the number of magnet uses,

if u used 2nd magnet for first iron u will not be able to use 1st magnet (since the condition is 1 iron can only have 1 magnet attracting it) and so firsT magnet will be useless but u have to maximise magnet so go for above match.

You are not getting what I am saying. Once you choose the first magnet, it doesn’t matter which iron you ‘choose’ for it, it will attract both irons anyway(since they are in range). This prevents you from choosing the second magnet at all since the middle iron is already being attracted by the first magnet, irrespective of you choosing the first magnet for it. In simple words, the first magnet will always attract both the iron pieces. You can’t ‘choose’ which iron it will attract or not. You place an iron piece in its field, it will attract it.

Sorry for the late reply.
There you go - CodeChef: Practical coding for everyone

What am I doing wrong here?

https://www.codechef.com/viewsolution/39821458