ItsAboudTime's blog

By ItsAboudTime, 5 weeks ago,

Smartass (Easy Version)

Tutorial
Solution

Smartass (Hard Version)

Tutorial
Solution

Smartass (Smartass Version)

Tutorial
Solution
Solution (lol)

Monasisa

Tutorial
Solution
• +8

 » 5 weeks ago, # |   +3
•  » » 5 weeks ago, # ^ |   0 https://mirror.codeforces.com/group/ppRciMeJFg/contestsJoin this group first!
•  » » » 5 weeks ago, # ^ |   0 ok. you didn't attach it in the blog.
 » 5 weeks ago, # |   0 4 JAYYED
 » 4 weeks ago, # | ← Rev. 2 →   +5 Unofficial Editorial for some more problems.Problem F TutorialOkay so if the array already has all equal elements then the answer is 0. Otherwise we can only make elements equal to any one value in this set {0, 2, 4, 6, 8}. Proof: Since we are doing the opearation $a[i]$ := $a[i]$ * $2$ % $10$. This operation will always make the number even and even numbers can only end with one of the possible values in that set.Now there is an edge case {0}. We can notice than all other numbers except {0} can be transformed into each other, in this cycle {2->4->8->6->2}. Therefore we can use this cycle to calculate operations required. About {0} the array can be made {0} iff the entire set has last digit as {0} or can be transformed into {0}. Now % operations are very slow so instead we can use if / else statements or some math to calculate min operations required to go from 'x' -> 'y'. Also we can transform the array into numbers in the set by preapplying opeartions to save time and in the result add these extra operations. So just calculate and check answer for each value in the possible set and print the minimum. Codevoid solve() { cin >> n; vl a = R(n); sor(a); if(a.ft==a.bk) { print(0); return; } ll extra = 0; rep(i, n) { if(a[i]>=10 || a[i]%2) { a[i]=(2*a[i])%10; extra++; } } debug(a) sor(a); if(a.ft==a.bk) { print(extra); return; } if(a[0]==0) { print(-1); return; } ll res = 1e18; debug(extra) auto func = [&](int val1, int val2) { if(val1==val2)return 0; if(val1==2) { if(val2==4)return 1; else if(val2==8)return 2; else return 3; } else if(val1 == 4) { if(val2==2) return 3; else if(val2==8)return 1; else return 2; } else if(val1==8) { if(val2==6)return 1; else if(val2==4) return 3; else return 2; } else { if(val2==2)return 1; else if(val2==4)return 2; else return 3; } }; for(int i=2; i<=8; i+=2) { ll step = 0; rep(j, n) { step+=func(a[j], i); } chkmin(res, step+extra); } print(res==1e18?-1:res); } Problem K TutorialThe max distance b/w any two nodes in the tree is called diameter. So we can find these two nodes for the given tree. Now after finding these nodes all that is left is to find a node whose distance from both these nodes > k. Both these things can be done with dfs. Codepair dfs(const vector> &tree, int node = 0, int previous = -1, int length = 0) { pair max_path = {node, length}; for (const int &i : tree[node]) { if (i == previous) { continue; } pair other = dfs(tree, i, node, length + 1); if (other.second > max_path.second) { max_path = other; } } return max_path; } void solve() { cin >> n >> k; vvl g = RG(n, n-1); int s1 = dfs(g).fi, s2 = dfs(g, s1).fi; auto f = [&](int i)->vi { vi dis(n); dis[i] = 0; queue q; q.push(i); vi vis(n, 0); vis[i] = 1; while(!q.empty()) { int j = q.front(); q.pop(); for(auto i: g[j]) { if(!vis[i]) { vis[i] = 1; q.push(i); dis[i] = dis[j]+1; } } } return dis; }; vi a = f(s1), b = f(s2); rep(i, n) { if(a[i]>k&& b[i]>k){ yesnoc(1); return; } } yesnoc(0); } Problem J TutorialThe number of pairs (a,b) with lcm(a,b)=n is equal to $(2*e_{1}+1)*(2e_{2}+1)...(2*e_{k}+1)$ where N = $p^e1 * p^e2 * p^ek$ are powers of primes factors of N. code cin >> n; ll res = 1; debug(n) for(int i=2;i*i<=n;i++) { debug(i) if(n%i==0) { ll c = 0; while(n%i==0) c++,n/=i; debug(c) res*=(2*c+1); } } if(n>1)res*=3; print(res); 
 » 4 weeks ago, # | ← Rev. 4 →   0 hint for L: Spoilerbinary search
•  » » 4 weeks ago, # ^ |   0 Bro I didn't tried it yet and you leaked the technique being used :( Please put this under a spoiler tag!
•  » » » 4 weeks ago, # ^ |   0 +1
 » 4 weeks ago, # |   +9 Can be add it to GYMS? ABO_3esam