### Pyqe's blog

By Pyqe, 5 months ago,

## 2A. Goals of Victory

Author: nandonathaniel
Developer: nandonathaniel

Tutorial

## 2B/1A. Helmets in Night Light

Author: ArvinCiu
Developer: gansixeneh

Tutorial

## 2C. Joyboard

Author: Pyqe
Developer: gansixeneh

Tutorial

Author: Pyqe
Developer: Pyqe

Tutorial

Author: Pyqe
Developer: Pyqe

Tutorial

Author: Pyqe
Developer: Pyqe

Tutorial

Author: Pyqe
Developer: Pyqe

Tutorial

Author: Pyqe
Developer: Pyqe

Tutorial

## 1G. Clubstep

Author: Pyqe
Developer: Pyqe

Tutorial
• +107

 » 5 months ago, # |   +9 [Reposting] for anyone interested in video editorials for A, B, C and D: https://youtu.be/3gP74cSjhwg?si=bl1lMboWq4O2dPgg
 » 5 months ago, # |   +7 A small correction for A: it has to be the negative of the sum of the present teams, not just the sum.
•  » » 5 months ago, # ^ |   +1 Whoops, sorry about that! It's fixed now
 » 5 months ago, # |   +11 Good Editorial!
 » 5 months ago, # |   +5 In div1-D, did anyone try directly calculating unequal part ?It should be for these 3 cases: inequality at odd occurrence of value, at even occurrence, and inequality due to insufficient lengthMy submission I've added comments.. Answer differs by one, struggling to find the reason. Would highly appreciate if anyone can help
•  » » 5 months ago, # ^ |   0 In case it gives any clue.. I had checked for this particular test-case, execution doesn't get to 3rd case.. gets to first & second
 » 5 months ago, # |   +3 In problem 2E, is it neccessary to push the parent vertex immediately if the current vertex is white? If it is, can anyone explain it for me? I've tried to push the vertex only when it's indegree is 0 and get WA on test 4.
•  » » 5 months ago, # ^ |   +3 I have the same issue as yours and I am also confused. Why would this change the answer? Does the order in which the vertices are pushed change the answer? I thought we were doing a BFS except that we stop when we encounter a cycle.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 Actually, I now do understand why my solution didn't work. Try this test case: 6 2 3 4 1 2 3 A possible solution is 3 1 2 3 The problems with pushing the vertex into the queue only if it's indegree is 0 is that some of the vertices in the cycles have to be assigned "black" before we iterate through the cycles.
•  » » 5 months ago, # ^ |   +3 It's not really necessary to handle it like that. But I chose to do it like that in order to easily handle the case where the colours in the cycle is forced (it happens when at least one child of a vertex in the cycle is white).
 » 5 months ago, # |   0 How to solve problem 2E/1C with 2-sat?I tried a lot of times but still wa on 4. And how to solve it with flow?
 » 5 months ago, # |   0 For problem A it should be negative of the sum.
 » 5 months ago, # |   0 In first question sum must be negative of n-1 other teams score not same
 » 5 months ago, # |   +16 For calculating the equal ways in 1D, if some $a_i$ occur odd times, impossible to equal, else we can think for each value x, $a_{i_1}=a_{i_2}=\dots=a_{i_{2k}}=x$, x have k segments $[a_{i_1},a_{i_2}]$, $[a_{i_3},a_{i_4}]$,$\dots$. For all segements, if one contains another, impossible to equal, if two segments for value x and y intersect, their order will be the same. Only need to use some easy data structure to search the segments.
 » 5 months ago, # |   0 Can Anyone share some problems similar to 2-D.
 » 5 months ago, # |   0 Can Someone Explain this part in more detail~  In order to calculate g(w) for all desired values of w , we need to iterate the elements of a from the biggest value to the smallest value. Each element we iterate, we iterate every index that is a factor of the index of the current element and mark those indices as group 1 while we keep track of the value of c .
•  » » 5 months ago, # ^ |   0 first we will sort the given array(but keeping track of the indices, so use pair or something to store the input).From biggest to smallest: I hope you understood the group 1 and group 2 idea. We are going from bigger values in the sorted array to smaller ones because we want to incrementally build group 1 (actually we need just the count of group 1, i.e. c).For each element we iterate, lets say curr1 (curr1.first -> value and curr1.second -> index), we are going to mark each element of group1 which are the divisor of my curr.second, which will represent the indices, if chosen in next iteration of curr2 element, will yield the value from group 1 (i.e. curr1->value), which we want to avoid for curr2. I hope it makes sense.
 » 5 months ago, # |   +20 Very good problems!
 » 5 months ago, # |   +12 I really enjoyed the problems ! They felt beautiful and creative. Congrats to the authors !
 » 5 months ago, # |   0 I think there is a typo in 1877B — Helmets in Night Light tutorial. residents with the smallest values of ai first. Using the fact that ai ≥ 1, we can deduce that we will always have a resident with an available share. Should be residents with the smallest values of bi first. Using the fact that ai ≥ 1, we can deduce that we will always have a resident with an available share. Values of b represent the cost, and since all ai >= 1 we can always have that cheap person to tell atleast 1 other person.
•  » » 5 months ago, # ^ |   0 That's right! It was a mistake. It should be fixed now
 » 5 months ago, # |   +10 Is Problem G a Geometry Dash reference? Lol.
•  » » 5 months ago, # ^ |   +13 Yes, it is! Glad you noticed :D
•  » » 5 months ago, # ^ |   +13 Yeah, I actually came up with the idea of that problem when playing an insane demon level in the game lol
•  » » 5 months ago, # ^ |   0 You guys should make more problems like this lol, would be interesting to see
 » 5 months ago, # | ← Rev. 2 →   0 UPD: Never mind
 » 5 months ago, # |   0 Can anyone help me to understand effects of Anti Pimples problem. I am not able to get the logic behind the tutorial.
 » 5 months ago, # |   +21 Alternative solution for div2-D:For each element $a_i$, define the value $m_i$ — maximum in $a$ over all indices which are multiples of $i$.Consider that some elements are colored black. If we suppose that the answer for such coloring is $m_i$, then the answer does not change while coloring black other indices $j$ such that $m_j \leq m_i$, so the answer to the problem is $\sum\limits_{i = 1}^n 2^{i-1} \cdot m_i$ over a sorted array $m$.To calculate $m_i$, let's use the idea of sqrt decomposition: If $i > \sqrt{n}$, then we can go over all multiples $i, 2i, ..., \lfloor\frac{n}{i}\rfloor i$ and find $m_i$ in $O(\sqrt{n})$. If $i \leq \sqrt{n}$, then let's use dynamic programming. Define $dp_{i,j}$ as the maximum value over indices $i, i + j, i + 2j, ...$. To calculate this, the transition between states is quite simple: $dp_{i,j} = max(a_i, dp_{i + j,j})$. After that, the desired value for $m_i$ will be stored in $dp_{i,i}$. Since we only need $j \leq \sqrt{n}$ to calculate the answer, all the values can be obtained in $O(n\sqrt{n})$. Therefore, the total complexity is $O(n\sqrt{n})$.
•  » » 5 months ago, # ^ |   0 then we can go over all multiples $i,2i,...,⌊n/i⌋i$ and find mi in O(n−−√) This takes $O(n/i)$, so $O(n\log n)$ in total
•  » » » 5 months ago, # ^ |   0 Oh, you're right, thank you!So there's no need for dp, and the solution is even simpler and more efficient.
•  » » » » 5 weeks ago, # ^ |   0 i came up with this solution too, tbh i find this much more intuitive/simpler than the solution in the editorial
•  » » 3 months ago, # ^ |   0 Bro u made it more difficult:P
 » 5 months ago, # |   0 Why is this wrong for B? I spent 15mins writing it then another 1hr debugging it :skull: #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using str = string; int main(){ int t; cin >> t; while (t --> 0){ int n, p; cin >> n >> p; int a[n], b[n]; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; vector> idx(0); int summ = 0, first_gen_give = 0, extra = 0; if (n == 1){ cout << p << '\n'; continue; } for (int i = 0; i < n; i++){ if (b[i] < p){ idx.push_back(make_pair(a[i], b[i])); summ += a[i]; summ += 1; first_gen_give += 1; // cout << summ << 'a'; if (summ > n) first_gen_give -= 1; } // cout << summ << 'b'; } // cout << '\n'; int given = 0, total = 0; if (summ < n){ // if (first_gen_give < n){ int ans = 0; for (int i = 0; i < idx.size(); i++)ans += idx[i].first * idx[i].second;// cout << idx[i].first << idx[i].second << ' '; // for (auto& c: idx) cout << c.first << c.second << 'c'; ans += (n - summ + first_gen_give) * p; cout << ans << '\n'; // } } else{ given = first_gen_give; // cout << first_gen_give << '\n'; sort(idx.begin(), idx.end(), [](auto &left, auto &right){return left.second < right.second;}); // for (auto& c: idx) cout << c.first << ' ' << c.second << 'c'; bool fl = false; for (int i = 0; i < idx.size(); i++){ given += idx[i].first; // cout << given << " a "; if (given == n){ cout << total + (idx[i].first * idx[i].second) + (first_gen_give * p) << '\n'; fl = true; break; } else if (given > n){ // cout << (n - given - idx[i].first) * idx[i].second << 'a'; // cout << (n - given + idx[i].first) << ' '; total += ((n - given - idx[i].first) * idx[i].second); total += ((given - idx[i].first) * p); // cout << total << " b "; break; } else total += idx[i].first * idx[i].second; // cout << total << " c "; } if (!fl) cout << total << '\n'; } } } 
 » 5 months ago, # |   +29 I have an alternative solution for G that runs in $O((n+q)(\log{n} + \log{\max{x}}))$.Same as editorial, to answer a query $(l,r,x)$, we take $x$ and run through gates $r$ to $l$ sequentially, where gate $i$ is the function $f(x)=\min{(a_i,\lfloor \frac{x+a_i}{2} \rfloor)}$. We can retrieve the answer after computing the sum of results after running each gate.Suppose all queries have $r=n$. Then we can get some solution sketch like this: gradually increment $x'$ from $0$ to $10^9$, while maintaining $ans_i$ for $1 \le i \le n$, where $ans_i$ is the result of $x'$ after running through gates $n$ to $i$. Then, to answer a query $(l,r,x)$, we just pick the moment we have $x'=x$, and we take the sum of $ans_i$ for $l \le i \le n$.To maintain $ans_i$, we can store a set of active gates, which are gates $i$ that have $a_i \le ans_{i+1}$. Once a gate is activated, it will never be deactivated. Obviously, if gate $i$ is not active, then $ans_i = ans_{i+1}$. So by knowing positions active gates, we can divide the $ans$ array into continuous blocks of equal value. Now, when we increase $x$ by $1$, we update the $ans$ array in a similar fashion as how we would do $+1$ on a big integer represented in binary. This takes $O(1)$ amortized. We then check, for each changed value of $ans_i$, whether it would activate some gates. This can be detected by RMQ, and we can have a $O(\max{x}+n\log{n})$ idea.To improve, we can compute the next value of $x'$ which either activates a gate or we need to answer a query of that value, instead of increasing $x'$ one by one. This improves the time complexity to $O((n+q)(\log{n} + \log{\max{x}}))$.Finally, let's think of how to also handle queries with arbitrary $r$. Let's say we have a query $(l,r,x)$, If at any moment we manage to have $ans_{r+1}=x$, then we are very happy as we can get what we want by just computing sum of $ans_i$ for $l \le i \le r$. So we can just modify the previous solution to detect the next important $x$ that either activates a gate, or hits some $ans_{r+1}=x$.But there might be some ugly situation where we have cooked $x'$ up to $10^9$, but \$ans_{r+1}
 » 4 months ago, # | ← Rev. 3 →   0 Can anyone help me with this code of problem D . Ive been trying this problem since tommorow and i dont know why this code doesnt works; 228466533
 » 4 months ago, # | ← Rev. 2 →   0 Can anyone tell the flaw in the logic for the problem 2e/1c. First we pool that values in array for which freq is more than one , then we can see that the index corresponding to that value should be circled . Then for the remaining array values apart from ones which will be circled and other which has freq more than one we can make an undirected graph with index --> array value . This graph should be bipartite and if not the ans is -1 , else we can alternate between the nodes to circle them.
 » 3 months ago, # |   0 In 2E/1C, "For each white element, there cannot be any white element with a value equal to the index of that black element.", should it be "For each white element, there cannot be any white element with a value equal to the index of that white element."
 » 2 months ago, # |   0 Could anyone please tell me the logical difference between these codes: 237306441 and 237304555? Both codes have the same logic.
 » 2 months ago, # |   0 can someone explain why I am getting TLE on this submission_A?