SPOJ.com - Problem BOARD

Problem hidden

This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

BOARD - Counting red squares

Your task is to count all red squares from defined area in the following infinite board:

Counting red squares

Input

The input consist of unknown number of tests. Each of them contain one line with four integers x1, y1, x2, y2 (0<=all<1000001). The first two are the coordinates of the bottom left corner of the rectangle and the last two are the coordinates of the top right corner of the rectangle.

Output

For each test print one line with the number of red squares that the rectangle contains.

Example

Input:
0 0 2 2
2 1 4 3

Output:
3
2

Submit solution!

Added by:	Piotr Kąkol
Date:	2011-07-14
Time limit:	5s-10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: SCM qobi
Resource:	Copy of Michael Suchacz's task: DCZPROST

hide comments

2011-07-30 16:28:26 Piotr KÄ…kol
@HWK - Yup, three byte less from Your new code and new Ruby record. ;-)
One variable less and You'll reach this score. ;-)
Think of a variable which is not so important. ;-)

2011-07-30 11:06:47 HWK
@Piotr: Thanks! But my 125 bytes solution seems to be not your one. I guess you could shorten it again 1 byte.

2011-07-30 10:15:42 Piotr KÄ…kol
@HWK - If You want to reach 125 with Your code (123 is hallvabo's algorithm) I suggest removing one variable. ;-)

2011-07-30 09:19:28 HWK
@Piotr: I meant two of the used Ruby-methods. Sorry, I guessed you'd understand the hint if you look at my code. Does the improvement apply to them?
Did you change my algo or implement hallvabos?

2011-07-29 23:27:30 Piotr KÄ…kol
@HWK - To 125 - without (X=changing the algo).
123 - with X.

BTW, what m..s is?

2011-07-29 21:54:07 HWK
@Piotr: Sure! Again like DIFFSUMS.
What's your trick? Does it apply to the m..s?

2011-07-28 10:39:17 HWK
@hallvabo: This implies that your solution is much, much simpler than my Python one. I assumed my solution on my last comment.
Congrats: You found the Bash trick after all. :-)

Last edit: 2011-07-28 10:42:07

2011-07-28 02:06:56 Hallvard Norheim Bø
@HWK: I'm not sure that Ruby will beat Bash here, and I also think Perl will do well. But that's up to Jander to show ;)

Regarding my Bash solution, it's possible to cut at least 10 bytes by rewriting the algorithm to be more suitable for a stack machine. As it stands now, it's a straightforward translation of my Python solution.

Last edit: 2011-07-28 02:09:21

2011-07-27 14:27:56 HWK
@Piotr: I guess this isn't a good task for Perl or Bash. Probably hallvabos algorithm with Ruby could be the shortest solution. Perhaps you want to show it? ;-)

Last edit: 2011-07-27 14:31:05

2011-07-27 10:51:12 Piotr KÄ…kol
Your were right. O(c) in C can be shorter.
And You were right again - Python has beaten C so everything seems ok. :-)
We'll se which place will Perl and Bash reach. ;-)

Shortening codes

BOARD - Counting red squares

Input

Output

Example