ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1003. Parity

1003
Posted by WuLF 8 Jan 2006 10:37
How to solve problem 1003? Please help.
Re: 1003
Posted by Burunduk1 9 Jan 2006 02:54
One of many ways to solve it:

- There is graph. k-th vertex is interval [1,k]
- Each vertex has its color (white or black).
- <L R odd> means L-th and R-th vertices have
  different colors.
- <L R even> means L-th and R-th vertices have
  same colors.
- You have to find contradictions.

It's simple to do it in O(n^2).
Re: 1003 !!!
Posted by Igor E. Tuphanov 9 Jan 2006 08:20
I solved this problem exactly this way, but used BSearch to find ans answer (cause sequence looks like: yes yes ... yes no no ... no). But got WA#1!!!
Re: 1003 !!!
Posted by Victor Barinov (TNU) 9 Jan 2006 13:21
Read forum! There is a multiply input in this problem.
Re: 1003 !!!
Posted by Igor E. Tuphanov 10 Jan 2006 06:38
I made a multiple input. That's not the problem.
Someone wrote about some bugs in tests. ???
Or maybe because of multiple input fitst test is very large and tricky. Don't know. My solution looks fine.
I'll download tests from CEOI'99 and test all of it.
Fix it up for the next contestants!
Posted by Igor E. Tuphanov 11 Jan 2006 15:29
Very very bad.
I found bug. Stupid bug, because of n == 0. Just one byte to fix up...

BUT!
That's from statement:
"In the second line, there is one POSITIVE integer which is the number of questions asked and answers to them".
Fix it up, please.

One more but, it would be better to see in FAQ:
How to enlarge stack size on C++ in a source code?