D. The Omnipotent Monster Killer| Codeforces Round 958 (Div. 2) solution

Рет қаралды 1,207

Күн бұрын

Пікірлер: 43

@og_prakash 2 ай бұрын

#include using namespace std; #define int long long const int N = 3e5 + 5; vector adj[N]; int a[N]; int dp[N][33]; int temp; int dfs(int s, int step, int par) { int res = (step * a[s]); if (dp[s][step] != -1) return dp[s][step]; for (auto it : adj[s]) { if (it == par) continue; int minVal = LLONG_MAX; for (int j = 1; j > n; for (int i = 1; i > a[i]; adj[i].clear(); } temp=log2(n); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for (int i = 1; i

@siddharth_helloworld1292 2 ай бұрын

This is the best solution of this problem. The only part I was not able to understand properly was eliminating (nodes left)/2 nodes in each round, how did we know that this case was worst case,

@Raj-ue3li 2 ай бұрын

Thanks man! , this is the easiest one so far , editorials solution was too complex for me to understand

@og_prakash 2 ай бұрын

🥰🥰

@Your_Soul_13 2 ай бұрын

why "temp+1" not just upto "temp" in ---> for (int j = 1; j

@og_prakash 2 ай бұрын

Bhai logn tak lena tha but n=2 wale case m total step 2 lg jayenge N= 6 m total 3 step lg jayenge i.e( logn)+1 that's why

@m_ithunvoe 2 ай бұрын

Bhai, why didn't we take the parent as a dp state?

@og_prakash 2 ай бұрын

Bro for each Node we can store its parent So parent can be derived from child So why to take it as state In short we try to take as less state as possible to minimise the complexity for that we don't take any variable which can be derived by other as state

@harsh5967 2 ай бұрын

can you share the submission link or code

@og_prakash 2 ай бұрын

@@harsh5967 check pinned comment

@DineshShukla-bb3zp 2 ай бұрын

Hi bhaiya, I wanted ask regarding 3rd Problem . I try to do and of n with ~(1

@og_prakash 2 ай бұрын

n= 4, 8,16 y sare test case p bs galat aayega i guess toh jaise 1 k liye direct ans print kiye waise in sab k liye v kr do

@ishansharma8520 2 ай бұрын

9:47 mein 3 ko second step mein kaise mitaya ??

@rohitchalak6379 2 ай бұрын

Informative but pls use time stamps

@Your_Soul_13 2 ай бұрын

bhai please ese hi sare contests me smjha diya krna div 2,C,D--love u

@SauravKumar-yj7xz 2 ай бұрын

@og_prakash Bhaiya 1 2 3 4 5 6 wale me hame 3 step kyu lagege 2 me bhi to ho jayega 1 4 5 6 aur phir 2 3 in 2nd step phir 3 step kyu lagega???? Please reply

@og_prakash 2 ай бұрын

Pehla cheez apan ko no of steps se matlab nhi hai kyonki dp use krne ka meaning hi y hai ki sare combination try kro For eg is case m apan 2 step m sbko maarne ka try krnge Phir 3 step m sbko maarne ka try krnge And dono ka best ans le lenge Aur baki 1 4 5 6 ko sath m isliye nhi le skte becoz 5 6 adjacent ho jayenge aur adjacent ko lena allowed nhi hai Hmlog y kr skte hai 1st step m 1 6 3 le le 2nd step m 2 5 3rd step m 6

@SauravKumar-yj7xz 2 ай бұрын

@og_prakash Ok dp wla part samj aaya but 5 6 adjacent to hae lekin question me direct connected edge sath me lene se mana kiya hae na?? 5 aur 6 ke bich me direct edge to nahi hae to kya nahi le skte phir bhi??

@og_prakash 2 ай бұрын

Sorry I thought 1-2-3-4-5-6 y tree ka baat kr rhe Bhai aap . Ha 1 2. 3 4. 5. 6 Is case m 1 4 5 6 ko 1st step m and 2 3 ko 2nd step m remove kr skte hai but apan y nhi keh payenge ki y optimal way hai Let's suppose node 2 aur 6 ka attack point 10000 hai aur bakiyon ka attack point 1 hai Toh is case m 1 step m 2 6 2nd step m 1 4 5 3 Rd step m 3 ko remove kr denge

@SauravKumar-yj7xz 2 ай бұрын

Ok bhaiya thanks for samaj aa gya finally

@PRANAVVARMA-p3o 2 ай бұрын

Bhaiya aapka codeforces handle kya hai

@og_prakash 2 ай бұрын

og_prakash

@amiya....6175 2 ай бұрын

Bro steps log2N kyon h ? Har step pe half damage reduce ho skta h iska intuition nhi aarha . Samjha skte ho kya ?

@og_prakash 2 ай бұрын

Apan adjacenct ko nhi le skte toh let's suppose n=10 hai toh 1st step m aapne 4 monster select kra But greedily apan y keh skte hai ki bhai Kam s Kam ek aur monster apan hata skte hai Aap koi v ek tree bnao n size ka usme s aap dekhna Kam s Kam n/2 elements aap hata hi doge koi v case m

@amiya....6175 2 ай бұрын

@@og_prakash Ya got it.👍

@Shubhh2101 2 ай бұрын

Bro which software you are using?

@og_prakash 2 ай бұрын

Jnotes for writing Obs studio for recording

@krishmakhija8333 2 ай бұрын

Bhai steps log2n hi kyun lagenge

@og_prakash 2 ай бұрын

Each step p apan atleast n/2 remove kr skte hai Step 1 k baad n/2 elements bachega step2 baad n/4 and so on That's why logn step max to max lgega Aur video m jo example hai wo worst case ko hi explain kr rha

@Adityasharma-ii3dg 2 ай бұрын

thanks

@jaisanan6182 2 ай бұрын

Bhai kya explain kia hai 💯 Grandmaster ho kya aap?

@og_prakash 2 ай бұрын

Nhi bhai expert hi hai 🥹

@vimalkumardubey6834 2 ай бұрын

Log2 N step hi kyu lgega ??? Ye batana bhai

@og_prakash 2 ай бұрын

@vimalkumardubey6834 2 ай бұрын

@@og_prakash Ohh....basically alternate Remove karenge...isliye..samajh gaya....E karne ke baad dimaag kaam hi nhi kr rha tha 😂😂 btw can u share your linkedin id ?? Let's connect there

@og_prakash 2 ай бұрын

www.linkedin.com/in/bhardwajprakash?

@namanjain1684 2 ай бұрын

@@og_prakash Bro if there is only Four nodes like (1000->1->1->1000) then first we remove end nodes then mid noded which take 2 step so total step is 3 am I right?

@og_prakash 2 ай бұрын

Yes correct