### Shayan's blog

By Shayan, 3 weeks ago,

Hi,

From now on, we are going to provide video editorials for Codeforces rounds. So, Codeforces rounds are not going to be limited to text editorials, but also video editorials!

We want to seek feedback and try to improve these video editorials as much as possible. We will try different ideas like recorded videos and livestreams to see which one helps you the best. So, please help us make a better content for you!

The blog will be shortly accessible in contest materials.

## 1986G — Permutation Problem

I hope it helps!

• +34

 » 3 weeks ago, # |   -18 Why
•  » » 3 weeks ago, # ^ |   0 it would help beginners ig
•  » » 3 weeks ago, # ^ |   +13 Because he thinks about others as well.
 » 3 weeks ago, # |   +5 Kring
 » 3 weeks ago, # |   +6 I believe text was much better for learning where you can take hints from each line and then work your way out to solve the problem.
 » 3 weeks ago, # |   +5 you are handsome bro
 » 3 weeks ago, # |   0 why is not anyone solving d with dp i can not understood
•  » » 3 weeks ago, # ^ |   0 Because using dp, the order of computation can't be controlled. For e.g., 2*3+4. First, it will go in-depth and compute (3+4), then multiply it with 2. which does not comply with the precedence of operators. You got accepted because the minimum value will be achieved by multiplying (if it's 1); otherwise, performing addition. Multiplying by 1 does not change the result, so the order does not matter. I have ignored the edge cases when min 0 is achievable and n <=3
•  » » » 3 weeks ago, # ^ |   0 ya i understood now i also read the code of others i understood the conditions
•  » » 3 weeks ago, # ^ |   0 I solved it with dp: 267111101
•  » » » 2 weeks ago, # ^ |   0 can u explain ur approach in dp recursion?
 » 3 weeks ago, # | ← Rev. 4 →   0 code#include #define endl "\n" typedef long long ll; using namespace std; void solve() { ll n, k; cin >> n >> k; unordered_map> mp; unordered_map count; for (int i = 0; i < n; i++) { ll cur; cin >> cur; mp[cur % k].push_back(cur); count[cur]++; } ll ans = 0, odd_count = 0; for (auto pair : mp) { vector& nums = pair.second; if (nums.size() % 2 != 0) { odd_count ++; if (odd_count == 2) { cout << "-1" << endl; return; } } vector v; for (auto num : nums) { if (count[num] % 2 != 0) v.push_back(num); } ll sz = v.size(); sort(v.begin(), v.end()); if (sz % 2 == 1) { ll mx_d = 0, index = 0; for (int i = 0; i < sz - 2; i+=2) { ll dif = abs((v[i + 1] - v[i]) - (v[i + 2] - v[i + 1])); if (dif > mx_d) { mx_d = dif; index = i; } } if (v[index + 1] - v[index] < v[index + 2] - v[index + 1]) { index = index + 2; } v.erase(v.begin() + index); sz--; } for (int i = 0; i < sz - 1; i+=2) { ans += (v[i + 1] - v[i]) / k; } } cout << ans << endl; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { solve(); } return 0; } Problem E; wrong answer 5th numbers differ — expected: '118834745', found: '123022038' my code is failing this test case, can someone help me? i could come up with the entire solution on my own apart from the prefix and suffix sum stuff to find the element that needs to go in the middle, i'm struggling to understand how i would use prefix and suffix to find this element, can someone explain how it would work? I did it in a different way in my code but it's missing this test case-
•  » » 3 weeks ago, # ^ |   0 Oh for fucking love of god, please don't paste your shitty code like this.1. Use a spoiler2. Use the Code block feature that codeforces provideslike this: Code#include define endl "\n" typedef long long ll; using namespace std; void solve() { ll n, k; cin >> n >> k; unordered_map mp; unordered_map count; for (int i = 0; i < n; i++) { ll cur; cin >> cur; mp[cur % k].push_back(cur); count[cur]++; } ll ans = 0, odd_count = 0; for (auto pair : mp) { vector& nums = pair.second; if (nums.size() % 2 != 0) { odd_count ++; if (odd_count == 2) { cout << "-1" << endl; return; } } vector v; for (auto num : nums) { if (count[num] % 2 != 0) v.push_back(num); } ll sz = v.size(); sort(v.begin(), v.end()); if (sz % 2 == 1) { ll mx_d = 0, index = 0; for (int i = 0; i < sz - 2; i+=2) { ll dif = abs((v[i + 1] - v[i]) - (v[i + 2] - v[i + 1])); if (dif > mx_d) { mx_d = dif; index = i; } } if (v[index + 1] - v[index] < v[index + 2] - v[index + 1]) { index = index + 2; } v.erase(v.begin() + index); sz--; } for (int i = 0; i < sz - 1; i+=2) { ans += (v[i + 1] - v[i]) / k; } } cout << ans << endl; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { solve(); } return 0; } 
•  » » » 3 weeks ago, # ^ |   0 thanks buddy lol
 » 3 weeks ago, # |   0 Video tutorials might be targeting certain group of individuals usually beginners and text tutorials might be concise and leave enough room for the individuals to think and figure why the solution works by themselves. I think text tutorials are needed irrespective of video tutorials, I presume vast majority of problem solvers prefer text tutorials ? Let me know what you guys think.
•  » » 2 weeks ago, # ^ |   0 Video solutions are my last resort when I can't understand what editorial is trying to say / the approach is too unintuitive. Otherwise, I see no reason it putting link for a video here.
 » 2 weeks ago, # |   0 Thank you Shayan
 » 11 days ago, # |   0 My G's code is O(n^2) ,but it passed.
 » 9 days ago, # |   0 I did G1 through brute force, that is checking each for the condition. Resulting in O(n^2). Its failing at when len is around 30k+. Wanted to know whats the difference bw g1 and g2 problem?