11063  B2Sequence
Moderator: Board moderators
11063  B2Sequence
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.
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.
Re: 11063 B2Sequence
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 B2sequence must be an increasing sequence.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.

 Experienced poster
 Posts: 111
 Joined: Mon Jan 09, 2006 6:19 pm
 Location: Tehran, Iran
 Contact:
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.
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.

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Don't forget to check if the sequence is positive and strictly increasing. If it's not, it's not a B2seq.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 B2sequence otherwise it is B2seq. any suggestions?

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

 Experienced poster
 Posts: 111
 Joined: Mon Jan 09, 2006 6:19 pm
 Location: Tehran, Iran
 Contact:
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.

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Check this part:arsalan_mousavian wrote:i am still getting WA , any suggestions ?
main() wrote:.........if ( !i ).........< shouldn't it be if ( i ) ?
.........{
............if ( p[i] <= p[i1] )
...............ok = 0 ;
.........}
.........else
............if ( p[0] < 1 )
...............ok = 0 ;.

 Experienced poster
 Posts: 111
 Joined: Mon Jan 09, 2006 6:19 pm
 Location: Tehran, Iran
 Contact:
Some IOs..... please
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
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..n1 and j=i..n1
(I have a boolean array with sums, I initialize it every time)
What am I missing here?
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..n1 and j=i..n1
(I have a boolean array with sums, I initialize it every time)
What am I missing here?
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 B2Sequence.\n");
} else {
System.out.println("Case #" + (tc++)
+ ": It is not a B2Sequence.\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();
}
}