JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Linden Lab OpenJPEG
Problem: J2KDecode

Problem Statement

     JPEG 2000 is an image format meant to be an improvement over the original JPEG format. Linden Lab, the creator of Second Life, uses this file format heavily via the OpenJPEG library, an open source project. While these images have very good image quality for their file sizes and can be decoded as they stream across a network channel, a drawback has been that they are computationally expensive to decode. Because almost all of the textures in Second Life are encoded via JPEG 2000, the decode performance is very important to millions of Second Life users. Your task in this problem is to build on the OpenJPEG library, improving its decode speed. Winning solutions may be incorporated into the OpenJPEG library codebase.



Implementation Details

You must write a program which takes N images at a time, decodes each of them to a bitmap, and returns the results. The image will be given to you as a int[], representing that concatenation of the N files, where four bytes are backed into each element (if the number of bytes is not divisible by four, the file is padded with 0's). You are also given the lengths of the N files (before padding). After decoding all of the images, you should return a single int[], each element of which corresponds to a single pixel in an image, where each channel is represented by 8 bits of the element. The pixels should be packed in row-major order, and the N images should simply be concatenated in the same order they were given to you. See the sample code for an example of exactly how this unpacking and packing should be done. Note that we will always by using exactly three channels from the decoded image (even though they sometimes claim to have more).



Sample Solution

To help you get started, a sample solution is available which wraps the OpenJPEG library with the necessary code to work with the TopCoder system. This archive contains the relevant .C and .H files from the OpenJPEG library. For more information about this sample solution, go to http://www.topcoder.com/contest/problem/J2KDecode/code.html. Minor changes have been made to the original code so that it will compile using g++, but it is essentially version 1.3 of the OpenJPEG Library.

Sample Images

A corpus of available images is available for download. The example tests use subsets of these images. The provisional and final testing use a different set of images, but with similar properties.

Scoring

Your program will be evaluated primarily on its runtime. If you return exactly the same bitmaps as the current library, your score for a test case will be exactly your runtime. However, it is acceptable for your images to differ slightly from the original library, in the interest of runtime. We will compute your mean squared error (MSE), evaluating each channel independently. If your total time is T, your score will be T*exp(10*MSE). Your overall score will be the sum of the inverses of your individual scores, times 1000.
 

Definition

    
Class:J2KDecode
Method:decode
Parameters:int[], int[]
Returns:int[]
Method signature:int[] decode(int[] data, int[] lengths)
(be sure your method is public)
    
 

Notes

-N will be 50 in all cases except the examples.
-Only C/C++ is allowed.
-Your solution must not contain any instructions newer than the appearance of SSE3. While such solutions may compile, they will not be eligible for prizes.
-The time limit is 30 seconds per test case.
-The memory limit is 512MB.
 

Examples

0)
    
N = 1
This example contains only one image, 6e8c0621-d300-1dbb-a6b2-15bd69f8d2f4.j2c
1)
    
N = 2
This example contains two images:

6e8c0621-d300-1dbb-a6b2-15bd69f8d2f4.j2c

e5debb46-54b9-a424-1436-12c2b13aaa44.j2c

2)
    
N = 4
6e8c0621-d300-1dbb-a6b2-15bd69f8d2f4.j2c

e5debb46-54b9-a424-1436-12c2b13aaa44.j2c

caaa90c5-8e30-84dc-e9c3-669e3344eb34.j2c

a3445c83-e2c3-63c2-3408-7decee204a51.j2c

3)
    
N = 10
6e8c0621-d300-1dbb-a6b2-15bd69f8d2f4.j2c

e5debb46-54b9-a424-1436-12c2b13aaa44.j2c

caaa90c5-8e30-84dc-e9c3-669e3344eb34.j2c

a3445c83-e2c3-63c2-3408-7decee204a51.j2c

1bafcd0a-eaf6-ee3b-d4a3-0b1ec8ce674e.j2c

eb6b748f-a5a3-7698-6fb5-716f2b3cd77d.j2c

70a2573b-f923-5cf7-a6ef-e21c36a97a96.j2c

a49ee1d7-1cbb-b24b-46d1-f7eb53f8e7ba.j2c

5665b17c-9a92-86ab-4aa6-d2d5f5f22422.j2c

247d58cd-9b24-6bde-090a-d4c76a42092f.j2c

4)
    
N = 20
6e8c0621-d300-1dbb-a6b2-15bd69f8d2f4.j2c

e5debb46-54b9-a424-1436-12c2b13aaa44.j2c

caaa90c5-8e30-84dc-e9c3-669e3344eb34.j2c

a3445c83-e2c3-63c2-3408-7decee204a51.j2c

1bafcd0a-eaf6-ee3b-d4a3-0b1ec8ce674e.j2c

eb6b748f-a5a3-7698-6fb5-716f2b3cd77d.j2c

70a2573b-f923-5cf7-a6ef-e21c36a97a96.j2c

a49ee1d7-1cbb-b24b-46d1-f7eb53f8e7ba.j2c

5665b17c-9a92-86ab-4aa6-d2d5f5f22422.j2c

247d58cd-9b24-6bde-090a-d4c76a42092f.j2c

a16b769e-bb7e-10e0-d612-83ec36024680.j2c

3b9e2ee1-3281-5a8f-c507-e3b07b284cec.j2c

058bb03b-0f93-e4e8-f2fa-648177fbe98c.j2c

f964c02a-5b5f-9d4d-1c01-4d096cad5e3f.j2c

73f161b9-dbc7-0097-4d9c-559e57847d8e.j2c

11852d78-d0a0-23ff-9fc1-7f8ac9e14d81.j2c

369476a8-2b3a-b756-fbc4-b0351a5dfdf6.j2c

58644b90-f4ef-0672-a7e0-0b91fe104d8e.j2c

5eb7c1a8-5bdf-3b6e-cf50-45d823f2236c.j2c

b342da3f-20e7-6c5e-fcea-b530f014f191.j2c

5)
    
N = 50
6e8c0621-d300-1dbb-a6b2-15bd69f8d2f4.j2c

e5debb46-54b9-a424-1436-12c2b13aaa44.j2c

caaa90c5-8e30-84dc-e9c3-669e3344eb34.j2c

a3445c83-e2c3-63c2-3408-7decee204a51.j2c

1bafcd0a-eaf6-ee3b-d4a3-0b1ec8ce674e.j2c

eb6b748f-a5a3-7698-6fb5-716f2b3cd77d.j2c

70a2573b-f923-5cf7-a6ef-e21c36a97a96.j2c

a49ee1d7-1cbb-b24b-46d1-f7eb53f8e7ba.j2c

5665b17c-9a92-86ab-4aa6-d2d5f5f22422.j2c

247d58cd-9b24-6bde-090a-d4c76a42092f.j2c

a16b769e-bb7e-10e0-d612-83ec36024680.j2c

3b9e2ee1-3281-5a8f-c507-e3b07b284cec.j2c

058bb03b-0f93-e4e8-f2fa-648177fbe98c.j2c

f964c02a-5b5f-9d4d-1c01-4d096cad5e3f.j2c

73f161b9-dbc7-0097-4d9c-559e57847d8e.j2c

11852d78-d0a0-23ff-9fc1-7f8ac9e14d81.j2c

369476a8-2b3a-b756-fbc4-b0351a5dfdf6.j2c

58644b90-f4ef-0672-a7e0-0b91fe104d8e.j2c

5eb7c1a8-5bdf-3b6e-cf50-45d823f2236c.j2c

b342da3f-20e7-6c5e-fcea-b530f014f191.j2c

33ff9a2d-4542-54b5-0571-deeccdf6a738.j2c

b7dba3d6-3eeb-31e8-25a8-0bb0c443e9dc.j2c

301cf66f-759a-3e8e-b2a9-4039b4d26d5d.j2c

405dd03a-ff83-1946-ab35-41e738005b88.j2c

3d2baf12-549b-75b1-b5b1-c06f25d372ab.j2c

caaeff25-6751-7104-6619-887403ff3c6f.j2c

69a79bb7-9a94-c265-dba1-0581bddfed9b.j2c

c60df22e-b37a-a7f4-7197-19fe60e29633.j2c

e078639f-c1fc-89d1-0735-fcb3c1bf2936.j2c

915f8276-450f-b8e1-51ed-fa1a091e22cb.j2c

3b29a892-58e2-424e-2c4e-30008cf203f7.j2c

f7655f2a-a4fc-d6ba-b5b5-e284ec2153e0.j2c

b076848a-39c9-9bf7-73e0-5808d794efaf.j2c

ef03448b-599f-de36-43f9-7dad75ac721e.j2c

3fe4c904-bac8-7bb1-81cf-51a3891252b9.j2c

44ef05d2-87c4-ac63-020a-576b0749bba4.j2c

f7f6564c-ff8f-fcb0-11f4-3a6a2b758013.j2c

dbc52174-e52a-6e33-5e48-e4b6e7c65228.j2c

0d4f9a9e-2b7c-e8c1-9522-2cff5c819a81.j2c

77a6734c-d3bd-6249-5a26-53322c5f757f.j2c

3a7c8d98-79d9-c0ef-1a13-a7cffbcb8380.j2c

968cfe31-46fc-db8d-940f-daa69c336e72.j2c

0cf5c667-0532-80b2-6c6d-0d3bf04112f8.j2c

4bbb7416-d0e2-e9cc-6687-c8dcc9451c81.j2c

05282b30-1076-d294-553b-342a58d396e6.j2c

9339d4df-99ea-3265-14b8-df7bba267c5f.j2c

e49275b1-1236-0280-9878-fdb3814821a6.j2c

2a795955-9b48-ec3a-98ac-3e67059c13d8.j2c

38d73189-65fa-ac60-7d14-57c05148d7ef.j2c

7c18f224-5428-6c67-975e-bb24eb07a203.j2c

6)
    
N = 50
800aba69-2355-21da-2b71-b6b0ab71c2d1.j2c

eb816ff1-0b82-e803-d6f6-10ca843f485a.j2c

2d77b067-3eb2-5971-6500-17f7d7135135.j2c

c8bf695c-0261-9f07-6835-de4da526ca69.j2c

f17a8f59-ea61-f50b-3d89-adb214b10b67.j2c

a020e7e3-0d38-b6a5-cff9-1e6951c24260.j2c

179fc671-7942-af3c-9ed8-cf71b91a7670.j2c

8aaf9de7-18aa-ae4b-3523-b2a2031b5ad1.j2c

92d52990-9eca-b166-1bba-6dfbcd7a8b8a.j2c

944fa83b-5882-7a97-8e08-563e498c4ff2.j2c

fc75013a-d3a6-32e1-bae8-ca3b7119ed19.j2c

8d3342cc-7ce0-669f-0564-fd9bdc5d6957.j2c

3fa3a143-5375-d18d-2531-121f92b9dd48.j2c

ba96e410-f3d9-c46c-0a6d-35ef0cb90fec.j2c

b4c5575f-b95e-896e-a113-0035fc57d801.j2c

a4ba7d71-c4fc-2968-cd66-aa98f0c4e987.j2c

e9e9cef9-866c-ed96-0129-e53941ce6bf2.j2c

a43a6107-6a7d-cc62-49f3-4f767b5566af.j2c

b4cd03c2-73e2-10f6-cc19-31e8466fabae.j2c

55e91c9b-2cff-ff07-f5ef-96974392e8a0.j2c

d090244e-5ee3-01aa-dc44-c0d40ac99078.j2c

dc415cc1-59ab-e462-1946-81956976fbfc.j2c

83a770d1-762e-96b8-d8a4-e82fbbe57242.j2c

636aace7-c514-f6c1-ac56-d0681235da72.j2c

93e1b75d-a948-0512-1130-55e8642700bf.j2c

7e242195-00b6-9073-0328-cd7019f150d4.j2c

361a6c8c-0036-0160-073e-4edc4dbfb808.j2c

0d4172c0-0c12-7f91-1bab-08a24095e5b0.j2c

71700898-0592-01f3-f329-d3a6cf8a69fd.j2c

c13d1f39-0af1-ebca-2646-64c0106d0a9f.j2c

0ab1cefe-cef7-8316-7b83-f64f86c1d1d9.j2c

d68b1fb4-09c0-2ba0-b995-c745bb17686b.j2c

6dc904d3-da47-6e7a-30e3-53d8b3f0623c.j2c

c23f5163-20b6-2353-b017-c1ae60732d38.j2c

fb560f05-4106-4555-387b-398790a586cc.j2c

b8768743-065f-a5da-163f-dfa11f4c2485.j2c

10535949-314c-e128-aee7-626951900125.j2c

ed909fa1-9d2e-3e4d-356f-e83562a5e2d2.j2c

42588ac8-acee-f3eb-4904-2a835a7e6063.j2c

44d12636-7f00-549b-c840-d9f899bbb629.j2c

8f1cbf87-9449-fa18-78f1-c21db721edde.j2c

f4e4e808-eda8-4c39-81d6-e4875cb23ae8.j2c

86936c9b-90ea-2ba0-3e79-6cd7df53c01e.j2c

52f39070-d23e-1004-ed0a-b95abe8d56c2.j2c

5ced7e64-d7c7-86b1-3615-d11e45193932.j2c

9be14607-a31d-6764-a06c-2b7491b0d585.j2c

05bc8709-856f-cb28-685f-a792dfccba1c.j2c

9790e003-3bb2-4852-c9e8-b7c52d13e16c.j2c

779153e2-d3da-4b65-5d22-c8128802bc34.j2c

51cfae74-da19-a642-f1c9-ca8be0cf31f4.j2c

7)
    
N = 50
f94b2d1f-413a-e1da-1361-a4738f6ac06b.j2c

03f11859-8172-93e6-40bc-867cf39731cb.j2c

184ce25a-8c2e-25cc-1128-9a6c2a4c0317.j2c

088f16ad-9d4f-dd39-92e9-ab2ee11b0806.j2c

7e1c096f-1634-ca73-5435-51c8e2598752.j2c

3c898ac5-29bd-d8fd-9228-3adb818576b2.j2c

054ea304-d348-e443-4748-6f3a6269454d.j2c

a4bc12a4-f894-0f6c-b86a-c2217db5a3b2.j2c

cea552b2-2fc6-53c0-8a33-75af20c7122a.j2c

451f7ae0-2b66-fe5f-93de-af338af0833a.j2c

886624b4-53f5-481b-9847-7db4b97115df.j2c

c3371090-ba05-9662-9724-bfe349e5fd16.j2c

2fa7cad6-8062-c538-3413-b3db7adbba61.j2c

1766d727-9c9d-7de9-de26-3d4483d7d66d.j2c

d82b8406-dded-dff6-7ed3-fafc9359b189.j2c

8020bc84-4086-93e5-8698-a3e9cd4a3473.j2c

2d104761-345f-9b59-e65e-608752251d1c.j2c

113f0482-60ee-786e-d04c-54bc6032921f.j2c

5d3f35bf-fbbe-1749-96b7-6817cf85cf12.j2c

e7816c15-d73a-b055-8328-c4dc4e698911.j2c

4d5f938d-bb2b-59a2-02e6-b491e06daf91.j2c

e0ed39cb-d702-9f97-15f9-ed8e42c0f4ad.j2c

ff87f93b-a0b5-f93f-998a-ee8f0ad194f7.j2c

d043338a-98d0-455d-1b0e-d40287cd149a.j2c

70ce6a02-e194-5702-ba74-8aa4c2d3ca16.j2c

8e4a1540-284f-a4bf-0b32-675554a1a5d4.j2c

39b318dc-bae4-3567-0802-af0878d38e0f.j2c

da5e658b-7a7a-dbae-e445-0db0769f64a8.j2c

7e5a44d6-c63a-ecba-6237-e2ec65029f21.j2c

cca1b3ae-a475-9592-d324-ccbe3ee5b556.j2c

7e78c80b-2583-42c9-ab09-3fa1b4efb147.j2c

26e1f9c3-3f8b-9706-0675-08f15a33df4d.j2c

59d014f1-f2c1-3c55-801f-93b1acab2a9c.j2c

417f1921-952b-b227-9318-8b7f1e55202f.j2c

7dc61191-384a-3387-7601-6932bfe4efc0.j2c

e87f53cf-ba85-9586-6669-2fd01b4e5603.j2c

a295dd41-c9f5-71cc-a183-5efe430bdd83.j2c

bfc04202-3ff2-9229-7ba0-9489fa505943.j2c

f0f8b2da-1f10-8447-bc7c-05d25be0e7c9.j2c

4c79cf48-94ab-302c-aca8-2807ea448041.j2c

1ca2ceed-31f7-0fb6-ce37-30aacb613288.j2c

6b642f63-59da-664f-4ab9-94141e6ad4a3.j2c

c67735e4-b6cc-75b5-0309-0a7c7ea26b91.j2c

8265fe5f-42bf-d0ea-c1c3-17719f373299.j2c

e041ed12-b317-826f-3a78-1fb7c436b9c5.j2c

02fbb041-899a-ad00-4f68-f2d55a723652.j2c

013b1885-35ea-7c9b-4124-d69545e5fce3.j2c

a603eec6-c608-50d7-2b38-97b991519863.j2c

eae45662-897d-e07f-2d4a-487bbc826315.j2c

ac1bdbc2-072c-7ef9-2c49-60cb54bd7ce7.j2c

8)
    
N = 50
da63ab42-2402-a506-b853-e4a8f79f5f75.j2c

846b4195-d056-c8b8-7026-f7364348a7e6.j2c

40340512-336b-add8-40f0-342142a22324.j2c

7e48664d-2d06-5886-bca5-a923b51c0e78.j2c

27b7f7d0-4dbf-990b-47df-8d34d17efcc8.j2c

b3badb0d-af78-306f-d116-aabf0ccaa774.j2c

1691f557-cda8-9c43-706f-df1a10320435.j2c

912ad4a9-99f2-c19b-dbdd-3fe50822f46f.j2c

0d74e852-d9aa-d949-1fc1-9b1a7a648ef3.j2c

07b45cb4-0c4c-b0d0-6b66-c6e07a96e753.j2c

9bbfc7d1-b5b8-9f84-2ce2-5c5bcd6e5e7c.j2c

e1a49d20-0033-2681-75bf-5891f4594f47.j2c

9b22af8f-c873-4585-6325-33adabe5fb16.j2c

45993e05-e516-9407-864d-30fffcf6a68e.j2c

82cc678f-8aa2-7f15-5056-3fe27d334291.j2c

6538605c-189a-55e2-f5d0-d3599e78e32b.j2c

f6194989-0e8b-aca3-91bc-def8fa29b088.j2c

9206ea7c-2a2f-9364-0503-bc9c887f609c.j2c

f063a05d-b6ff-a00a-f3f6-8e2749c63de3.j2c

8e77cbf3-143e-b912-4275-944853435a60.j2c

779830ec-2d59-7a32-5811-9e7c05f42393.j2c

02709ae4-6cb1-31e9-6bef-37169f17ef6f.j2c

3cf73958-5e3c-075f-97e2-49815956c744.j2c

9a2beee5-9ab9-c9b1-650a-db2ff21427b1.j2c

47d16df5-140f-82a2-2ade-d77ff3e625c8.j2c

8c45937b-f901-1a12-a936-51c60e3f778b.j2c

896048e3-8e33-fbed-8181-f15366b79140.j2c

c09b3b2d-d907-7bbd-e1a4-a344b0dece4e.j2c

632f4f85-58fc-d7b7-086b-e07a8ffb50e1.j2c

b65534bc-8a10-ffb5-92f2-6b7c0c7a2a03.j2c

cc0eeba9-4a06-5925-335d-c5162563c369.j2c

62e26adf-bf89-bd1b-a4d0-f45a3bc7c789.j2c

9223e838-457b-ae58-2d81-b25ee9d7cd0e.j2c

56a7bcec-130e-73e8-9dd2-5d34891efa52.j2c

527e0079-2cf4-199e-9f39-372cefcfacbf.j2c

b2e28d68-49c7-b866-5dcc-89687d9997e1.j2c

64bb20b3-a808-1561-3ba1-723b1aea34ef.j2c

42176a56-c404-6d8d-6f8b-1c932d9dd36d.j2c

a2a71a2a-1330-43e2-e369-02d10280dc8f.j2c

01c8f524-77f0-ff4c-4f46-cf95af628ffa.j2c

0742e7a3-e0e1-7be4-257b-0dd48a9bf1cf.j2c

0bfffaa7-4da4-a03d-68c1-4b147dee102a.j2c

602d6883-2da3-3aa3-6945-467546757e10.j2c

1eb0b190-3697-65c5-c0ab-b622e591d5ad.j2c

5042996a-23e1-c7c7-8784-b61e419ad2f2.j2c

a9dd094b-ecec-8767-1bc1-9886e6889b1e.j2c

20ddbd26-2c00-e4b9-b590-160dd9f57f37.j2c

b2921cf3-bdb1-39aa-ec4a-129b4923ed12.j2c

28a3d28f-89d8-888d-39e0-cda75eb225dc.j2c

47a0b98b-1b0a-4052-db8f-63956915db46.j2c

9)
    
N = 50
87611554-ea0c-ca32-73f4-c56d407a9196.j2c

e7adb3f7-f814-fa64-0394-d544aec45ad1.j2c

46dc13db-f838-f9ab-f5ea-0e42f6903733.j2c

9774081b-f663-b6ae-224e-ae143d77c1df.j2c

0896de41-b5ab-9a0f-6c0c-4945347ecc4d.j2c

eac99037-1cf0-242d-9f5c-a9ccced32a4c.j2c

a7d4ccdd-ce14-b9d4-076f-da841001d240.j2c

b29b2e79-3c62-4e39-f389-15ea7732331a.j2c

6c42d636-aebd-a4fb-9927-824f9c3d988a.j2c

1727bf77-79a7-187c-6282-0f24ec5460b0.j2c

374628a3-c88e-0f29-cda7-e7f6691f1f13.j2c

c9363abe-98b1-60cc-4e81-baba18b26819.j2c

363057d3-6253-7d09-1622-9dbe43a85702.j2c

d557b6fd-439d-5898-1427-7d7b81f59e92.j2c

bbe15ec7-4bc2-c262-169d-bd898dd6e382.j2c

8e36c470-0c66-4a4b-cab7-24b85f6017be.j2c

a208c691-c18a-008e-150b-6f72e0820063.j2c

6dd9d3f9-56e4-43d5-3ba2-7d8dacaaeb4b.j2c

dad7cee4-075c-c475-cf13-086e3946ecdb.j2c

03401dea-1685-3944-bd6e-7ff48b55fa59.j2c

1b339e2e-7f72-8775-4c1c-feafcae7d943.j2c

e4cdf170-5109-377e-ed67-bb0aae4e5e9d.j2c

9d9ab29a-9380-e47f-de62-a1b98ed25b8a.j2c

b285244a-41e3-8948-da9b-385b187c59fa.j2c

6675ef9d-cba4-32dc-890a-fce45c27a29f.j2c

9583b088-e0c4-a09b-9ff4-85dd9b6e9710.j2c

442b4d80-26c8-a5f9-10c3-b4d408a9df8a.j2c

3c9adea4-b0bd-e4d4-4400-726517623beb.j2c

9e540dcc-221b-6fe7-5b41-7b87eded528b.j2c

32216559-8513-9887-5136-3c9506c2563b.j2c

3e8c4999-5ddd-7277-cda8-bac86cfc2813.j2c

125f11fc-380a-8ac5-5a0e-7a7d932a9f67.j2c

35be984f-e55c-5b30-d8be-49986e5e70c6.j2c

fb6054b7-fc0e-5f7d-d338-fdcbda16f28a.j2c

1d514d27-a658-cf16-072e-8efc258d7f4e.j2c

dd4ed6b9-e0cc-40ab-7452-f50a53b64739.j2c

0022becf-1b77-032e-5ebf-c8275f982ed9.j2c

d9075e28-0cb6-cb76-eab5-4328d64d7faf.j2c

cc5dfcf5-a45d-2ae9-5aee-1aeb292321c3.j2c

5a146570-ec76-557d-7f65-c19c6d1b9e29.j2c

fb671e44-5e9b-421b-24cc-1b61676ee8e1.j2c

7b44ef96-5377-1101-d7c2-56446f294332.j2c

940eafbb-03a6-b667-b824-26dc8bf3d03f.j2c

4a7aeb24-cec8-1ec5-22cf-39f236318a2d.j2c

c0c99313-fa08-c76a-4bf8-d54ea91534cf.j2c

f40532fb-a888-2db2-7451-0eda62443f69.j2c

25428ccb-8e48-6da9-e27e-59ec0c07ce47.j2c

596db8b7-6b14-8c45-6625-9fa3b6cae98e.j2c

83611cbe-4ba9-c9d2-e7cf-d0f6e04baeb2.j2c

6ed19c24-caf4-b7a5-bb69-b7b9a8f213e4.j2c

10)
    
N = 50
11)
    
N = 50
12)
    
N = 50
13)
    
N = 50
14)
    
N = 50

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)2010, TopCoder, Inc. All rights reserved.