なんでも質問してください。Please feel free to ask any questions. You can ask debugging questions, but please use the submission link (like atcoder.jp/contests/abc339/submissions/49970180 ) unless the code is quite short (at most around 20 lines).
Managed to solve A-C this time. B was incredibly stressful but managed to solve it at the very last minute. Felt like Tom Cruise ngl. Btw I saw you as a writer of this contest so if I may ask what question was yours? Awesome video as always!
Thanks! I think you can expect yourself to be able to walk over B (like you probably walked over A) some time soon. Well, I proposed just C (to be clear, presented the original idea but did not prepare test cases).
Unfortunately (?), I write just about all English statements in these contests. Can I ask you what parts of the problem statement ( atcoder.jp/contests/abc339/tasks/abc339_c ) are not clear and concise? Frankly speaking, this statement should be too plain to blame in that direction. (It's something like the 4000th problem statement I've written, and while I admit that I've made hundreds of mistakes, this problem is too simple to mess up.)
Oops, thank you for pointing that out. (It seems almost nobody has checked this in English version for months...) I fixed it: ruclips.net/p/PLAYMgc8c_QezzZAEcnhI_Awo1QHWxE6FD
Thank you for your suggestion. I've had that idea before but have been reluctant to make more than one such video a week. However, I should give it a try. I'm thinking of covering Codeforces Div. 2 soon.
I've decided to skip G in these videos because including G seems to have almost no effect on the video's performance. However, this time it might have been reasonable to make an exception. (I would have used Segment Tree with a sequence on each element.)
Probably no. I mean, since there is no update query, we can afford to build a gorgeous Segment Tree where each node has a sorted array for the corresponding interval (which happens to be equivalent to Merge Sort), then for each query, perform O(log N) binary searches for a total of O(log^2 N) time. The official editorial (Japanese version, somehow the English one is not out yet) has code for this: atcoder.jp/contests/abc339/editorial/9207
@@evimalab yeah i get it with a total of n log n memory we get a mergesort tree kind of... i read that thats what its called in a codeforces blog... love your videos btw tho i just read the english subtitles...
Actually, I can't deny it. In Japan, there's an established genre of videos called "Yukkuri Kaisetsu," which this video belongs to. However, even Japanese viewers might find it odd at first glance.
Sir you translate problems why don't you translate editorials. English editorials are unavailable earllier this was not the case but from some recent abc's english editorial are unavailable
I'm not sure if it can be solved in O(HW) time, but I'm almost sure it is either quite hard or impossible, or it would have been used in that setting. There seems to be no O(HW) submission that got accepted during the contest.
![5-Color Theorem Revised [English Subtitles]](http://i.ytimg.com/vi/uBy2Vghh--8/mqdefault.jpg)
なんでも質問してください。Please feel free to ask any questions.
You can ask debugging questions, but please use the submission link (like atcoder.jp/contests/abc339/submissions/49970180 ) unless the code is quite short (at most around 20 lines).
7か月も前の動画に質問失礼します。問題Fについて2つ質問させてください。
①作中のMは10^31ぐらいのランダムな整数より
10^8,10^8+1,10^8+2,・・・10^8+kのk+1パターン全部試したほうが
確実な気がするのですがどうでしょうか？（確率的には失敗確率が1/10^8kぐらいになる？）
10^8で割ったときの商と余りの情報があれば残りのパターンは計算量を節約して求められるような気もします。
（結局確率論のままなのであんまり意味ないかもしれませんが）
②Mで割った余りが0になるA_i,A_j,A_,kの組み合わせを保持しておいて確認の計算をしてはダメなのでしょうか？
当方プログラミングは簡単なものしかできず、競プロはやったことがないため、的外れな質問なら申し訳ございません。
自分には、公式解説を頑張って読むより4分動画を見る方が分かりやすいのでいつも助かっています。ありがとうございます。
温かいお言葉ありがとうございます。励みになります。
1:40 ここすこ
F is very educational. Thanks!
You're welcome! (Actually, I was a bit worried that it might get too many ACs, but instead E and G did.)
今回はバスがあるぜｗｗｗ
E問題でAtCoder Libraryを使用されてたので気になって色々調べていたらかなり難解で、えびまさんの解説が愛しくて切なくてたまらなくなりました。
今後の動画でAtCoder LibraryやACL practice contest に関する解説を行う予定はありますか？
ACL のパソコンへの導入（WSL+VSCode）については ruclips.net/video/uhnASau7fB4/видео.html で詳しく扱ったので、ご覧になっていなければご覧ください。
ACL の中身についての動画もあってよさそうなのは確かで、検討します。
（かなりの分量があるので扱い方が悩ましいですが…。
なお、念のため、ACL Practice Contest の正解コードは公式ドキュメント atcoder.github.io/ac-library/master/document_ja/ に載っていると書いておきます。
また、atcoder.jp/contests/dp の解説動画でも segtree, lazysegtree, modint については軽く触れる予定です。）
@@evimalab
ありがとうございます！
今のところは公式のドキュメントを参考に頑張ってみようかなと思っているのですが、えびまさんの解説動画も見れると非常に嬉しいという次第です。
動画内の説明やコードがどれも見やすいもので非常に分かりやすくいつも参考にしています。EDPCの解説動画がとっても楽しみです！
これからも応援してます❣️大好きです！
面白かった〜 全完できて大勝利！
Dは怯みました、貪欲だったり移動方向を記録するBFSだったりを考えててこずりました
Managed to solve A-C this time. B was incredibly stressful but managed to solve it at the very last minute. Felt like Tom Cruise ngl.
Btw I saw you as a writer of this contest so if I may ask what question was yours?
Awesome video as always!
Thanks! I think you can expect yourself to be able to walk over B (like you probably walked over A) some time soon.
Well, I proposed just C (to be clear, presented the original idea but did not prepare test cases).
@@evimalab C was good just that whoever wrote it (hoping it's not you) needs to make sure the details are clear and concise.
Unfortunately (?), I write just about all English statements in these contests. Can I ask you what parts of the problem statement ( atcoder.jp/contests/abc339/tasks/abc339_c ) are not clear and concise? Frankly speaking, this statement should be too plain to blame in that direction. (It's something like the 4000th problem statement I've written, and while I admit that I've made hundreds of mistakes, this problem is too simple to mess up.)
何度もごめんなさい!
概要欄のえびまさんの解答コードへのリンクで
C のリンクが D になってるかもしれないです!
(もし違ったらごめんなさい! URLが直接見れないので)
(なんか指摘してばっかでごめんなさい! いつもわかりやすい解説めちゃくちゃ助かってます!)
ご報告ありがとうございます！間違っていたので直しました。
こういうご指摘は何回でも助かります。（一度投稿してしまうと投稿者はほぼ気づけなくなります。コメントなど他に見るものがたくさんあるので…）
the link to the playlist of competitive programming in description is not working??
Oops, thank you for pointing that out. (It seems almost nobody has checked this in English version for months...) I fixed it: ruclips.net/p/PLAYMgc8c_QezzZAEcnhI_Awo1QHWxE6FD
you should do these 4 min videos for other platforms also like Codechef and Codeforces
Thank you for your suggestion. I've had that idea before but have been reluctant to make more than one such video a week. However, I should give it a try. I'm thinking of covering Codeforces Div. 2 soon.
@@evimalab yea that would be great . your videos are really really helpful
thank you
There is a data structure called wavelet trees which directly solves g
I've decided to skip G in these videos because including G seems to have almost no effect on the video's performance. However, this time it might have been reasonable to make an exception. (I would have used Segment Tree with a sequence on each element.)
@@evimalab the persistent segment tree trick from cp algorithms?
Probably no. I mean, since there is no update query, we can afford to build a gorgeous Segment Tree where each node has a sorted array for the corresponding interval (which happens to be equivalent to Merge Sort), then for each query, perform O(log N) binary searches for a total of O(log^2 N) time. The official editorial (Japanese version, somehow the English one is not out yet) has code for this: atcoder.jp/contests/abc339/editorial/9207
@@evimalab yeah i get it with a total of n log n memory we get a mergesort tree kind of... i read that thats what its called in a codeforces blog... love your videos btw tho i just read the english subtitles...
B問題30分以上コード見たり触ったりしてるけど理解できない、、、
is it just me or these editorial videos are so weird ?
Actually, I can't deny it. In Japan, there's an established genre of videos called "Yukkuri Kaisetsu," which this video belongs to. However, even Japanese viewers might find it odd at first glance.
動画タイトルが 338 になってる?気がします!
もしもう訂正済みならごめんなさい!
ご報告ありがとうございます！修正しました、非常に助かりました。
（「動画の詳細を再利用する」というボタンを押したあとで直すのを忘れました。）
Cの原案、きっとパーフェクトさんすう教室だよねw
Y E is segment tree😭😭😭😭
Sir you translate problems why don't you translate editorials.
English editorials are unavailable earllier this was not the case but from some recent abc's english editorial are unavailable
I need permission from the company to write the official editorials, but I'll talk to them.
F問題の解説話が飛んでませんか?
どの部分がでしょうか？3:21 など再生時間を示してくださいませんか。
@@evimalab 3:29 あたりです。
@@hasumi_kuzusake
ま：ひとつ素因数分解するより100万回かけ算するほうがマシだな
ち：実は詰んでない？
ここでしょうか？ここでセリフを1行飛ばしてしまったなどということはなく、意図した通りです。
「（かけ算以外のことをするのはとても無理で、かけ算も間に合わないってことは）実は詰んでない？」という発言です。
@@evimalab その後です。「絶対に一回で正解する方法は..」という前にmodをとる話というか、その正当性が何も言及されていないため飛んでいるように思いました。
@hasumi_kuzusake なるほど。念のためこの後の会話をすべて載せます。
1. ち：実は詰んでない？
2. ま：絶対に1回で正解する方法は、正直私もわからない
3. ち：え…
4. ま：テストケースは100個くらいしかないから、
5. ま：1000回に1回くらいならまあ失敗できるぜ
6. ち：じゃあ、適当な数を選んであまりが合ってたらOKで…
7. ま：ケース1個あたり実質10億回くらいのチェックをするから、
8. ま：100ケースでは10の11乗回くらいで、
9. ま：それぞれが10の30乗分の1くらいの確率で失敗するなら…
10. ま：地球上の全員が提出しても全員助かるだろう
1 から 5 までの流れは問題ないと思います。
（実は低確率で不正解してもよい、という暗黙の前提を導入します。）
6 は確かに飛躍があるといえますが、7 から 9 まででフォローしたつもりです。
（mod の正当性（？）は 9 で軽く触れました。
より詳しくは、A[i] * A[j] - A[k] が 0 でなくかつ M で割り切れてしまうとこの i, j, k について判定を誤りますが、
A[i] * A[j] - A[k] が 0 でない場合に M で割り切れる確率、
つまり A[k] を M で割ったあまりが A[i] * A[j] を M で割ったあまりと一致する確率は 1/M 程度と考えられます。
これは、M で割ったあまりという 0 以上 M-1 以下の値を使って失敗する確率は 1/M だろうという直感的な考えと一致するので、説明を省きました。）
Any hint on D if N >= 1000.
I'm not sure if it can be solved in O(HW) time, but I'm almost sure it is either quite hard or impossible, or it would have been used in that setting. There seems to be no O(HW) submission that got accepted during the contest.
неплохо, но последняя конечно лажа
Please make videos in English.
When this channel has multi-language audio available, I'll add English voiceovers.
first