Sweet and Sour Rock

The term "easily" is relative . All AMPPZ's and CEPC's have one problem which is meant to be solved by most teams; in the case of this contest this is the one.

Don't bring back painful memories... argh
Still, I suppose I was in the lucky half that did something

You are absolutely right. I should have done it straight away when adding the problem. Now changing the input may get tricky in case the solutions have to be rejudged.

Perhaps we could leave the problem as is this once (after all, the O(n^2) solution is simpler than the O(n^3) ), and I would simply remember about this when adding tasks from other contests?

As you say, both approaches have their advantages and disadvantages. I think all such cases should be analysed individually. This particular task demonstrates another problem that might appear, necessitating a change of test data rather than a change of time limits. This is more unpleasent (since previously submitted programs simply stop being correct for the new test data). I think that in such a case, if the problem is worth it, it would be better to add another similar task.

We were hoping that optimisation problems might prove a reasonable compromise - allowing users to outperform problemsetters without the need for rejudging. Perhaps they require some interface improvements before they "catch on".

And I would sincerely like to thank you & all SPOJ users for solving them, and for the kind and helpful remarks which allow us to improve the judge and the problemset.

I will try to add a new batch of tasks soon, but since our team will temporarily "run dry" in about 120 tasks (~20 original ones and ~100 from contests - chosen from CEOI, PolishOI, remaining AMPPZ, SwissOI and Algorithm Busters), we are always counting on new problems being added by SPOJ Problemsetters, and on any suggestions of interesting contests with freely available problems, for inclusion in SPOJ.

I don't understand why the first example returns 9 - which 9 segments of "100110001010001" would be used? They have to be contiguous, right? Or can you break it more than once?

dplass;

this way, old bean,

10011 000 101 000 1

Sum up the total length of pieces in bold.

Thanks. I inferred from the problem statement that you could only break the rock once.

A half-of-the-kingdom for a couple of good, brain-cleanzing test inputs.

Doing my best I could think up only this one:

16
0110100001110001
=====
12

(The previous post is mine)
I ever thought it is a kind of "linear" problem.
My main idea on this is:
1.
find the leftmost "1" in a given "0,1" string; then, starting from this "1",
I find the continuous piece of MAX length that can be bitten off (and sold).
Bite off this left-end piece.
2.
Repeat 1.

What's wrong here? It works so far (on my test inputs):

1
0
= 0

3
111
= 3

3
101
= 3

3
010
= 1

7
0011111
= 7

15
100011001100011
= 12

It's not gonna work here:
13
1000111001001
8)

Can someone give me some hints for this problem .I am running out of options. Any special data structures . What line do we need to think in.

Hi,
I got AC in this problem by first finding all the valid pieces and then finding the longest increasing subsequence of valid sticks. It runs for more than 4 seconds. I believe there's a more efficient algorithm. Could someone tell me what it is? Or a hint, maybe?

I found a recurrence for the problem, and simply implemented it as a recursive function memoized by a large 2D array. My C solution runs in 1.13 seconds. I hope this helps.

MAK

Hi,
For the case:

15
100110001010001

Why can't we choose (the segments in bold) 1 00 110 00 1010001 and get a total length of 11 ?
Anyone please tell me where I am wrong. Thank you.

Number of sweet segments must be greater than number of sour segments.

In your last rock, you have sweet=3 parts and sour=4 parts.

Hi,
I am trying spoj.pl/problems/ROCK/
The 1st code below gives WA and the 2nd TLEs.
Anyone please explain what I am missing.
Thank you.

Code 1:

#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
using namespace std;
#define GI ({int t ;scanf("%d",&t);t;})
#define FORZ(i,n) for(typeof(n)i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define PB push_back
#define sz size()
#define FF first
#define SS second
typedef vector<int> VI;
typedef pair<int,int> pII;
typedef vector<string> VS;
typedef long long LL;
int n;
string s;
int dp[202][202];
int solve (int p, int diff, int len)
{	
	if (p == n) 
		return (diff > 0) ? len : 0;
    if (dp[p][diff] != -1) 
	return dp[p][diff];

int a = 0, b = 0, c = 0;

if (s[p] == '1') 
{
	// include the '1' to the current segment
	a = solve (p + 1, diff + 1, len + 1);		
	
	// break at this point and start a new segment at this point (p)
	if (diff > 0) b = len + solve (p + 1, 1, 1);	
	
	return dp[p][diff] = max (a, b);
}

else 
{
	// break at this point and start a new segment at (p + 1) discarding the '0'
	if (diff >= 0) a = len + solve (p + 1, 0, 0); 
	
	// include the '0' to the current segment
	b = solve (p + 1, diff - 1, len + 1); 
	
	// break at this point and start a new segment at this point (p)
	if (diff >= 0) c = len + solve (p + 1, -1, 1); 
		
	return dp[p][diff] = max (a, max (b, c));
}
}
int main ()
{
    int t = GI;

while (t --)
{
	cin >> n >> s;		

	FORZ (i, 202) 
		FORZ (j, 202) 
			dp[i][j] = -1;		
			
	int ans = solve (0, 0, 0);		
	printf ( "%d\n", ans );		

}

return 0;
}

Code 2:

#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
using namespace std;
#define GI ({int t ;scanf("%d",&t);t;})
#define FORZ(i,n) for(typeof(n)i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define PB push_back
#define sz size()
#define FF first
#define SS second
#define MP make_pair
typedef vector<int> VI;
typedef pair<int,int> pII;
typedef vector<string> VS;
typedef long long LL;
#define MAX 40001
int n, size;
string s;
vector <pII> vec;
int dp[MAX];
int solve (int p, int len)
{
	if (p == size - 1)	return len;		
	if (dp[p] != -1) return dp[p];	
	int ret = 0;
	for (int nxt = p + 1 ; nxt < size ; nxt ++)
	{
		if (vec[nxt].FF < vec[p].SS) continue;
		int v = vec[nxt].SS - vec[nxt].FF + 1;
		if (vec[nxt].FF == vec[p].SS) v --;
		ret = max ( ret, solve ( nxt, len + v ) );
	}
	return dp[p] = max (len, ret);
}
int main ()
{
	int t = GI;
	while (t --)
	{
		cin >> n >> s;	
		vec.clear();
    	FORZ (i, n)
	{
		for (int j = i ; j < n ; j ++)
		{
			int diff = 0;
			for (int k = i ; k <= j ; k ++)
				diff += (s[k] == '1') ? 1 : -1;
			if (diff > 0) vec.PB ( MP (i, j) );	
		}
	}	

	vec.erase ( unique ( all(vec) ), vec.end() );

	if (vec.empty())
	{
		printf ( "0\n" );
		continue;
	}

	size = (int)vec.sz;
	
	int ans = 0;		
	for (int st = 0 ; st < size ; st ++)
	{
		memset (dp, -1, sizeof dp);		
		int val = solve ( st, vec[st].SS - vec[st].FF + 1 );
		ans = max ( ans, val );		
	}		
		
	printf ( "%d\n", ans );
}

return 0;
}

hey , i was practicing Dynamic Programing and slolving this problem .. i am getting wrong answer , please can anyone tell me what is wrong with my code ...
and i am new to programing and all so the code might seem haphazardous ...

#include<cstdio>
#include<cstring>
typedef struct table
{
	int start;
	int end;
	int val;
}table;
table l[50001];
int H;
void merge(int L,int m,int r)
{
	table b[50001];
	int i=L,j=m+1,k=L;
	while(i<=m && j<=r)
	{
		if(l[i].end>l[j].end)
		{
			b[k]=l[j];
			j++;
		}
		else
		{
			b[k]=l[i];
			i++;
		}
		k++;
	}
	while(i<=m)
	{
		b[k]=l[i];
		i++;
		k++;
	}
	while(j<=r)
	{
		b[k]=l[j];
		j++;
		k++;
	}
	for(i=L;i<=r;i++)
	{
		l[i]=b[i];
	}
	return;
}
void sort(int l,int r)
{
	if(l>=r)
		return;
	int m;
	m=(l+r)/2;
	sort(l,m);
	sort(m+1,r);
	merge(l,m,r);
	return;
}
int bin(int s)
{
	int m=H/2;
	int x;
	int r,f=-1;
	int min=0,max=H;
	while(min<max && s!=l[m].end)
	{
		if(l[m-1].end <s && l[m].end>s)
		{
			f=m-1;
			break;
		}
		if(l[m].end<s && l[m+1].end>s)
		{
			f=m;
			break;
		}
		if(s<l[m].end)
		{
			max = m;
			m=(m+min)/2;
		}
		else
		{
			min=m+1;
			m=(m+max)/2;
    	}

}
if(f!=-1)
return f;
return m;
}
void best()
{
int X[50001]={0};
	int i,j=0;
	for(i=1;i<=H;i++)
	{
		j=bin(l[i].start-1);
		X[i]=X[i-1]>X[j]+l[i].val?X[i-1]:X[j]+l[i].val;
    }
printf("%d\n",X[H]);
}
int main()
{
	int t,q=0;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		char c[202];
		scanf("%d",&n);
		scanf("%s",c);
		int count=0;
		int so=0,sw=0;
		int max=-1;
		int i;
		int S=1;
		for(i=0;i<n;i++)
		{
			count=0;
			int mark=i;
			sw=0;
			so=0;
			if(c[i]=='0')
			{
				so++;
				count=0;
			}
			else
			{
				sw++;
				count=1;
			}
			for(int j=i+1;j<n;j++)
			{
				if(c[j]=='1')
					sw++;
				else
					so++;
			            if(sw>so)
				{
					count=j-i+1;
					mark=j;
				}
    		}
		if(count!=0)
		{
	 	 l[S].start=i;
		 l[S].end=mark;
		 l[S].val=count;
		 S++;
		}
	}
	H=S-1;
     sort(1,H);
 best();
}
return 0;
}

W sumie są dwie możliwości.
Albo jest błąd w teście, albo jeżeli ilość wierzchołków i krawędzi jest jednakowa (tak jak w tym teście) to trzeba pierwszą daną wziąć za obydwie wartości.