VennDiagrams | Topcoder Archive

Problem Statement

You are given an int N. Produce a bitmap drawing of any valid Venn diagram for N sets.

To avoid confusion, we will use the word classes to denote the N sets for which you are constructing the diagram. We will number the classes 0 through N-1.

Your task is as follows:

Choose the dimensions for the bitmap. It must be a rectangle with at most 50 rows and at most 50 columns.
For each class, choose a subset of pixels of the bitmap that will represent the class.
Color the pixels by assigning the color number (2^c1 + ... + 2^ck) to a pixel that represents the classes { c1, ..., ck }.

Additionally, the drawing must have some properties you would intuitively expect from a Venn diagram. In order to define these properties formally:

Imagine that we placed the bitmap onto an infinite grid of pixels of color 0.
Once we do that, let's say that a block denotes a set of pixels B on the infinite grid such that all pixels that do belong to B form a single nonempty 4-connected area, and all pixels that do not belong to B also form a single nonempty 4-connected area.

Your drawing must satisfy the following:

For each nonempty subset of classes, the pixels that represent all of them (including pixels that also represent some other classes) form a block.
For each subset of classes (including the empty set), the pixels that represent exactly all of them (and no other classes) form a block.

If the bitmap you constructed has R rows and C columns, return a int[] with 2+R*C elements: { R, C, color[0][0], ..., color[0][C-1], color[1][0], ..., color[R-1][C-1] }. Any valid solution will be accepted.

Definition

Class:: VennDiagrams
Method:: construct
Parameters:: int
Returns:: int[]
Method signature:: int[] construct(int N)
(be sure your method is public)

Notes

An area is 4-connected if we can walk from any of its pixels to any other, given that we are not allowed to leave the area and in each step we can only move up, down, left, or right by a pixel.

Constraints

N will be between 1 and 10, inclusive.

Examples

```
2
```
```
Returns: {9, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 2, 2, 2, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 2, 2, 2, 2, 0, 0, 0, 1, 1, 1, 1, 3, 3, 3, 2, 2, 2, 2, 0, 0, 1, 1, 1, 1, 3, 3, 3, 2, 2, 2, 2, 0, 0, 1, 1, 1, 1, 3, 3, 3, 2, 2, 2, 2, 0, 0, 0, 1, 1, 1, 1, 3, 2, 2, 2, 2, 0, 0, 0, 0, 0, 1, 1, 1, 0, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
```
The sample output is a bitmap with the traditional two intersecting circles: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 2 2 2 0 0 0 0 0 1 1 1 1 3 2 2 2 2 0 0 0 1 1 1 1 3 3 3 2 2 2 2 0 0 1 1 1 1 3 3 3 2 2 2 2 0 0 1 1 1 1 3 3 3 2 2 2 2 0 0 0 1 1 1 1 3 2 2 2 2 0 0 0 0 0 1 1 1 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Class 0 is represented by colors 1+3. Class 1 is represented by colors 2+3. Color 3 represents the intersection of the two classes. Color 0 represents the elements that do not belong into either class.
```
3
```
```
Returns: {12, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 2, 2, 2, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 2, 2, 2, 2, 0, 0, 0, 1, 1, 1, 1, 3, 3, 3, 2, 2, 2, 2, 0, 0, 1, 1, 1, 1, 7, 7, 7, 2, 2, 2, 2, 0, 0, 1, 1, 1, 5, 7, 7, 7, 6, 2, 2, 2, 0, 0, 0, 1, 5, 5, 5, 7, 6, 6, 6, 2, 0, 0, 0, 0, 0, 5, 5, 5, 4, 6, 6, 6, 0, 0, 0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
```
As you certainly expected, the second example output is a bitmap with three overlapping circles. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 2 2 2 0 0 0 0 0 1 1 1 1 3 2 2 2 2 0 0 0 1 1 1 1 3 3 3 2 2 2 2 0 0 1 1 1 1 7 7 7 2 2 2 2 0 0 1 1 1 5 7 7 7 6 2 2 2 0 0 0 1 5 5 5 7 6 6 6 2 0 0 0 0 0 5 5 5 4 6 6 6 0 0 0 0 0 0 4 4 4 4 4 4 4 0 0 0 0 0 0 0 4 4 4 4 4 0 0 0 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.