Time Limit: 600 sec / Memory Limit: 8000 MB
問題文
アメリカ大陸の一部を 5 分おきに観測したデータが 4 観測分あります。 データは光の波長によってデータが別れていて 16 チャネルあるので、合計で 64 個の衛星データファイルがあります。
このデータ全てを可能な限り圧縮するプログラムと、解凍を行うプログラムを、同一のソースコードで作成しなさい。
問題文補足
- 与えられるデータについての情報は、問題文下部の参考情報にて与えられます。
- 与えられる 64 個のデータには関連があり、データの差分を利用して圧縮することで、データファイルが小さくなることが期待出来ます。
提出プログラムの制約
- 可逆圧縮であり、採点データ以外の同条件の衛星データファイルも圧縮・解凍可能であること。
- アルゴリズムの利用にあたり、他の組織や人物に対して利用料を支払う必要がないこと。
- 圧縮フェーズと解凍フェーズを合わせて 600 秒以内に実行が終わる必要がある。なお、採点プログラムの実行時間（およそ 16 秒）もこれに含まれる。
入力
入力は、圧縮と解凍の2つのパターンが連続して与えられる。
圧縮フェーズでは、入力は以下の形式で与えられる。
encode UserEncodingFileName DirectoryName N file_1 fileSize_1 file_2 fileSize_2 : file_N fileSize_N
解凍フェーズでは、入力は以下の形式で与えられる。
decode UserEncodingFileName UnzipDirectoryName
入力の制約
- ファイル数 N = 64
- 入力で与えられる、
encode,decodeは、それぞれそのままの文字列であり、圧縮フェーズ・解凍フェーズの判別に使用する。 - UserEncodingFileNameは、圧縮ファイルを出力するべきファイルの絶対パスを指し、アルファベットまたはスラッシュで 50 文字以下の文字列であることが保証されている。
- DirectoryNameは、圧縮したいディレクトリの絶対パスを指し、アルファベットまたはスラッシュで 50 文字以下であることが保証されている。
- file_i は圧縮すべきファイルのファイル名を表し、半角英数またはハイフン、アンダースコア、ドットで構成された 100 文字以下の文字列であることが保証されている。
- fileSize_i ≦ 120,000,000, filesize_i の合計は 1,200,000,000 以下であることが保証されている。
- UnzipDirectoryNameは、解凍したいディレクトリの絶対パスを指し、アルファベットまたはスラッシュで 50 文字以下の文字列であることが保証されている。
出力
圧縮フェーズでは、指定されたファイル名の圧縮ファイルを 1 つだけ出力してください。 別名のファイルなどを作成した場合、採点は行われますが、後日、手動でのチェックにて削除されます。
誤って別ファイルを生成するプログラムを作成してしまった場合は、このコンテストの質問ページよりご連絡ください。
解凍フェーズでは、指定されたフォルダに、圧縮された全てのファイルを解凍しなさい。
スコアの算出方法
正しく圧縮・解凍が行われていた場合、圧縮率を 1,000,000 倍したものがスコアになり、その他の場合は 0 点となります。
入力例1
encode /AtCoder/ZipFile /AtCoder/Dir 3 fileA 100 fileB 100 fileC 200
- 圧縮フェーズの入力です。
/AtCoder/Dir/fileA,/AtCoder/Dir/fileB,/AtCoder/Dir/fileCの 3 つのファイルを圧縮し、/AtCoder/ZipFileというファイル名で出力してください。
入力例2
decode /AtCoder/ZipFile /AtCoder/UnzipDir
- 解凍フェーズの入力です。入力例1で与えられたファイルを解凍する場合、
/AtCoder/ZipFileから、/AtCoder/UnzipDir/fileA,/AtCoder/UnzipDir/fileB,/AtCoder/UnzipDir/fileCの 3 つのファイルを出力してください。
補足説明: 12月19日更新
圧縮率の算出について補足します。 算出には以下の式を用います。
1 - 参加者のアルゴリズムで圧縮されたデータのサイズ / bz2によって圧縮されたデータのサイズ※ただしbz2圧縮は-9オプションを指定した際のサイズで、ジャッジに用いられているデータを圧縮した場合は507,803,245bです
上記の式を用いて圧縮率を計算し、最も圧縮率が高いアルゴリズムを提出した参加者のみを受賞者として賞金が支払われます。受賞者の賞金の算定はbz2圧縮より圧縮率が高い場合に30万円、圧縮率が1%上がる毎に1万円が加算され、最大で100万円の賞金が支払われます。 また、本コンテストは既存のライブラリなどを用いて圧縮方式を試行するコンテストではありません。システム上Acceptが出ますが、コンテスト終了後に最終審査の段階で審査員がソースコードを読みRejectしますのでご了承ください。
衛星データについて
GOES(Geostationary Operational Environmental Sattellite)はアメリカ合衆国の静止気象衛星で、NOAA(Natonal Oceanic and Atmospheric Administration:アメリカ海洋大気庁)が運用を行っています。GOESはアメリカ大陸の東西に1機ずつ配置され、GOES-16は東側を担当するGOES-Eastとして2017年12月からの運用が予定されています。 衛星はABI(Advanced Baseline Imager)を用いてイメージャー/サウンダー観測を行います。観測データは波長ごと16のバンドに分かれていて、バンドによって解像度が異なります。各バンドの詳細は表を参照してください。
| バンド | 波長(μm) | 中心波長 | 解像度(km) | 画素数(x * y) |
|---|---|---|---|---|
| 1 | 0.45-0.49 | 0.47 | 1 | 5000 * 3000 |
| 2 | 0.59-0.69 | 0.64 | 0.5 | 10000 * 6000 |
| 3 | 0.846-0.885 | 0.865 | 1 | 5000 * 3000 |
| 4 | 1.371-1.386 | 1.378 | 2 | 2500 * 1500 |
| 5 | 1.58-1.64 | 1.61 | 1 | 5000 * 3000 |
| 6 | 2.225-2.275 | 2.25 | 2 | 2500 * 1500 |
| 7 | 3.80-4.00 | 3.90 | 2 | 2500 * 1500 |
| 8 | 5.77-6.6 | 6.19 | 2 | 2500 * 1500 |
| 9 | 6.75-7.15 | 6.95 | 2 | 2500 * 1500 |
| 10 | 7.24-7.44 | 7.34 | 2 | 2500 * 1500 |
| 11 | 8.3-8.7 | 8.5 | 2 | 2500 * 1500 |
| 12 | 9.42-9.8 | 9.61 | 2 | 2500 * 1500 |
| 13 | 10.1-10.6 | 10.35 | 2 | 2500 * 1500 |
| 14 | 10.8-11.6 | 11.2 | 2 | 2500 * 1500 |
| 15 | 11.8-12.8 | 12.3 | 2 | 2500 * 1500 |
| 16 | 13.0-13.6 | 13.3 | 2 | 2500 * 1500 |
今回のコンテストではCONUS(Continental US)データを用います。このデータはアメリカ域の5000km * 3000kmのエリアを5分毎に観測したデータです。4観測分のデータは約15分間のデータに相当します。
Problem Statement
There are 48 files of satellite data which were observed by weather satellite GOES16. These data represent 4 observations and each observation is separated into 16 channels based on different wavelengths. The task is to create source code which contains a program to compress this dataset, and a program to decompress compressed dataset.
Notes
- Detailed information about dataset is given at last section of this page.
- Given dataset has relation among each file, which we can expect to minimize data by using delta compression.
Constraints on submission
- The program should be able to compress data with lossless compression.
- The program should be able to compress different sets of satellite data which have the same conditions.
- The algorithm code should be royalty-free, which means Weathernews will not need to pay any fee to another organization or person when using this algorithm.
- The program should finish execution within 600 seconds including compression phase and decompression phase. The review process (which is about 16 seconds) is included in this execution time.
Input
The input will be given with two patterns of compression and decompression, sequentially.
On the compression phase, the input will be given as format below.
encode UserEncodingFileName DirectoryName N file_1 fileSize_1 file_2 fileSize_2 : file_N fileSize_N
In the decompression phase, the Input will be given as format below.
decode UserEncodingFileName UnzipDirectoryName
Constraints on Input
- Number of files N = 64
- The words
encodeanddecodegiven in input are text sequences used to discriminate compression phase and decompression phase. - UserEncodingFileName is the absolute path of file which participants should output the compressed file to. It is guaranteed to be less than 50 characters, including alphabet and slash.
- DirectoryName is the absolute path of directory to compress, and it is guaranteed to be less than 50 characters including alphabet or slash.
- file_i is a filename that participants should compress, and it is guaranteed to be less than 100 characters including hyphen, underscore, dot nad alpanumeric.
- Amount of fileSize_i ≦ 120,000,000, filesize_iis guaranteed to be under 1,200,000,0
- UnzipDirectoryName is the absolute path of directory which you store decompressed files to. It is guaranteed to be less than 50 characters, including alphabet and slash.
Output
On the compression phase, output only one compressed file with the designated filename. The program will be reviewed even if you define another filename. However, that will be deleted manually in judge’s review process. If you accidentally made a program which provides another file, please contact us using the question form of this competition. On the decompression phase, decompress all the compressed data into the designated directory.
Calculation method of Score
Compression rate times 1,000,000 will be the score if compression and decompression are successful. Otherwise, it will be 0 .
Input Example1
encode /AtCoder/ZipFile /AtCoder/Dir 3 fileA 100 fileB 100 fileC 200
- This is the input of the compression phase. Compress 3 files
/AtCoder/Dir/fileA,/AtCoder/Dir/fileB,/AtCoder/Dir/fileCand output as/AtCoder/ZipFile.
Input Example2
decode /AtCoder/ZipFile /AtCoder/UnzipDir
- This is the input of the decompression phase. When decompressing file given in Input Example1, output 3 files
/AtCoder/ZipFile,/AtCoder/UnzipDir/fileA,/AtCoder/UnzipDir/fileB,/AtCoder/UnzipDir/fileCfrom/AtCoder/ZipFile.
Additional information: Updated on Dec 19th
Additional information about compression rate. Compression rate is calculated with following equation.
1 - size of data compressed with user defined algorithm / size of data compressed with bz2#datasize of compressed dataset compressed by bz2 using –9 option is 507,803,245b This competition does not focus on trying existing libraries. Submission system may accept your answer with existing compression libraries. However, those answers will be rejected by reviewer after competition period.
About GOES-16 Satellite data
GOES (Geostationary Operational Environmental Satellite) is a United States weather satellite, operated by NOAA (National Oceanic and Atmospheric Administration). GOES platforms are deployed to the West side and East side of the American continent, and GOES-16 is scheduled to become GOES-EAST, beginning its operation from December 2017. This satellite has an ABI(Advanced Baseline Imager) to create visible and infrared observations. Observation data is separated into 16 bands, depending on sensor wavelength, and each band has different resolution. For details, please refer to a table below.
| Band | Wavelength(μm) | Central Wavelength(μm) | Resolution(km) | Pixels(x * y) |
|---|---|---|---|---|
| 1 | 0.45-0.49 | 0.47 | 1 | 5000 * 3000 |
| 2 | 0.59-0.69 | 0.64 | 0.5 | 10000 * 6000 |
| 3 | 0.846-0.885 | 0.865 | 1 | 5000 * 3000 |
| 4 | 1.371-1.386 | 1.378 | 2 | 2500 * 1500 |
| 5 | 1.58-1.64 | 1.61 | 1 | 5000 * 3000 |
| 6 | 2.225-2.275 | 2.25 | 2 | 2500 * 1500 |
| 7 | 3.80-4.00 | 3.90 | 2 | 2500 * 1500 |
| 8 | 5.77-6.6 | 6.19 | 2 | 2500 * 1500 |
| 9 | 6.75-7.15 | 6.95 | 2 | 2500 * 1500 |
| 10 | 7.24-7.44 | 7.34 | 2 | 2500 * 1500 |
| 11 | 8.3-8.7 | 8.5 | 2 | 2500 * 1500 |
| 12 | 9.42-9.8 | 9.61 | 2 | 2500 * 1500 |
| 13 | 10.1-10.6 | 10.35 | 2 | 2500 * 1500 |
| 14 | 10.8-11.6 | 11.2 | 2 | 2500 * 1500 |
| 15 | 11.8-12.8 | 12.3 | 2 | 2500 * 1500 |
| 16 | 13.0-13.6 | 13.3 | 2 | 2500 * 1500 |
This competition uses CONUS (Continental US) data, which represents 5000km * 3000km area of the United States of America region. Observation is done every 5 minutes and data provided in this competition is 4 observations which is separated by approximately 15 minutes.