11063 - B2-Sequence

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

11063 - B2-Sequence

Post by Darko » Sun Aug 06, 2006 1:10 am

Ok, what is the trick in this one? I solved B by switching from Java to C and realizing that my WAs were actually RTEs (books with negative costs..sigh).

I was about to try to do that with this problem, too, but just ran out of patience.

Ok, I eventually realized that "pairwise" included sum of an element with itself (it was right there, but I chose to ignore it). But I really don't know what else is there in that statement that I misunderstood.

Clarification said something about bi being less than 1, but they never changed the "positive integers" part - I have no idea what to think of that.

User avatar
Mg9H
New poster
Posts: 18
Joined: Sun Oct 14, 2001 2:00 am
Location: Ohio University
Contact:

Re: 11063 B2-Sequence

Post by Mg9H » Sun Aug 06, 2006 1:12 am

Darko wrote:Ok, what is the trick in this one? I solved B by switching from Java to C and realizing that my WAs were actually RTEs (books with negative costs..sigh).

I was about to try to do that with this problem, too, but just ran out of patience.

Ok, I eventually realized that "pairwise" included sum of an element with itself (it was right there, but I chose to ignore it). But I really don't know what else is there in that statement that I misunderstood.

Clarification said something about bi being less than 1, but they never changed the "positive integers" part - I have no idea what to think of that.
Well, I got plenty of WAs until I read the clarification, I added the code to check whether the elements are >= 1 and got AC. Also remember that a B2-sequence must be an increasing sequence.

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Sun Aug 06, 2006 2:06 am

Hi , i got many WA s on this problem , i store all the sums in a set , and for each i and j that i<=j check whether their sum is in set or not , if so it is not B2-sequence otherwise it is B2-seq. any suggestions?
In being unlucky I have the record.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Sun Aug 06, 2006 2:12 am

1<=b1<b2<b3 , doesnt it mean that a b2 seq should have a 1 in the front element ? it says that 2<=n<=100.
fahim
#include <smile.h>

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Aug 06, 2006 2:12 am

DO NOT assume that the input sequence is strictly increasing and its first element is >= 1.
You have to verify these conditions! If any of them is violate, the sequence is not a B2 sequence by definition.
Last edited by mf on Sun Aug 06, 2006 2:12 am, edited 1 time in total.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun Aug 06, 2006 2:12 am

arsalan_mousavian wrote:Hi , i got many WA s on this problem , i store all the sums in a set , and for each i and j that i<=j check whether their sum is in set or not , if so it is not B2-sequence otherwise it is B2-seq. any suggestions?
Don't forget to check if the sequence is positive and strictly increasing. If it's not, it's not a B2-seq.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun Aug 06, 2006 2:15 am

smilitude wrote:1<=b1<b2<b3 , doesnt it mean that a b2 seq should have a 1 in the front element ? it says that 2<=n<=100.
No, b1 does not have to be 1. For instance "2 3" is a B2-seq, too.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Sun Aug 06, 2006 2:16 am

no I was wrong! it doesnt mean that input starts with a 1! :o
got ac!
fahim
#include <smile.h>

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Sun Aug 06, 2006 2:23 am

i am still getting WA , any suggestions ?

Code: Select all

now i know why i got WA :)
}
Last edited by arsalan_mousavian on Sun Aug 06, 2006 2:28 am, edited 1 time in total.
In being unlucky I have the record.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun Aug 06, 2006 2:26 am

arsalan_mousavian wrote:i am still getting WA , any suggestions ?
Check this part:
main() wrote:.........if ( !i ).........<-- shouldn't it be if ( i ) ?
.........{
............if ( p[i] <= p[i-1] )
...............ok = 0 ;
.........}
.........else
............if ( p[0] < 1 )
...............ok = 0 ;.

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Sun Aug 06, 2006 2:29 am

thanks a lot , you know it is about 4AM here and i made this silly mistakes
In being unlucky I have the record.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Some IOs..... please

Post by nymo » Sun Aug 06, 2006 6:13 am

I know it should be some simple mistakes..... but I can't find it. Can you provide some IOs? I 've checked all the cases you have mentioned, but still WAs :roll:

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sun Aug 06, 2006 7:23 am

I am with you there, nymo, I just recoded it and got WA again. I think my program crashes, but I am not sure why it should.

I check three things:
- b is in the range (1 <= b <= 10000)
- b < b[i+1]
- all (b+b[j]) are unique, where i=0..n-1 and j=i..n-1
(I have a boolean array with sums, I initialize it every time)

What am I missing here?

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Sun Aug 06, 2006 7:35 am

I checked the followings:
i. number[0] is >= 1 else not a B2-seq
ii. number [i + 1] > number else not a B2-seq
iii. using a boolean array checking for uniqueness :)

I must be missing something, too. But what is that?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sun Aug 06, 2006 7:40 am

I just recoded this in C and it worked. Here's my Java solution that I couldn't get accepted (I have no idea what's wrong - a few people got it in Java today):

Code: Select all

import java.io.IOException;
import java.util.StringTokenizer;

class Main {
	int[] b = new int[110];
	void work() {
		String line;
		StringTokenizer st;
		int tc = 1;
		while ((line = readLine()) != null) {
			if (line.length() == 0)
				continue;
			int n = parseInt(line);
			line = readLine();
			while (line.length() == 0)
				line = readLine();
			st = new StringTokenizer(line);
			for (int i = 0; i < n; i++) {
				b[i] = parseInt(st.nextToken());
			}
			boolean[] seen = new boolean[20020];
			boolean ok = true;
			if (b[0] < 1)
				ok = false;
			if (ok) {
				for (int i = 0; i < n; i++) {
					if (b[i] > 10000 || (i < n - 1 && b[i] >= b[i + 1])) {
						ok = false;
						break;
					}
					for (int j = i; j < n; j++) {
						int sum = b[i] + b[j];
						if (seen[sum]) {
							ok = false;
							break;
						}
						seen[sum] = true;
					}
					if (!ok)
						break;
				}
			}
			if (ok) {
				System.out.println("Case #" + (tc++)
						+ ": It is a B2-Sequence.\n");
			} else {
				System.out.println("Case #" + (tc++)
						+ ": It is not a B2-Sequence.\n");
			}
		}
	}

	private String readLine() {
		StringBuffer sb = new StringBuffer();
		int b = 0;
		while (b != '\n' && b >= 0) {
			try {
				b = System.in.read();
			} catch (IOException e) {
				return null;
			}
			if (b != '\r' && b != '\n' && b >= 0)
				sb.append((char) b);
		}
		if (sb.length() == 0 && b < 0)
			return null;
		return sb.toString().trim();
	}

	private int parseInt(String s) {
		// what if s.length() == 0 ?
		int result = 0;
		int sign = (s.charAt(0) == '-') ? -1 : 1;
		if (sign == -1)
			s = s.substring(1);
		if (s.charAt(0) == '+')
			s = s.substring(1);
		int i = 0, max = s.length();
		if (max > 0) {
			while (i < max) {
				result *= 10;
				result += s.charAt(i++) - 48;
			}
		}
		return sign * result; // could be 0 if not an integer
	}

	public static void main(String args[]) {
		Main myWork = new Main();
		myWork.work();
	}
}

Post Reply

Return to “Volume 110 (11000-11099)”