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-26 17:52:26 HWK
@Piotr: Did it O(c) with Ruby and Python but far away from C O(n).
I guess this algo with C shouldn't require 317 bytes. ;-) Would you try it?

After solving it O(c) I think: Definitely don't change the task.

Last edit: 2011-07-26 18:13:07

2011-07-25 17:42:31 HWK
A different solution could be to make a new task which forces a O(c) answer. Then the time I put in my code wouldn't be useless. ;-)

2011-07-25 17:28:04 Piotr KÄ…kol
Hint - It's not about algorithm.

Increasing tests - I also thought giving C some chances is ok but we'll e what other users think.

2011-07-25 16:54:52 HWK
@Piotr: Shortened again but I'm sure that's not the trick you used. So I'm awaiting your 151. :-(
Seems to become like DIFFSUMS. :-) Could you give a hint?

Last edit: 2011-07-25 16:58:09

2011-07-25 15:52:15 HWK
My opinion: At last a shortening task with good chances for C beating script languages though all languages can solve the problem. But in this task some slower languages perhaps with a longer code.
Hence I wouldn't change the task.
P.S.: I rather have a problem with tasks like NPRIME because you couldn't solve it with e.g. Perl despite a long but fast Perl solution because Perl is too slow in this case.

Last edit: 2011-07-25 15:57:25

2011-07-25 15:35:21 Piotr KÄ…kol
Should I change the tests so that Your algorithm got TLE?
In C it's indeed long but perhaps in other languages it'll take less chars.
...or maybe my formula is not the shortest one.

2011-07-25 13:40:00 HWK
@Piotr Kakol: Seems that O(c) is much longer but probably it is the only chance to solve it with a "slow language" like Python & Co.
Thus we are expecting you, hallvabo and Jander. ;-)

2011-07-24 09:20:12 HWK
Oh, I feared that.

2011-07-23 14:53:01 Piotr KÄ…kol
To make it clear there's a O(const) solution. ;-)

Shortening codes

BOARD - Counting red squares

Input

Output

Example