質問


問題名 ユーザ名 質問 回答 全体公開 投稿日時 最終更新日時
tubo28
解法をSNSなどに公開してもいいですか?
公開頂いても問題ありません。
Q. Can I post the submitted solution algorithm in SNS?
A. Yes, you can.
Yes
A - Problem 1 mcfx
Can foreigners get prize?
Absolutely!
Yes
A - Problem 1 WA_TLE
システムテストにおいて、ランダムグラフでの辺の偏りはまだありますか?
あります。システムテスト用のジャッジデータは同じジェネレータで生成します。
Q. In regard to current generator, the number of edges is biased such that vertices with large index have more edges. Do the test cases of the system test have this bias?
A. Yes. As for the system test, the test cases are generated by the same generator.
Yes
A - Problem 1 iehn
最終結果は最後の提出ではなく、最高スコアが採用されますか?
(その場合、1時間に1度提出することが有効な戦略になると思うのですが。)
【訂正】最終結果は、最終提出に対するシステムテストによって決定されます。詳細は更新された問題文をご覧下さい。当初のアナウンスから変更が出たことをお詫びいたします。
Q. Is the final result determined by the best scoring submission or the final submission? 
A. [Update] We have updated the rules for evaluating a contestants final score. (For details please see the problem page.) As a result your final score is evaluated based on your final submission.  We apologize for the changes in the scoring rules and ask for your understanding.
Yes
A - Problem 1 olphe
システムテストはありますか。
【訂正】hoshi524様のご質問にお答えしたように、システムテストを実施することにいたしました。詳細は問題文をご覧下さい。当初のアナウンスから変更が出たことをお詫びいたします。
Q. Is there a system test?
A. As mentioned in the updated reply to hoshi524’s comment, we have decided to conduct a system test after the contest has finished. Please see the problem page for details. We apologize for the changes in the scoring rules and ask for your understanding.
Yes
A - Problem 1 hoshi524
最終結果はテストケース30個で評価されますか。
もしくは、コンテスト期間の終了後に、テストケースが追加されますか。
【訂正】AtCoder 社様との協議の結果、システムテストを実施することにいたしました。本テストは、新規に作成した150個のテストケースを用いて、各コンテスタントの最後の提出に対して、リジャッジを実施します。なお、新規に作成したテストケースは、テストケースを作成した方法と同じであり、内訳は下記となります。
・ランダムグラフ:90個(そのうち40個は各頂点の次数が高々8)
・完全グラフ:60個
本内容に合わせて、問題文を更新いたしました。当初のアナウンスから変更が出たことをお詫びいたします。
Q. Is the final score determined by the 30 test cases? Do you plan to add test cases after finishing the contest?
A. [Correction] 
As a result of recent developments, we revise our initial statement. While current standings will be estimated on the current 30 test cases, the final score and rankings of each final submission will not be determined based on the current 30 test cases. Instead, the final score and rankings will be determined by running your final submission on 150 previously undisclosed test cases after the contest has finished. Out of these 150 graphs 90 will be random graphs (including 40 random graphs with maximum degree 8) and 60 will be complete graphs. Note that this implies that the final standings may change, after the contest has finished.
This change in evaluating the final score has been decided in agreement with AtCoder Inc. and became necessary to penalize excessive code tuning which is specific to the current 30 input graphs. We will also update the problem statement in order to announce this change in evaluating the final score and rank.
Yes
A - Problem 1 sugim48
「各頂点の次数が高々 8 であるようなランダムグラフ」は、公開されているジェネレータと同じアルゴリズムで生成されましたか?
(例えば、ランダムに辺を張っていく際に次数が 8 未満の頂点のみを選ぶなど、アルゴリズムに修正が加えられましたか?)
WA_TLE様のご質問にお答えしたように、本グラフを生成したアルゴリズムは非公開です。なお、問題文にこのグラフの生成方法に関して追記いたしましたので、ご覧下さい。
Q. Are the random graphs, which have maximum degree at most 8, generated by the algorithm provided with the sample code?
A. No, they are not. As already mentioned in the reply to WA_TLE’s comment: The algorithm for creating degree constraint random graphs is not included in the sample code. However, the algorithm is not fundamentally different from that which generates random graphs. It merely skips the assignment of random edges, if one of the corresponding vertices already reached the maximum degree. We have updated the problem statement accordingly, in order to clarify this point.
Yes
A - Problem 1 WA_TLE
2つ質問があります。
グラフの作り方において,
"ランダムグラフ
•はじめに、 |V| 頂点からなる木をランダムに生成し、その後 |E|−|V|+1 回ランダムに辺を張り、グラフの各辺についてランダムに重み付けします。
•ランダムグラフのうち 8 ケースは、各頂点の次数が高々 8 であるようなランダムグラフになっています。"
とありますが、
① 、"各頂点の次数が高々 8 であるようなランダムグラフ"の作り方は秘密ですか?
②,"その後 |E|−|V|+1 回ランダムに辺を張り"、とありますが、ジェネレーターのコード、および作成されたグラフを見ると、明らかに大きいの数字のほうが辺が張られている割合が高いです。本当にランダムですか?それともジェネレーターが正しいですか?
① ジェネレータは一般的なグラフ (次数などの追加制約なし) を生成するために配布しておりますので、このグラフの作成において使われたアルゴリズムはジェネレータのものと異なり、そのソースコードは非公開です。なお、問題文にこのグラフの生成方法に関して追記いたしましたので、ご覧ください。
② 申し訳ありません。次数に若干の偏りが出るように生成されておりました。これは意図的なものではありませんので、次回のコンテストにおいて修正されます。
Q. There are two questions about the generation of the random graph:
[1] Is the source code for generating random graphs with maximum degree 8 published?
[2] In regard to current generator, the nodes with larger index are more likely to have more edges. Are you sure the graphs are randomly generated?
A. 
[1] No, the source code for generating random graphs, for which each vertex has at most 8 edges attached, is unpublished. For clarification we have edited the problem statement.
[2] We apologize for the inconvenience caused by this issue. As you indicated correctly, the number of edges is biased such that vertices with large index have more edges. This bias was unintended and an updated graph-generator will be provided during the 2nd contest. During the first contest we will stick to the current version.
Yes
A - Problem 1 mcfx
What does "one hour after he/she submits, further answers may be rejected." mean?
It means I can only test my program online in one hour?
We apologize for the misleading statement. We hope that the updated version on the website is more clear. We mean to say that after submission a contestant should wait for at least one hour before submitting an improved algorithm.
Yes
A - Problem 1 ll931110
"However, one hour after he/she submits, further answers may be rejected."

I'm confused by the statement. Does it mean a contestant only have a 1-hour window for submission (counting from the first submission), or consecutive submissions must be at least 1 hour apart?
We apologize for the confusion. We mean to say that consecutive submissions should be separated by a time-interval of at least one hour. The statement is now updated on the main page.
Yes
A - Problem 1 makonagix
入力の a_1 b_1 以降は,グラフG_embがKing's graphであることと同値ということで正しいですか。
正しいです。
Q. The input lists from a_1 and b_1 ensure that G_emb is a King’s graph, don’t they?  
A. Yes, that is correct.
Yes
A - Problem 1 square1001
|V|=1の場合|E|の値は必ず0になります。なので、V=1は定義を満たさない気がしますが、problem1 toolkit (問題文中に添付されていたzipファイル) だと V=1 が生成されるケースがありそうです。本当に全てのケースにおいてV≥2が保証されているのですね?
申し訳ありません。tomerun様のご質問にお答えしよたように、ジェネレータに誤りがあり、problem1 toolkitを更新いたしました。全てのケースにおいて、V≥2は保証されております。
Q. Since |E| always becomes 0, if |V|=1, the choice |V|=1 does not satisfy the definition. However, the attached zip file (problem1_toolkit) inside the problem sentence has the possibility to generate the test cases with |V| = 1. With respect to all test cases, is the condition of |V|≥2 guaranteed?
A. We apologize for the inconvenience caused by this issue. We have already fixed it in response to tomerun’s comment and updated the toolkit for problem 1 accordingly. Furthermore, we guarantee that all test cases satisfies the condition |V|≥2.
Yes
A - Problem 1 キーキ
テスターのgraph_generatorでランダムグラフを生成する時に、同じシードを指定しても実行するたびに生成されるグラフが変わるのですが仕様ですか?(コンパイル・実行はMAC OS、clang-700.1.81です)
申し訳ありません。ランダムグラフの生成時にシードが同一でも生成されるグラフが同一でない不具合があったため、ジェネレータ(graph/randomgraph.h)を修正いたしました。なお、生成されているグラフ自体は正しいものであるため、リジャッジは行いません。
Q. The graph_generator generates different random graphs, even if same random seeds are set.
A. We apologize for the inconvenience caused by this issue. We have corrected the graph/randomgraph.h. It now generates the same random graph for the same choice of the random seed. Note that, the submitted codes are not evaluated again because the current test cases do not suffer from that problem.
Yes
A - Problem 1 tomerun
graph_generatorに graphclass=1, seed=102 を与えると、グラフGについての制約に違反(E==0)するデータが出力されます。
大変申し訳ありません。G の頂点数 |V| の下限に誤りがあり、問題文ならびにジェネレーターを修正いたしました。なお、ジャッジ用のテストケースにE = 0 ならびに |V| = 1 となるテストケース含まれておりませんので、リジャッジは行いません。
Q. Concerning the graph_generator.cpp, when the graphclass and seed are set to 1 and 102, respectively, the output data violates the constraints of graph G, i.e., E=0.
A. We apologize that the lower limit of |V| of graph G was mistaken. We have corrected the problem statement and the common/constraints.h. However, the submitted codes are not evaluated again because the current test cases do not commit such constraint violation (E=0 and |V|=1).
Yes
A - Problem 1 sugim48
30 個のテストケースのうち、ランダムグラフの個数および完全グラフの個数はいくつですか?
ランダムグラフは 18 ケース、完全グラフはサンプル2ケース含む 12 ケースです。
Q. Please show a breakdown of 30 test cases. How many random and complete graphs?
A. The test case includes 18 random graphs and 12 complete graphs (including 2 sample cases). 
Yes
A - Problem 1 Jeffrey
Can I assume the vertices in the King's Graph are numbered from top to bottom, then from left to right same as the sample inputs?
The vertices of the King’s graph are numbered from left to right and then from top to bottom, as in the first figure of the problem.
Yes
A - Problem 1 capythm
レーティング変化はありますか
ありません。
Yes