![Nachiket Kanore](/img/default-banner.jpg)
- Видео 123
- Просмотров 23 490
Nachiket Kanore
Индия
Добавлен 28 ноя 2011
Math | Computer Science | Software Engineering
FFT
Slides:
www.canva.com/design/DAGLBj3JMOY/zjQdZ1iI4CNwcnGNhqsxqg/watch?DAGLBj3JMOY&
Links:
github.com/nachiketkanore/CP-Snippets/tree/master/FFT
codeforces.com/problemset/problem/632/E
codeforces.com/problemset/problem/827/E
Solutions:
codeforces.com/contest/827/submission/199628060
codeforces.com/contest/632/submission/102694227
Timestamps:
00:00 FFT Introduction
00:20 Problem 1
04:20 Problem 1 - Hard
04:46 Problem 2
06:35 Polynomial Exponentiation
08:40 Problem 3
12:25 Problem 3 - Solution
www.canva.com/design/DAGLBj3JMOY/zjQdZ1iI4CNwcnGNhqsxqg/watch?DAGLBj3JMOY&
Links:
github.com/nachiketkanore/CP-Snippets/tree/master/FFT
codeforces.com/problemset/problem/632/E
codeforces.com/problemset/problem/827/E
Solutions:
codeforces.com/contest/827/submission/199628060
codeforces.com/contest/632/submission/102694227
Timestamps:
00:00 FFT Introduction
00:20 Problem 1
04:20 Problem 1 - Hard
04:46 Problem 2
06:35 Polynomial Exponentiation
08:40 Problem 3
12:25 Problem 3 - Solution
Просмотров: 121
Видео
Segment Trees
Просмотров 55Месяц назад
Simplest form of segment tree - point update and range queries Timestamps: 00:00 Introduction 00:50 Simplest form 01:50 Sample Problem 02:18 Structure 05:00 Point Update & Range Query 09:00 Time Complexity - Build 10:57 Time Complexity - Update & Query 10:50 Implementation - Build 12:42 Implementation - Update 15:10 Implementation - Query 16:20 Template code 19:45 Applications
Advent of Code 2023 Day 11 Explanations
Просмотров 898 месяцев назад
Link to Solutions: github.com/nachiketkanore/Advent-of-Code-2023/tree/main Timestamps: 00:00 Problem Description 02:15 Observations 05:20 Solution with example 08:22 Implementation Walkthrough 12:20 Final thoughts
Advent of Code 2023 Day 05 Explanations
Просмотров 3658 месяцев назад
Advent of Code 2023 Day 05 Explanations
LeetCode Weekly Contest 373 | All Solutions Explained
Просмотров 729 месяцев назад
LeetCode Weekly Contest 373 | All Solutions Explained
Understanding Recursion by solving 10 problems!
Просмотров 549 месяцев назад
Understanding Recursion by solving 10 problems!
A - Frog 1 | Atcoder Educational DP Contest
Просмотров 5529 месяцев назад
A - Frog 1 | Atcoder Educational DP Contest
D - Knapsack 1 | Atcoder Educational DP Contest
Просмотров 4169 месяцев назад
D - Knapsack 1 | Atcoder Educational DP Contest
C - Vacation | Atcoder Educational DP Contest
Просмотров 3659 месяцев назад
C - Vacation | Atcoder Educational DP Contest
E - Knapsack 2 | Atcoder Educational DP Contest
Просмотров 6619 месяцев назад
E - Knapsack 2 | Atcoder Educational DP Contest
B - Frog 2 | Atcoder Educational DP Contest
Просмотров 2189 месяцев назад
B - Frog 2 | Atcoder Educational DP Contest
F - LCS | Atcoder Educational DP Contest
Просмотров 3919 месяцев назад
F - LCS | Atcoder Educational DP Contest
G - Longest Path | Atcoder Educational DP Contest
Просмотров 3179 месяцев назад
G - Longest Path | Atcoder Educational DP Contest
H - Grid 1 | Atcoder Educational DP Contest
Просмотров 1499 месяцев назад
H - Grid 1 | Atcoder Educational DP Contest
I - Coins | Atcoder Educational DP Contest
Просмотров 4619 месяцев назад
I - Coins | Atcoder Educational DP Contest
J - Sushi | Atcoder Educational DP Contest
Просмотров 9839 месяцев назад
J - Sushi | Atcoder Educational DP Contest
K - Stones | Atcoder Educational DP Contest
Просмотров 4319 месяцев назад
K - Stones | Atcoder Educational DP Contest
L - Deque | Atcoder Educational DP Contest
Просмотров 4899 месяцев назад
L - Deque | Atcoder Educational DP Contest
M - Candies | Atcoder Educational DP Contest
Просмотров 7379 месяцев назад
M - Candies | Atcoder Educational DP Contest
N - Slimes | Atcoder Educational DP Contest
Просмотров 59510 месяцев назад
N - Slimes | Atcoder Educational DP Contest
O - Matching | Atcoder Educational DP Contest
Просмотров 80910 месяцев назад
O - Matching | Atcoder Educational DP Contest
P - Independent Set | Atcoder Educational DP Contest
Просмотров 35910 месяцев назад
P - Independent Set | Atcoder Educational DP Contest
Q - Flowers | Atcoder Educational DP Contest
Просмотров 61010 месяцев назад
Q - Flowers | Atcoder Educational DP Contest
R - Walk | Atcoder Educational DP Contest
Просмотров 37710 месяцев назад
R - Walk | Atcoder Educational DP Contest
S - Digit Sum | Atcoder Educational DP Contest
Просмотров 50410 месяцев назад
S - Digit Sum | Atcoder Educational DP Contest
T - Permutation | Atcoder Educational DP Contest
Просмотров 57010 месяцев назад
T - Permutation | Atcoder Educational DP Contest
U - Grouping | Atcoder Educational DP Contest
Просмотров 41310 месяцев назад
U - Grouping | Atcoder Educational DP Contest
V - Subtree | Atcoder Educational DP Contest
Просмотров 41310 месяцев назад
V - Subtree | Atcoder Educational DP Contest
W - Intervals | Atcoder Educational DP Contest
Просмотров 33410 месяцев назад
W - Intervals | Atcoder Educational DP Contest
X - Tower | Atcoder Educational DP Contest
Просмотров 30510 месяцев назад
X - Tower | Atcoder Educational DP Contest
It's so cool !!
Hi can you please help me debug my code..I have a logic and implementation style very similar to yours but my answer seems to be incorrect
Mind blowing explanation 🫡
Thanks .
nice
u made it easy :)
thanks so much :D
beautiful problem and solution ... loved it😇
very beautiful explanation! i was unable to understand from many other places, but this video made it in one go! You are putting so much effort in explaining little things, that is appreciable! Thank you 😊
Nicely explained :)
Thanks a lot brthr
dhang se to samjha jhat ke baal , google se solution to mai tep du
Great job.. the way you explain the application is too good. just one request if you use marker or pointer then it will be super great. Thanks.
Keeping the code out here for future reference ;) ********************* Recursive Memo ************************* /* कर्मयोग */ void TanTanmayMay() { ll n, m; cin >> n >> m; unordered_map<ll, vector<ll>> adj; for(ll i=0; i<m; i++) { ll a, b; cin >> a >> b; adj[a].push_back(b); } vector<ll> dp(n + 1, -1); auto dfs = [&] (auto f, ll cur) -> ll { if(dp[cur] != -1) { return dp[cur]; } ll x = 0; for(auto node : adj[cur]) { x = max(x, (1 + f(f, node))); } return dp[cur] = x; }; ll ans = 0; for(ll i=1; i<=n; i++) { if(dp[i] != -1) { ans = max(ans, dp[i]); continue; } ans = max(ans, dfs(dfs, i)); } cout << ans << ' '; return; } ********************** Topological ************************* /* कर्मयोग */ void TanTanmayMay() { ll n, m; cin >> n >> m; unordered_map<ll, vector<ll>> adj; for(ll i=0; i<m; i++) { ll a, b; cin >> a >> b; adj[a].push_back(b); } vector<ll> inDegree(n + 1, 0), topo ; for(ll i=1; i<=n; i++) { for(auto neigh : adj[i]) { inDegree[neigh]++; } } queue<ll> q; for(ll i=1; i<=n; i++) { if(!inDegree[i]) { q.push(i); } } while(!q.empty()) { ll curNode = q.front(); q.pop(); topo.push_back(curNode); for(auto neigh : adj[curNode]) { inDegree[neigh]--; if(!inDegree[neigh]) { q.push(neigh); } } } vector<ll> dp(n + 1, 0); for(ll i=(n - 1); i>=0; i--) { for(auto neigh : adj[topo[i]]) { dp[topo[i]] = max(dp[topo[i]], (1 + dp[neigh])); } } ll ans = 0; for(ll i=1; i<=n; i++) { ans = max(ans, dp[i]); } cout << ans << ' '; return; }
damn, i thought it could be solved by greedy; that we simply add two smallest elements each time. Can you find me any counterexample which cause this idea fail?
Bro careful, every time you can add 2 elements , if both are adjacent.
Bhai please add more video on. Advance dp.
perfect explanation to be honest
No comments! Underrated channel...insightful explanation!
Thank you!
Can be do it by recursive dp approach sir.
I don't think so it can be done with the expected complexity To optimize the time complexity, we need to use iteration to compute prefix suma
@@nachiketkanore ok sir got it 🙂
sir you write very nicely all the cases, but you stop while explaining very frequently. Please try to be more fluent. Thank you for the tutorials. And also please have a good mike.
I will try my best
Why you do plus 1 on 2nd and 3rd conditions in recursive function
Added an explanation at 18:41
Nice video
Thanks
Can you make videos on segment tree including lazy propagation
Nice Nice Nice
Just Wow
explanation is very good.. keep it up
bhai you didnt memoize the ans in solve function
I did actually `ans` variable is created as a reference of dp[id], so any changes in `ans` will reflect in dp[id]
You are the worst explainer I've ever encountered 🤢
🔥
nice work, thanks!
Which software you are using for note taking ?
Can't believe there's no likes you're literally the best person describing out here, thank you.
Thank you!
Nice Nice
thanks for this, it explains it well
Nice
THANK YOYOYOOOU little goat
Was wondering how it can be done using iterative DP
check this blog: usaco.guide/problems/ac-matching/solution
thanks for clear explanation
Nice
// हर हर महादेव // जय महाकाल जय महाकाल जय महाकाल जय महाकाल /* Author :- Himanshu Shekhar , IIIT Bhagalpur */ #include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; const long long INF = 1e15; const int MAX_N = 200 * 1000 + 13; # define ll long long vector<vector<int>> graph; ll a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,sum,maxi; bool flag; string str; // IN-OUT DP or UP-DOWN DP ll in[MAX_N]; // // number of ways to colour the nodes outside the subtree of i ll out[MAX_N]; // number of ways to colour the nodes outside the subtree of i void dfs(int source, int parent){ in[source]=1; // choice 1: for painting black for(auto it: graph[source]){ if(it!=parent){ dfs(it,source); in[source]=(in[source]*in[it]); } } in[source]++; // for painting all whites } void dfs2(int source, int parent){ vector<ll> pre,suff; for(auto it: graph[source]){ if(it!=parent) pre.push_back(in[it]); suff.push_back(in[it]); } int sz = pre.size(); for(int i = 1; i<sz; i++){ pre[i]=(pre[i]*pre[i-1]); } for(int i = sz-2; i>=0; i--){ suff[i]=(suff[i]*suff[i+1]); } int cnt = 0; for(auto it: graph[source]){ if(it==parent) continue; ll t2 = in[it]; // re-rooting from node to ch ll l=1, r=1; if(i-1>=0) l=pre[i-1]; if(i+1<sz) r=suff[i+1]; out[it]=(l*r*out[source]); out[it]++; dfs2(it,source); cnt++; } } void solve(){ cin>> n >> m; graph.resize(n+1); // constructing the graph for(int i = 1; i<n; i++){ cin >> a >> b; a--; b--; graph[a].push_back(b); graph[b].push_back(a); } fill(in,in+MAX_N,1); fill(out,out+MAX_N,1); dfs(0,-1); // calculation in[i] for each node i dfs2(0,-1); // calculation out[i] for each node i for(int i = 0; i<n; i++){ cout << ((in[i]-1)*out[i])%m << endl; // "-1" to remove case of for all whites we did earlier for "i" while calcualting in[i] } cout << endl; fflush(stdout); cout << flush; } int main() { #ifndef ONLINE_JUDGE //for getting input from input.txt freopen("input1.txt", "r", stdin); //for writing output to output.txt freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(NULL); solve(); return 0; } please check this approach why AC on 8 TC while rest are showing WA ???
Nice
Just keep uploading…
very helpful...
Nice editorial )):
Hatasi
Can you add some questions on this cyclic dp state
You are doing a great job man. Your content is on an upper level. On top of that you are consistent despite the low views. All the best Bhai..your all work and hard work will pay you off one day for sure.
Nice~~
GG