Swagath's blog

By Swagath, 11 years ago, In English

I have been trying this problem http://www.spoj.com/problems/ESY/.. SPOJ/ESY

pls help me what cases i'm missing... pls....

#include <iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main() {
	int n;
	while(scanf("%d",&n)!=-1){
		int a[n];
		int ones=0;
		int ans=1;
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			a[i]*=(a[i]<0)?-1:1;
			if(a[i]>1)
				ans*=a[i];
			else if(a[i]==1)
				ones++;
		}
		//cout<<ans<<" "<<ones<<endl;
		if(ans==1)
			ans=0;
		int k=ones,l;
		if(ones>3)
		{
			k=ones/2;
			l=ones-k;
			k=k*l;
		}	
		if(ans>0&&k>1)
			ans*=k;
		else
			ans+=k;
		ans*=-1;
		cout<<ans<<endl;
			
	}
	return 0;
}

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By Swagath, 11 years ago, In English

I and my friend were recently trying to solve a problem named KEY TASK in SPOJ.

Our first approach is simple BFS that resulted in a TLE.

Then we searched for hints online we came across a hint saying we can solve it using BFS with bit-masking . we tried to understand the concept by reading some others code online but we couldn't get the hang of it.

What we inferred from seeing other's code was, this maze was split into 16 layers like MAZE[row][column][16] and the coder was using masks in powers of 2 each and every time and we were baffled on seeing his code.

we always visualize the concept told to us or that we learn but we couldn't visualize anything for this problem.

So my questions are, what is the intuition behind BIT-MASKING ? How to find you need a bit-mask for a problem ? How to approach and apply it for problems ? Why we need it and how it simplifies the task ?

Answers considering this question and all problems in general relating to bit-masking is every much appreciable.

Can someone well versed in this help me with your thought process in this!

Thanks in advance.

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it