This app is Japanese-only, but I think you can use it: andoryoto.github.io/WebApplication/searchapp/ This lets you search words in problem statements or official editorials of ABC and ARC. For example, if you want to practice Dynamic Programming, you can ask ChatGPT to translate it into Japanese (AI should work fine here) and search "動的計画法".
Hello evima, thx for the tutorial! I was thinking if problem C could be solved by thinking of starting tile from which we imagine graph of absolute value - sort of a 'V' shape that has 2 points as a base and then check if the end point is inside that graph? Because if it is inside, then the answer is simply abs(sy - ty) and I couldn't quite find what to do when it is outside of the 'V' shape. I could only think of finding the boundaries of the absolute value and then ask whether the end point is further than the boundaries. Can this approach work?
It seems your approach is what I explained in the video without the shifting and flipping. Here is a "stationary" version of the explanation which might work better for you: atcoder.jp/contests/abc359/editorial/10279 If I understand you right, you can tweak my code there and get what you want.
For an integer i and a length-(K-1) string s consisting of A and B, let dp[i][s] = the number of ways to determine the first i characters so that the last K-1 of those equal s without having a length-K palindrome as a substring. For example, if K=4 and s = "ABB", you cannot add A because "ABBA" is a palindrome, but you can add B (if the given string allows it), after which the new s will be "BBB". When i < K-1, s can be shorter than length K-1, or you can prepend dummy characters. You can use hashmaps to maintain s as a string or convert it to a bitmask.
I don't see a point in rerooting here. Just count the contribution of each edge (like (cnt[v] * (total - cnt[v])) and you are done. Here is my code: atcoder.jp/contests/abc359/submissions/54778861 (Rerooting works but it would need strictly more work.)
I doubt it's "much" simpler, especially if you don't have prewritten code. Also, Centroid Decomposition is one of the to-go solutions for this kind of problem.
![What's DFS & BFS? [For CP Beginners] (English subtitles)](http://i.ytimg.com/vi/0_9heBS7Flg/mqdefault.jpg)
![What's DFS & BFS? [For CP Beginners] (English subtitles)](/img/tr.png)
![AtCoder Beginner Contest 354 A-G in 4 minutes [English Subtitles]](http://i.ytimg.com/vi/FUO2HX3Mqt8/mqdefault.jpg)
![THE Hardest Problem in Competitive Programming [English Subtitles]](http://i.ytimg.com/vi/4vxSyqk0jVY/mqdefault.jpg)
ABC初参加でCが(過去問を除いて)人生で3問目の問題でした
難しかったです
C: 制約を見間違えていました……が解法には影響しないはずです。
I figured the constraints wrong... but it should not affect the solution.
Wrong: -2*10^16
3問目わけわからんくてヤケクソ提出したら通って嬉しかった
C問題の制約なんですけど、第一象限のみ考える問題です！
0
ご指摘ありがとうございます。間違えました。
ただし、第一象限に限っても特に簡単にならないはずです（スタートとゴールの方向関係は相変わらず自由です）。
パフォーマンスが 前回ABCD < 今回ABC になるくらいCが強かったけど解けたから嬉しい
Dはdpっぽい雰囲気を感じたけど組み方がね……
C問題、難しいとか言われてたので、やってみたら解けたので非常に嬉しかった(リアル参加できなかったのであとでやった)。ｘ方向右に行くか左に行くかでコスト０で一つ進めるかで考えました。D問題のDPでキーに文字列を使う発想がなかった…(いつも数値だったので…)。E問題のs = [(0, 0)]はs= []でも問題ないですか？(python知らないので初期値で何らかの値が必要なら必要になりますが)。FはまだしもGはさっぱり…解けるのがすごい
Eの初期値は [] で問題ありません。
[(0, 0)] は [(INF, 0)] の間違いでした（こうすれば while のループ条件で空でないことの確認を省けます）。
@@evimalab なるほど！INFだと確かに空でないことは不要ですね。
面白かった〜 5完でした…
どれも一筋縄ではいかなくてボッコボッコにされちゃいました
C問題、高さyのミノをyだけ左に動かすとイメージしやすくなる
初めてB,Cまで行けたけど実装方法が難しかった
problem C wrecked me bro
hi evi, if i'd like to practice by topic on atcoder, how can i do that ?
This app is Japanese-only, but I think you can use it: andoryoto.github.io/WebApplication/searchapp/
This lets you search words in problem statements or official editorials of ABC and ARC.
For example, if you want to practice Dynamic Programming, you can ask ChatGPT to translate it into Japanese (AI should work fine here) and search "動的計画法".
@@evimalab thank you, i love japan because of u
Will atcoder tags work again ?@@evimalab
Cで質問なんですけど、制約でS_y,S_x,T_y,T_x>=0なはずなんですけど...
でも難しい発展問題として参考にしていただきます！
@@sakamiyari ご指摘ありがとうございます。実際には全く難しくなっていないと思います。（すべて非負でも S_y, S_x を自由に選べてしまうので……）
I am very pleased with myself that I solved the problem C in half an hour and using the formula that I wrote on paper.
Same but I took 67 minutes
初めて本番でC解けた！うれしい！
Hello evima, thx for the tutorial! I was thinking if problem C could be solved by thinking of starting tile from which we imagine graph of absolute value - sort of a 'V' shape that has 2 points as a base and then check if the end point is inside that graph? Because if it is inside, then the answer is simply abs(sy - ty) and I couldn't quite find what to do when it is outside of the 'V' shape. I could only think of finding the boundaries of the absolute value and then ask whether the end point is further than the boundaries. Can this approach work?
It seems your approach is what I explained in the video without the shifting and flipping.
Here is a "stationary" version of the explanation which might work better for you: atcoder.jp/contests/abc359/editorial/10279
If I understand you right, you can tweak my code there and get what you want.
@@evimalab You are right, the approach is actually the same, you just nicely simplified this idea, I'll try to better understand 🙂
atcoderの解説に載ってたんやけど
evimaさん何者？
問題文の英訳を担当しています。たまに問題の発案もします。
i wish there was a english version of this
Just in case you miss it, the video has English subtitles. (Multi-language audio, that is, English voiceover is not yet available to this channel.)
@@evimalabplease try to do in English. It will be very helpful
@@manishkumar-uw5mw I will add English voiceover when TH-cam allows me to. (More than 90% of the viewers are from Japan, so I guess that's it.)
Cなにw
中学受験の算数でてきそう
俺は無理だった
D問題が難しかったのでE問題に行ったら解けました
動的計画法が思いつかなかったです
Cの入力は常に非負では
Can you explain the dp solution for D more?
For an integer i and a length-(K-1) string s consisting of A and B, let dp[i][s] = the number of ways to determine the first i characters so that the last K-1 of those equal s without having a length-K palindrome as a substring.
For example, if K=4 and s = "ABB", you cannot add A because "ABBA" is a palindrome, but you can add B (if the given string allows it), after which the new s will be "BBB".
When i < K-1, s can be shorter than length K-1, or you can prepend dummy characters.
You can use hashmaps to maintain s as a string or convert it to a bitmask.
in g in editorial how in one dfs you are calculating the sum for an single color by rerooting ?that when i change an edge how much change will come
I don't see a point in rerooting here. Just count the contribution of each edge (like (cnt[v] * (total - cnt[v])) and you are done.
Here is my code: atcoder.jp/contests/abc359/submissions/54778861
(Rerooting works but it would need strictly more work.)
@@evimalab thanks sir
@@evimalab thanks sir i got it im just stupid
質問です
E問題で解説していたstackの解法の計算量ってどれくらいになりますか？水の高さを同じになるようにした塊のようなものを合併して、stackにはひとつの要素として入れると思うのでO(n^2)を超えることはないのはわかるのですが、正しい計算量はどれくらいなのでしょうか？
線形時間です。
atcoder.jp/contests/abc359/submissions/54776467
このコードで append() はちょうど N 回実行され、そのときに入ったもの以外は pop() できない（妙な初期要素を入れてしまいましたが無視してください）ため pop() の回数は N 回以下です。
@@evimalab ありがとうございます！stackに追加される回数を考えればよかったんですね！！
Why centroid in G??? There is a much simpler way with compressed trees
I doubt it's "much" simpler, especially if you don't have prewritten code. Also, Centroid Decomposition is one of the to-go solutions for this kind of problem.
First!
يا فرحة امك بيك
@@A57278 كسمك
@@A57278kosooooomk
@@yosefmahmoud3715 ابويا ع امك
@@A57278 koooooosomok