Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972. ×

### awoo's blog

By awoo, history, 4 weeks ago, translation,

2004A - Closest Point

Idea: BledDest

Tutorial
Solution (BledDest)

2004B - Game with Doors

Idea: BledDest

Tutorial
Solution (Neon)

2004C - Splitting Items

Idea: BledDest

Tutorial

2004D - Colored Portals

Idea: BledDest

Tutorial
Solution (Neon)

2004E - Not a Nim Problem

Idea: BledDest

Tutorial
Solution (BledDest)

2004F - Make a Palindrome

Idea: BledDest

Tutorial
Solution (Neon)

2004G - Substring Compression

Idea: BledDest

Tutorial
Solution (awoo)
• +64

 » 4 weeks ago, # |   +3 finally it is released.!!!
 » 4 weeks ago, # |   +15 In D, also you can use bellman-ford after construct a graph: 276620074
•  » » 4 weeks ago, # ^ |   0 can you explain your construction of graph?
•  » » 4 weeks ago, # ^ |   +3 can you use dijkstra with you graph or not?
•  » » 12 days ago, # ^ |   0 You have 2e5 queries so in total it will be TLE
 » 4 weeks ago, # |   +1 The implementation / logic of F makes me feel I am the dumbest man on planet.
•  » » 4 weeks ago, # ^ |   +19 Same, it is very unintuitive for me how you can just add the cumsums; This implementation makes a lot more sense to me: 276838911
•  » » » 4 weeks ago, # ^ |   0 I like this kind of solution. This solution is completely different from author's solution.
•  » » » 2 weeks ago, # ^ |   0 Can someone please explain this marked solution? How is looking at the difference in the prefix sums giving the answer? The ranges (i,j) with same Prefix sums can be completely disjointed after all
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 What do you mean by disjoint? Lets denote the first range as $i_0$-$j_0$ and the second one as $i_1$-$j_1$. We can only account for $i_0 < i_1$, Also we can say $j_0 < j_1$ because other ways the second range will always have smaller sum than the first. This means that the first range always describes a prefix and the second one a suffix, that have a unique start and end point. Now it is just counted how often they are the same.
•  » » 3 weeks ago, # ^ |   0 Enjoy the process in thinking problems.
 » 4 weeks ago, # |   0 can someone explain to me what is wrong with my solution of problem C : 276692116
•  » » 4 weeks ago, # ^ |   0 It is actually causing Overflow, check your output. You can see negative value. When we add positive numbers, we can never get negative values, unless you got memory overflow.
•  » » » 4 weeks ago, # ^ |   0 yeah, in accumulate i had to write 0ll instead of just 0. Thanks.
•  » » 4 weeks ago, # ^ |   0 I faced something like this... maybe using Long Long can fix it.
 » 4 weeks ago, # | ← Rev. 2 →   0 Hello .. Can anyone tell me that for problem D , why this solution is giving wrong answer https://mirror.codeforces.com/contest/2004/submission/276820238 or can anyone suggest some test cases where this failed
•  » » 4 weeks ago, # ^ |   +3 You can actually find the failing test yourself.Checker's output says "wrong answer 248th numbers differ — expected: '3', found: '-1'". That means you only need to add something like "if (test_id == 248) then print(all input)" to your code (and don't print anything else so that the output is not too large). The verdict will still be WA but at least you'll get to see the problematic test.
•  » » » 4 weeks ago, # ^ |   0 damn, i was actually looking for something like this thanks
•  » » » 4 weeks ago, # ^ |   0 It says 248th number, and not 248th testcase. So we don't know which testcase number it really falls under :(.
•  » » » » 4 weeks ago, # ^ |   +4 Then you could replace test_id == 248 with query_id == 248
•  » » » » » 4 weeks ago, # ^ |   0 Can you explain more clearly how to do this ? where to put test_id ?
•  » » » » » » 4 weeks ago, # ^ |   0 You can do something like this#include using namespace std; int main() { int t; cin >> t; if (t == 2) { cout << "1\n4\n0\n3\n2\n-1"; return 0; } int query_ID = 0; while (t--) { int n, q; cin >> n >> q; string s[n]; for (int i = 0; i < n; i++) { cin >> s[i]; } while (q--) { query_ID++; int a, b; cin >> a >> b; if (query_ID == 248) { cout << n << ' ' << 1 << endl; for (int i = 0; i < n; i++) { cout << s[i] << ' '; } cout << endl; cout << a << ' ' << b; } } } } 
•  » » » » » » » 4 weeks ago, # ^ |   0 it won't work for failure on large tests.. like my this submission failing on some 27610th test case... that much input is also not available on that test case..
•  » » » » » » » 4 weeks ago, # ^ |   0 ohk thanksbut it won't work for system tests as it will wrong answeron querry no. 248 of some previous test case and programm will itself terminate
•  » » » » » 4 weeks ago, # ^ |   0 can you explain a bit more? Like how & where to do it?
•  » » » » » » 4 weeks ago, # ^ |   0
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Hey could you please tell what am i missing in this D problem :- 276639203. This got WA . But this got AC :- 276654708Could you please tell what is the difference
•  » » 4 weeks ago, # ^ |   0 you are considering wrong combination of string to search. i.e) if temp1 is RY and temp2 is BG then your first combination would be RB which is not possible
•  » » 4 weeks ago, # ^ |   0 Take a look at Ticket 17471 from CF Stress for a counter example.
 » 4 weeks ago, # |   +3 finally the text editorial is here, still waiting for rating recalculation :(
 » 4 weeks ago, # |   0 can anyone tell why this solution for problem D is giving tle ?
•  » » 4 weeks ago, # ^ |   0 youre using maps and sets a bit too much probably
•  » » » 4 weeks ago, # ^ |   0 ig time complexity is O(q*4*log(n)) which should not give TLE
•  » » » » 4 weeks ago, # ^ |   0 ohh yeah, you just have to add & before st "for(auto st:mp[a[x]])", i just added the & and it passes 276829023. by adding &, you iterate over the elements by reference which is much faster.
•  » » » » » 4 weeks ago, # ^ |   0 thanks, got it
•  » » 4 weeks ago, # ^ |   0 change auto st to auto& st
 » 4 weeks ago, # |   +54 why did problem E get so much hate and backlash ? the problem is actually really nice and high quality even tho there were 10+ videos that leaked the solution first hour which had nearly 5k views combined that doesnt take from the quality of the problem i honestly found it really interesting and gives a new way of approaching problems atleast for me
•  » » 4 weeks ago, # ^ |   +16 I said the same in original Contest post. and guess what, heavily downvoted. I would say it again. E was a nice problem.
•  » » » 4 weeks ago, # ^ |   +8 i think they are missing the core idea tbh i always underrated trying to prove facts from realizing a pattern but this problem proves that sometimes looking at the pattern and trying to build intuition then proving it (proofs for this problem are really easy and i 100% believe most experts+ will be able to reason enough to prove the pattern) actually is a valid idea and sometimes solves even hard problems
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 ik this is off topic but wow dude how did you go from grey to purple in less than a year? as someone who's given about 5 contests it looks lowkey impossible for someone like me
•  » » » 4 weeks ago, # ^ |   +16 it also looked impossible for me after 5 contests but after 60 u will realize its not
 » 4 weeks ago, # | ← Rev. 10 →   +9 In the editorial for problem F, it is written that: "It can be shown that it doesn't matter which of these actions we take".Please mention in the editorial how it can be shown. I have an intuition for this, but I don't have a rigorous proof.
•  » » 4 weeks ago, # ^ |   0 i dont get this part aswell if u understand it please explain it below here
•  » » 4 weeks ago, # ^ |   +26 A rigorous proof would be something like that:Consider the prefix sums of an array, and denote $s$ as the sum of all elements in it. An array of positive integers is palindromic if and only if its prefix sums are "symmetric" with $\frac{s}{2}$ as the center (i.e. if an integer $\frac{s}{2} + x$ exists in the array of prefix sums, then the integer $\frac{s}{2} - x$ should also exist, and vice versa). If there is a pair $(\frac{s}{2}-x, \frac{s}{2}+x)$ such that only one of these elements exists in prefix sums, this pair violates the condition, and we need to "fix" every such pair.Now consider what our actions do to the array of prefix sums. When we merge two adjacent elements, we delete a prefix sum. When we split an element, we add a new prefix sum between the existing two. Every such action can "fix" one of the violating pairs $(\frac{s}{2}-x, \frac{s}{2}+x)$: merging two elements deletes one element from a pair, and splitting an element adds an element into the pair. So, if we have a pair that violates the condition, it doesn't matter whether we fix it by split operation or merge operation — we will still spend one operation to fix this pair.
•  » » » 4 weeks ago, # ^ |   0 Thanks !
•  » » » 4 weeks ago, # ^ |   0 This is amazing. I think it should be written inside the editorial.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 I think a rigorous proof might also go like this:Given the array $b[1\cdots n]$ after doing the minimum number of operations to make it a palindrome. While possible, pick any element $b_i$ that was obtained by a split operation, and do the following:$\textbf{Case 1:} \text{ if } i > \left\lceil \frac{n}{2} \right\rceil \text{or } i < \left\lfloor \frac{n}{2} \right\rfloor \text{, undo the split operation in any possible direction, and fuse } b_{n - i + 1}$ $\text{in the opposite direction that } b_i \text{ got unsplit towards.This increases the number of operations by at most 0.} $$\textbf{Case 2:} \text{ if } i = \left\lceil \frac{n}{2} \right\rceil \text{or } i = \left\lfloor \frac{n}{2} \right\rfloor \text{, do the same as case 1 but if the direction of unsplit of } b_i \text{ is towards } b_{n - i + 1} \text{don't do anything after the unsplitting step. This also increases the number of operations by at most 0.}$$ \textbf{Case 3:} \text{ if } i = \frac{n}{2} \text{, unsplit } b_i \text{ and fuse the result in the opposite direction.}$Note: when you fuse two elements $b_i$ and $b_j$, the state of the resulting element is the union of the split directions of $b_i$ minus the direction $b_i \rightarrow b_j$ and the split directions of $b_j$ minus the direction $b_j \rightarrow b_i$.This process has to end because in each iteration you decrease the number of split elements by at least 1.A similar argument can be constructed to convert all fuse operations to split operations.
•  » » » 4 weeks ago, # ^ |   0 This proof is also helpful. Thanks !
 » 4 weeks ago, # |   0 Any idea why this submission for Problem D is going TLE? As per my understanding, the time complexity for this should be O(q * 6 * logn) which should be within limits I guess. Thanks in advance!https://mirror.codeforces.com/contest/2004/submission/276826924
•  » » 4 weeks ago, # ^ |   +3 Ok I see, issue was with 1., deep copying of vector. 2. Solves it. So dumb, it was going to be the first time I solved a D in div 2!!1.vector nodes = colorToNodes[all_colors[j]];2. vector& nodes = colorToNodes[all_colors[j]];
 » 4 weeks ago, # |   0 I thought of applying dfs for D but will it give tle?
•  » » 4 weeks ago, # ^ |   +3 probably yeah
•  » » 4 weeks ago, # ^ |   0 Yes. If you're checking every possible index, then time complexity will be approximately O(N*Q) because in the worst case, let's say, you will be getting the same x and y each query, and every other string will be suitable. Then, for each query you will be checking N-2 elements. Rounding up, it is N*Q
•  » » 4 weeks ago, # ^ |   0 It will be o(nq) so yeah
 » 4 weeks ago, # |   0 Can someone tell me why my code here isn't necessarily correct? 276831391I understood the idea quite well, as you essentially need to check if there exists a city in between x and y, as well as if the closest two cities not in the range to x and y respectively, but I'm not certain why my above submission is WA, while this submission 276831747 is.Thanks in advance :D
•  » » 4 weeks ago, # ^ |   0 Take a look at Ticket 17468 from CF Stress for a counter example.
•  » » » 4 weeks ago, # ^ |   0 I see, I understand what I was doing wrong now. In my head I thought I was checking the two possible city locations, but I guess my code didn’t reflect that :/. Thank you very much!
 » 4 weeks ago, # |   0 Idk how the B task was for you guys. But for me, as a beginner, it's very tricky.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 To be honest, I was also confused by this problem. I tried to solve it by math first, but decided to just write brute force.
 » 4 weeks ago, # |   0 Hello ...Could anyone tell why this is giving TLE for Problem D and how could i improve .
•  » » 4 weeks ago, # ^ |   +4 In this line set temp=m[s]; you're copying a whole set which maximum size can be $2 \cdot 10^5$. Potentially this copy can be done for each query (again $2 \cdot 10^5$) and moreover a function solve() is called 8 times for every query.If you really need this temporary variable, you can use a const reference: const set& temp=m[s]; 
•  » » » 4 weeks ago, # ^ |   0 Thanks a lot caustique for helping me .
 » 4 weeks ago, # |   0 I always skip problem C. Every contest, If I can not come up with solution as soon as I read problem C then I used to skip it. Then I would solve the next problem D. Educational Codeforces Round 169 is one example. I skipped D, then solved E. And in the EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2), I skipped C, then solved E. After contest, I was disappointed that I did not solve C. Could anyone explain me about this? I can not sure the reason.
 » 4 weeks ago, # |   0 For G, how do you get the digit you placed in the last odd block if in your transition you put a dummy state c=0? Thanks!
•  » » 4 weeks ago, # ^ |   +3 I was thinking of it like that. If you are in a state with $c > 0$, you are always placing the next (the $i$-th) digit into an even block. And you always add $c$ to the answer with that. You can opt to go to $\mathit{dp}[i + 1][0]$, telling the $(i + 1)$-st digit to be in an odd block. With that, you'll know that digit when you are in that state.
•  » » » 4 weeks ago, # ^ |   0 Ohhhhh I see thanks!
 » 4 weeks ago, # |   +3 so slow
 » 4 weeks ago, # |   +5 Idiot me, who wrote 500 lines of code in D :] 276672729
•  » » 3 weeks ago, # ^ |   +3 Honestly, only your effort deserves accepted.
 » 4 weeks ago, # |   -7 Can anyone please correct my code for D ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ void solve() { int n, m; cin >> n >> m; vector v(n+1); for(int i = 1; i <=n; i++) { cin >> v[i]; } while (m--) { int a, b; cin >> a >> b; if (v[a][0] == v[b][0] || v[a][1] == v[b][1] || v[a][1] == v[b][0] || v[a][0] == v[b][1]) { cout << abs(a - b) << endl; } else { int pos = -1; int pos2 = -1; int ans = INT_MAX, ans2 = INT_MAX; int maxi=max(a,b); int mini=min(a,b); for(int i = 1; i< maxi; i++) { if(v[i][0] == v[maxi][0] || v[i][1] == v[maxi][1] || v[i][1] == v[maxi][0] || v[i][0] == v[maxi][1]) { pos = i; } } for(int i = maxi + 1; i <=n; i++) { if(v[i][0] == v[mini][0] || v[i][1] == v[mini][1] || v[i][1] == v[mini][0] || v[i][0] == v[mini][1]) { pos2 = i; break; } } if(pos != -1) { ans = abs(maxi - pos)+abs(pos-mini); } if(pos2 != -1) { ans2 = abs(mini - pos2)+abs(pos2-maxi); } int final_ans = min(ans, ans2); if(final_ans != INT_MAX) { cout << final_ans << endl; } else { cout << -1 << endl; } } }} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 » 4 weeks ago, # |   0 Can someone please tell what am i missing in this D problem :- 276639203. This got WA . But this got AC :- 276654708Could you please tell what is the difference
•  » » 4 weeks ago, # ^ |   0 You can see the difference yourself using built-in "Compare" tool
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 nvm, i got it .
 » 4 weeks ago, # |   0 Can some1 please help me understand why this won't work for prob C??https://mirror.codeforces.com/contest/2004/submission/276886399
•  » » 3 weeks ago, # ^ |   0 In your code inside accumulate function you are declaring 0 as L i.e Long int but for large values you must declare it as 0LL i.e Long Long, rest everything is correct.Link for corrected code: Solution
•  » » » 3 weeks ago, # ^ |   0 So I lost ranks due to a single chars :sob::sob::sob:
•  » » » » 3 weeks ago, # ^ |   0 It happens; the same has happened with me many times
 » 4 weeks ago, # |   0 Can anyone explain editorial of e , i read it many times still i didn't get approach , i understand concept of nim problem because there are alot of editorial are exists already but i'm not getting approach of this problem can anyone explain please ??? thanks
 » 4 weeks ago, # | ← Rev. 3 →   0 F. Can you tell me in more detail what what the line means: ans -= (s % 2 == 1 || !binary_search(p.begin(), p.end(), s / 2)); As far as I understand, this is a check for a palindrome of odd length. But why there are two checks here is not quite clear.
 » 4 weeks ago, # |   +6 In problem E tutorial's induction proof, author writes "if x is a composite prime number", this should be corrected to "if x is an odd composite number".Great explanation otherwise :)
 » 4 weeks ago, # |   0 https://mirror.codeforces.com/contest/2004/submission/276672351this solution is O(n+q) but still gave TLE just because I was using python
 » 4 weeks ago, # |   +3 I had some trouble grasping that the solution for F actually worked (going in increasing order through sizes of segments) because I thought you could end up counting disjoint segments. But all the elements being non-negative makes that impossible, that is, all arrays with equal p[l] + p[r] are one inside of the other.
 » 4 weeks ago, # |   0 can someone pls explain the idea behind D solution once again
 » 4 weeks ago, # |   0 Who can tell me why, in problem F, when the sample input is 1 2 3 4 4, the result is 18 instead of 15?
 » 4 weeks ago, # |   0 can anyone help me with D,I failed in the test 2 2651th number for lots of times:#277004006
 » 4 weeks ago, # |   0 Good problems!
 » 4 weeks ago, # |   0 can we get hidden testcases like we can get in cses problemset
 » 4 weeks ago, # | ← Rev. 5 →   0 where is my code getting wrong for problem D? Link to submissionbased totally on tutorial ideaUPDATE:- ok, got the problem, it is giving -1 for this test case: 4 1 BY RY RY BG 3 4 answer should be 5, my bad :( My Code#include #define int int64_t using namespace std; #define fl(i,a,b) for(int i=a;i=b;i--) bool similar(string &a, string &b) { int res=0; if(a[0]==b[0])res=1; if(a[1]==b[0])res=1; if(a[0]==b[1])res=1; if(a[1]==b[1])res=1; return res; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tt; cin>>tt; while(tt--) { int n,q; cin>>n>>q; vectorv(n); fl(i,0,n) { string s; cin>>s; v[i]=s; } int lastr=-1,lastb=-1,lastg=-1,lasty=-1; vector>l(n,vector(4,-1)),r(n,vector(4,-1)); fl(i,0,n) { l[i][0]=lastr,l[i][1]=lastb,l[i][2]=lastg,l[i][3]=lasty; for(char ch:v[i]) if(ch=='R')lastr=i; else if(ch=='B')lastb=i; else if(ch=='G')lastg=i; else lasty=i; } lastr=-1,lastb=-1,lastg=-1,lasty=-1; rl(i,n-1,0) { r[i][0]=lastr,r[i][1]=lastb,r[i][2]=lastg,r[i][3]=lasty; for(char ch:v[i]) if(ch=='R')lastr=i; else if(ch=='B')lastb=i; else if(ch=='G')lastg=i; else lasty=i; } while(q--) { int src,dest; cin>>src>>dest; src--,dest--; string s1=v[src],s2=v[dest]; if(similar(s1,s2)) {cout<<(abs)(src-dest)<vc={'R','B','G','Y'}; for(int c=0;c<4;c++) { char ch = vc[c]; //checking onto left side int res=0,f=0,pos=-1; if((ch==s1[0]) or (ch==s1[1])) { pos=l[src][c]; if(pos!=-1) res+=(abs)(src-pos); } if(pos!=-1) { string s3=v[pos]; if(similar(s3,s2)) {f=1,res+=(abs)(dest-pos);} if(f) ans=min(ans,res); } //checking onto right side res=0,f=0,pos=-1; if((ch==s1[0]) or (ch==s1[1])) { pos=r[src][c]; if(pos!=-1) res+=(abs)(src-pos); } if(pos!=-1) { string s3=v[pos]; if(similar(s3,s2)) {f=1,res+=(abs)(dest-pos);} if(f) ans=min(ans,res); } } if(ans==1e18)cout<<-1<
•  » » 4 weeks ago, # ^ |   0 Use V &ds = mp[temp[i]] instead of V ds = mp[temp[i]] at Line 98 to avoid copy.
•  » » » 4 weeks ago, # ^ |   0 can you please provide some reason for this it will be very helpful for me in future cases
 » 4 weeks ago, # | ← Rev. 2 →   0 Nevermind, All this time in problem F, I thought we're asked to form a "PERMUTATION" NOT PALINDROME
 » 4 weeks ago, # |   0 I'm very curious why my code with primitive array in java 8 should get timelimit in 21 tests int a []. But the same code with Integer a[] should pass all tests and should be accepted the same logic. Can someone explain me why is that in java solutions.
•  » » 4 weeks ago, # ^ |   0 In Java 13 and earlier versions, Arrays.sort for primitive types doesn't guarantee $O(n\log n)$. You can refer to this and this.
 » 4 weeks ago, # |   0 Sorry, I am dumb in F what does the ans minus two values represent?
 » 4 weeks ago, # |   0 I tried all source shortest path (Floyd-Warshall) in D and apparently got tle. There have been many problems that I tried to solve with the algorithm yet failed again and again at the time limit. Can anyone tell me better approach to solve problems like these? (and also if there is a faster variant of the algorithm)
•  » » 4 weeks ago, # ^ |   0 It will TLE. There is no cutting corner around Floyd-Warshall that would help you, the algorithm is doing its best (sort of, this is excluding any research paper improving it to an extreme, but as far as I understand, this cannot have a better complexity than quadratic).D is more of an exercise to practice implicit graph. That is, you know what you are solving is a graph, but it has special attributes that you should take advantages of instead of blindly jumping into a regular graph algorithm just because you deduce "shortest path" from the problem statements.
•  » » » 4 weeks ago, # ^ |   0 What are the other implicit graphs properties are like? I think this codechef problem has also graph/tree like properties yet still my methods leads to tle.
•  » » » » 4 weeks ago, # ^ |   0 Yes, your example is one out of many incidents. The vague term "implicit graph" simply implies a graph by concept and formulaic constraints — there is no fixed algorithm to solve them all since each constraints would leave different observations/loopholes that contestants must figure out.
 » 4 weeks ago, # |   0 Why algorithm described in solution for F problem is optimal? function f(l, r) is defined as minimum operations required to make a palindrome from a[l..r]. there's no proof in solution. can you explain it plz BledDest?
 » 4 weeks ago, # | ← Rev. 2 →   0 In the tutorial for problem E (Not a Nim Problem), the last paragraph says "if x is a composite prime number...", is this probably a typo? I think it would be correct to write "if x is an odd composite number..."upd: I saw such a comment with such content, I apologize
 » 4 weeks ago, # |   0 Hello guys! Can someone tell me if it was possible to solve D using a graph + Dijkstra's algorithm? For some reason I have some problems)
 » 4 weeks ago, # |   0 If z < x < y ans = (y - z) + (x - z) = (x + y) - 2* z Considering z = (x - a) ans = (x + y) - 2 * (x - a) = x + y - 2x + 2a = y - x + 2a. eq(1)  If x < y < z ans = (z - y) + (z - x) = 2z - (x + y) Considering z = (y + a) ans = 2 * (y + a) - (x + y) = 2y + 2a - x - y = y - x + 2a eq(2) From eq(1) and eq(2) it is clear that z can be either close to x or close to y and it should not matter. I don't understand how is D being solved.
»
4 weeks ago, # |
0

~~~~~~~~~~~~~~

# include <bits/stdc++.h>

using namespace std;

# define YES cout << "YES" << endl

ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;} ll mminvprime(ll a, ll b) {return expo(a, b — 2, b);} ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;} ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;} ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a — b) % m) + m) % m;} ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;} void print(vector &ans){for(auto x: ans) cout<<x<<" "; cout<<endl;} void input(vector &v,int n){for(int i=0;i<n;i++){int e;cin>>e;v.pb(e);}} //===========================================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

void solve(vector &a,int n,int k){ sort(a.begin(),a.end(),greater<>()); ll i=1; while(i<n && k>0){ a[i]+=min(a[i-1]-a[i],k); k-=min(a[i-1]-a[i],k); i+=2; } ll alice=0,bob=0; for(int i=0;i<n;i++){ if(i%2==0){ alice+=a[i]; } else bob+=a[i]; } cout<<(alice-bob)<<endl;

}

int main(){ int T;cin>>T;

while(T--){
int n,k;cin>>n>>k;
vector<int> a;
input(a,n);

solve(a,n,k);

}

}

Can someone please point out the mistake in my code?

 » 3 weeks ago, # |   0 Hello， can someone tell me in f, why the ans should do ans -= (s % 2 == 1 || !binary_search(p.begin(), p.end(), s / 2)); ?? Thanks!
 » 3 weeks ago, # |   0 Hey guys, I don't know why my solution for C got TLE. Can anyone tell me where it went wrong? Thank you ^^
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Avoid using custom comparator function, instead using inbuilt greater () function to sort the array in descending order, as:The use of a custom comparator function introduces additional overhead due to function calls, which becomes significant when sorting large arrays. On the other hand, greater() is a highly optimized standard library component that avoids this overhead, leading to better performance and preventing TLE (Time Limit Exceeded) in competitive programming or performance-critical applications.In most cases, prefer using standard library comparators like greater() for better performance unless you need custom behavior that can’t be achieved otherwise.link for corrected solution: https://mirror.codeforces.com/contest/2004/submission/277758988
•  » » » 3 weeks ago, # ^ |   0 ahh I didnt know that, thank you so much ^^
•  » » » » 3 weeks ago, # ^ |   0 You're welcome! Glad I could help!
•  » » 8 days ago, # ^ |   0 Same problem: TLE 9 in 280240613 I'm using built-in qsort and have no idea how to speed this code up...
 » 3 weeks ago, # | ← Rev. 2 →   0 // This is Code ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ `void sol(){ ll n,q; cin>>n>>q; std::vector v(n); vector>u(6); unordered_mapm; m["BG"]=0; m["BR"]=1; m["BY"]=2; m["GY"]=3; m["GR"]=4; m["RY"]=5; for (int i = 0; i < n; ++i) { cin>>v[i]; u[m[v[i]]].push_back(i); } // for(auto a:u){ // for(auto b:a)cout<>a>>b; // cout<mp; mp[v[a][0]]++; mp[v[a][1]]++; if(mp.find(v[b][0])!=mp.end() || mp.find(v[b][1])!=mp.end()){ cout<vec; if(m.find(temp)!=m.end())vec=u[m[temp]]; else { reverse(temp.begin(),temp.end()); vec=u[m[temp]]; } if(vec.size()==0)continue; // sort(vec.begin(),vec.end()); auto it =upper_bound(vec.begin(),vec.end(),a); if(it!=vec.end())ans=min(ans,abs(*it-a)+abs(*it-b)); if(it!=vec.begin())ans=min(ans,abs(*(it-1)-a)+abs(*(it-1)-b)); } } if(ans==INT_MAX)cout<<-1<>t; while(t--){ sol(); // cout<
 » 2 weeks ago, # |   0 Did anyone try to solve D with using BFS?
 » 2 weeks ago, # |   0 278709370 can someone pls help me why my code always gets wrong answer at test 422
 » 10 days ago, # |   0 can anyone find the issue with this Code for the Problem D?