### Ezio07's blog

By Ezio07, history, 2 years ago,

Problem Authors: GT_18, karansiwach360

Authors Code: 42406878

Code Complexity: O(LogN)

Problem Authors: csgocsgo, karansiwach360

Authors Code: 42406891

Code Complexity: O(NLogN)

Problem Authors: csgocsgo, ezio07

Authors Code: 42406848

Code Complexity: O(N)

Problem Author: ezio07

Authors Code: 42406857

Code Complexity: O(NLogN)

Problem Authors: dhirajfx3, GT_18, praran26

Authors Code: 42406908

Code Complexity: O(NLogN)

Problem Authors: karansiwach360, hitman623

Authors Code: 42406921

Code Complexity: O(N)

Problem Authors: 300iq

Authors Code: 42406934

Code Complexity: O(262 * N + 26 * Q)

Problem Authors: dhirajfx3, dark_n8

Authors Code: 42406942

Code Complexity: O(|x| * LogN * 26) per request.

We hope you enjoyed the problems!

Hope to see you all in next edition of Manthan.

• +70

 » 2 years ago, # |   0 Can someone tell me why i am getting this error in my code it is working fine in my compiler 42407188
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 your array should be initialized with a constant value. In case of your code: int a[n+1] and int si[l] are wrong!
 » 2 years ago, # | ← Rev. 2 →   +14 ezio07 It would be very helpful if you could add Time Complexity for all the proposed solutions. Thanks!
•  » » 2 years ago, # ^ |   0 Yes, added!
 » 2 years ago, # |   0 another solution to problem A:As was written, the answer it's number x for series of numbers: 1, 2, 4, 8,..2^x. This series of numbers it's geometric progression. The sum of the geometric progression is given by the formula: S(x) = (b(x)*q-b(1))/(q-1). For 1, 2, 4,..2^x q=2, b(1) = 1 and b(x) = 2^(x-1) => S(x) = (2^(x-1)*2-1)/(2-1) => S(x) = 2^x-1. The following condition must be met for the answer to be correct: S(x)<=n => 2^x-1<=n => n+1-2^x>=0. The code this solution: 42408562. (sorry for my not so good english)
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Another solution :)) #include using namespace std; int main() { int n; cin >> n; cout << (int)log2(n) + 1; return 0; } 
•  » » » 2 years ago, # ^ | ← Rev. 2 →   -17 hey...can you explain me... how did u get this logic? thanku in advance @ Dragonol...
•  » » » » 2 years ago, # ^ |   +4 The logic is based from the binary form of n:for exemple: n = 10. The binary form of 10 is 1010, you will need 1000,0100,0010,0001 to form any number x (1<=x<=10) 1 from: 0001 2 from: 0010 3 from: 0010 + 0001 4 from: 0100 5 from: 0100 + 0001 6 from: 0100 + 0010 7 from: 0100 + 0010 + 0001 8 from: 1000 9 from: 1000 + 0001 10 from: 1000 + 0010 The answer is actually the length of binary form of n. In fact, log2(n) = length_of_binary_form_of_n — 1 so the answer shuould be log2(n)+1.
•  » » » » » 2 years ago, # ^ |   0 Thanks. Now I got it
•  » » » » » 2 years ago, # ^ |   0 Thank you for Explaination. I got it now
•  » » » 2 years ago, # ^ |   0 This is a beautiful solution. :)
•  » » » 2 years ago, # ^ |   0 Hi,I used cout<<(ll)(log(n)/log(2) + 1)<<'\n'; I got wrong answer. http://codeforces.com/contest/1037/standings/participant/19485663#p19485663 Can you please tell why?
•  » » » » 2 years ago, # ^ |   0 Your code seems to be correct. Even ideone is giving the expected answer on 8 that is 4. https://ideone.com/tgBeiN
•  » » » » » 2 years ago, # ^ |   0 Yes, but codeforces is giving wrong answer.
•  » » » » » » 2 years ago, # ^ |   0 GT_18 karansiwach360, can you please provide the reason?
•  » » » » » » » 2 years ago, # ^ | ← Rev. 3 →   +8 It's clear case of precision error.If you try cout<<(log(n)/log(2)+1-4);, (for n=8) you'll get -1.60245e-016. On casting to (ll), the result you get is 3.
•  » » » » » » 2 years ago, # ^ |   0 Yes. I think Something may have gone wrong on their side.
•  » » » » 2 years ago, # ^ | ← Rev. 4 →   -39 ///Deleted
•  » » » » » 2 years ago, # ^ |   +8 loge(n)/loge(2) == log2(n), not loge(n-2).
•  » » » » » » 2 years ago, # ^ |   0 ops!! My fault :)) Sorry
•  » » » 2 years ago, # ^ |   -16 Your solution sucks. If n could be up to 1018, it wouldn't work.
•  » » » » 2 years ago, # ^ |   +17 http://codeforces.com/contest/1037/submission/42365860Yours fail too when n is up to 10^18, you suck.
•  » » » » 2 years ago, # ^ |   0 That's because the problem condition for n is 1 ≤ n ≤ 10^9. If you want n up to 10^18, then here you are: #include using namespace std; int main() { long long n; cin >> n; cout << (long long)log2(n) + 1; return 0; } 
•  » » » » » 2 years ago, # ^ |   0 try to check n = 259 and n = 259 - 1
•  » » » » » » 2 years ago, # ^ |   0 I don't understand . They both come out with 60. So i do the subtraction of 2^59 and 2^59-1, the answer is 0.Why?
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   -6 most probably it's wshift-count-overflow try this #include using namespace std; int main() { unsigned long long n=1ULL<<59; //unsigned long long n=1ULL<<59-1; cout << (unsigned long long)log2(n) + 1; return 0; } 
•  » » » » » » » » 2 years ago, # ^ |   0 It also writes 60 for n = 259 - 1
•  » » » » » » » » » 2 years ago, # ^ |   0 but not for n=2^(59) do you have correct solution?
•  » » » » » » » » » 2 years ago, # ^ |   0 correct solution is to do all in integers. just go from 0 to 60 and check whether it is a right answer
•  » » » 2 years ago, # ^ |   0 32 - __builtin_clz(n)
 » 2 years ago, # | ← Rev. 2 →   0 can anybody tell me why iam getting wa in test case 11 in D problem https://ideone.com/r2c4K5
•  » » 2 years ago, # ^ |   0
•  » » 2 years ago, # ^ |   0 if(n==200000) { cout<
•  » » 2 years ago, # ^ |   0 2 2 1 1 2output: Yesthis might be the condition
•  » » » 2 years ago, # ^ |   0 Got accepted I was declaring array size smaller than input
 » 2 years ago, # |   -14 Can someone tell me D's solution? I read the D's tutorial and read other source codes, but I can't understand. What does D's tutorial say and what is the solution?
•  » » 2 years ago, # ^ |   0 For understanding what the tutorial is trying to say, first you need to understand how graph is stored in an adjacency list and BFS Order Traversal. If you understand these two things, then you can read ahead.Basically, the way you store nodes in adjacency list, determine how your BFS Order Traversal is going to look like.So, for checking the given BFS Order, you store the neighbours of a node in the list according to the order they appear in the given BFS Order Traversal. Basically, "we can sort the adjacency lists of all the nodes in the order in which they are present in the input BFS Sequence." (as mentioned in editorial)Once you get the adjacency list according to given BFS Order, Do BFS on the list and then check whether it matches the given order or not.
•  » » 2 years ago, # ^ |   +1 Here is my editorial to D. Let me know if it helps :)
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 42423685 oh Great minds think alike .
 » 2 years ago, # |   0 Can somebody tell me what is wrong with my code (42403836) for 4th problem.Actually I am getting WA on test case no.11 which is a large test case that is why I am not able to debug it.
•  » » 2 years ago, # ^ |   +4 maybe this condition
•  » » » 2 years ago, # ^ |   0 My answer is yes in this case what should be its answer?
•  » » » » 2 years ago, # ^ |   0 Yes, you are right,answer should we yes
•  » » » 2 years ago, # ^ |   0 Thank you that helped me a lot !
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 see this comment
•  » » » 2 years ago, # ^ |   0 I submitted again, with little bit of moification -> (42416659) now it is passing the case you are pointing to,but still it is not passing the test case no.11
 » 2 years ago, # |   -19 Can we do Problem D using Dijkstra's algorithm with edge weights set to 1 ?Input order should be in increasing order of distances from the source.
•  » » 2 years ago, # ^ |   0 If you ever use Dijkstra with all edge weights as 1, use BFS instead. But I don't think it would work. You have to add all nodes connected to the last node in some order, but you can't mix them with other nodes (even if they are on same distance from 1).
 » 2 years ago, # |   0 My submission for B is in queue for too long. 42412545 What should i do ?
•  » » 2 years ago, # ^ |   0 everyone get stuck in queue. maybe they're repairing the system
 » 2 years ago, # | ← Rev. 2 →   0 Can someone tell me why i am getting this error in my code it is working fine in my compiler 42399951
•  » » 2 years ago, # ^ |   0 You don't initialize local visited array with zeros
 » 2 years ago, # |   0 Can Someone Explain Problem B? Why are other elements modified when only the median needs to be modified?
•  » » 2 years ago, # ^ |   0 Median is middle element in a sorted array.Now, modifying Median may break the sorted order of the array elements. So we make sure elements before the median are still smaller than new median and all the elements after median are larger than new median too.
•  » » » 2 years ago, # ^ |   0 Got It.Thanks For Help.
 » 2 years ago, # |   0 Still wondering: optimality proof for A, anyone?
 » 2 years ago, # |   +13 Can anyone explain G more clearly?
•  » » 2 years ago, # ^ |   +25 For each character c, you need to precalculate grundy numbers of strings between consecutive occurrences of c, their prefixes and suffixes. When a string s breaks into multiple strings, the first part is a calculated suffix, last part is a calculated prefix. For other parts, you can keep prefix xor of the calculated xors. So suppose you have a string adbecbdabfr and query on dbecbdabf and you choose character b (as your first move), the precalculated grundy numbers will be of ad, ec, da and fr and their prefixes and suffixes. To answer the query, you take d suffix from ad and f prefix from fr. ec and da can be retrieved from prefix xor.There are n + 26 such strings. You can consider them as queries while precalculating and order them properly such that the required values are calculated before the query.
 » 2 years ago, # |   +3 Why actually "The best possible way to distribute the coins is to create packets with coins 1,2,4,…2k with maximum possible k such that 2⋅2k−1≤n. " is there any proof about that ? I have solved the problem and I still don't know why this happens!
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 To be able to make 1 you defnitely need the coin of value 1 so it has to be included.d now to make 2 you can include another coin of value one to sum to 2 or you can use a coin with value 2 so that you can make 3 as well so using coin with value 2 is optimal. You can go on inductively to show 2k is optimal.
•  » » 2 years ago, # ^ |   +7 Lets assume that we can take <= log2(n) coins. We can choose some of them in 2^log2(n) = n different ways. So there are at most n different sums. One of them is 0. So we have at most n-1 non-zero sums. It is not enough to cover n numbers(1, ..., n). Thus answer is not <= log2(n), answer is >= log2(n)+1. So, log2(n)+1is optimal answer.Now we have to find log2(n)+1 coins. These are 1, 2, 4, ..., 2^(log2(n)+1). We can prove its optimality by induction. First i coins cover numbers [1 ... 2^i-1]. Next coin is 2^i. With that coin we can obtain also sums 2^i, 2^i+1, ..., (2^i+2^i-1 = 2^(i+1)-1). So with first i+1 numbers we can cover 2^(i+1)-1 coins.
 » 2 years ago, # |   +2 I see that many people make arrays/vectors of size 2e5 + 5 if max number of elements is 2e5. Why is it not 2e5?
•  » » 2 years ago, # ^ |   0 Maybe for work on boundary of array and taking this size to sure don't go out of size of array ... actually for more security
•  » » 2 years ago, # ^ |   0 i see you have never got WA/RE because of wrong bounds
•  » » » 2 years ago, # ^ |   0 Could you explain what is it and when it happens?Because in my view if an array goes out of bounds, there is a mistake in the code.
 » 2 years ago, # | ← Rev. 2 →   0 Can anybody tell me what is wrong with my solution for D. It is getting wrong answer on case 12 My code
 » 2 years ago, # | ← Rev. 2 →   +1 can anyone tell to me in task A why we can not do this with smaller number of packets?
 » 2 years ago, # | ← Rev. 2 →   0 in problem B why we need to traverse the whole array and find the answer but we simply know the required value of the median(s) from the question, we can perform the operations from the middle element to s.
 » 2 years ago, # | ← Rev. 2 →   +28 Let me clarify problem E a bit, for current explanation goes more into details and less into the idea.First, we build final graph of friendships. Then we delete from it all nodes with less than k friends — those buddies weren't going anywhere anyway.The interesting observation is that all the remaining people can go to the trip on the last day. Now we can just play the time backwards. After we removed edge which appeared on day n and also all the nodes with friends number below k, all remaining nodes can go to the trip on (n-1)-th day. Then do the same thing for n-1, n-2, et cetera. Need to print results in reverse order though :)
•  » » 2 years ago, # ^ |   0 Thanks for the explaination.
•  » » 2 years ago, # ^ |   0 https://codeforces.com/contest/1037/submission/42430271I am doing different approach can anyone figure out where I am going wrong!!!
•  » » 2 years ago, # ^ |   0 Can you please describe how the third sample test case works??????? I couldn't figure it out.
 » 2 years ago, # |   0 Auto comment: topic has been updated by ezio07 (previous revision, new revision, compare).
 » 2 years ago, # | ← Rev. 2 →   0 solved F with Divide & Conquer 42425616. Actually it's quite similar to the one in the editorial.
 » 2 years ago, # |   0 Why the code of E is so long......
•  » » 2 years ago, # ^ |   +3 Just have a look at the solve() function rest is just template. Solution#define ve vector int n, m, k; cin >> n >> m >> k; ve > Edges(m); ve Ans(m); ve degree(n); ve > > adj(n); set > Good_set; ve in_good_set(n, true); for (int i = 0; i> Edges[i].first >> Edges[i].second; Edges[i].first--; Edges[i].second--; adj[Edges[i].first].pb({ Edges[i].second,i }); adj[Edges[i].second].pb({ Edges[i].first,i }); degree[Edges[i].first]++; degree[Edges[i].second]++; } for (int i = 0; ifirstsecond; for (auto &y : adj[node]) { int x = y.first; if (in_good_set[x]) { Good_set.erase({ degree[x],x }); --degree[x]; Good_set.insert({ degree[x],x }); } } Good_set.erase({degree[node],node}); in_good_set[node] = false; } for (int i = m - 1; i >= 0; i--) { Ans[i] = Good_set.size(); int u = Edges[i].first, v = Edges[i].second; if (in_good_set[u] && in_good_set[v]) { Good_set.erase({ degree[u],u }); --degree[u]; Good_set.insert({ degree[u],u }); Good_set.erase({ degree[v],v }); --degree[v]; Good_set.insert({ degree[v],v }); while (!Good_set.empty() && Good_set.begin()->firstsecond; for (auto &y : adj[node]) { int x = y.first; if (y.second >= i) continue; if (in_good_set[x]) { Good_set.erase({ degree[x],x }); --degree[x]; Good_set.insert({ degree[x],x }); } } Good_set.erase({degree[node],node}); in_good_set[node] = false; } } } for (int i = 0; i
 » 2 years ago, # |   +3 Nice solution for E...Will definitely give it a try
 » 2 years ago, # |   +3 Problem FCan someone push me in the right direction? I can't figure out how to get l and r for each element in linear time.
•  » » 2 years ago, # ^ |   +14
•  » » » 2 years ago, # ^ |   +1 Thanks for help.
 » 2 years ago, # | ← Rev. 2 →   +33 For problem F, Can anyone give an explain about how to calculate number of segment in [l, r]? Also, why the segment is not k, 2 * k — 1, 3 * k — 1 ... ?
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 Did you get the answer? I'm also confused why is it 2*k and not 2*k-1 in the explanation. EDIT: Got the answer. Here is a great explanation.
•  » » » 2 years ago, # ^ |   +8 thanks, it's a good solution.
 » 2 years ago, # | ← Rev. 2 →   0 Can somebody tell me what is wrong with my code(42398601) for valid BFS problem?
 » 2 years ago, # |   +8 Could you explain, how did you solve the query part in O(|x|* LogN *26) per request? I solved it in O(|x| * LogN * LogN * 26) . I first build the suffix tree of given string. Then to find whether there is an element in range [l,r] in given subtree, I use binary search on each node of segment tree which are visited during query. Hence, there would be O(logN * logN) for each character (from 0 to 26) for each index of x in the worst case.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +19 Consider of example the ith position of the array of leaves has value li, now we will be maintaining a set of persistent segment trees from left to right, that is persistent segment tree for ith leaf is obtained by adding value 1 to the li position of persistent segment tree of leaf i - 1. To do this, maintain three arrays, seg_tree, L_ptr, R_ptr. The node represented by integer id c will represent- seg_tree[c]: The sum of values in the segment represented by current node. L_ptr[c]: The left child of node represented by c. R_ptr[c]: The right child of node represented by c. Now to add the value li to the persistent segment tree of leaf i - 1 and get the root node for the persistent segment tree for leaf i, we can adopt the following algorithm.If we have persistent segment of node i - 1 as c, we can obtain persistent segment tree for node i by calling add(c,0,|S|,li). Code snippetint add(int c, int l, int r, int pos) { if (l>pos || r < pos) return c; int ID = Next++; if (l == r) { seg_tree[ID] = seg_tree[c] + 1; return ID; } int mid = (l + r) >> 1; L_ptr[ID] = add(L_ptr[c], l, mid, pos); R_ptr[ID] = add(R_ptr[c], mid + 1, r, pos); seg_tree[ID] = seg_tree[L_ptr[ID]] + seg_tree[R_ptr[ID]]; return ID; } Now to find whether the current subtree contain any value in the range L ≤ R,Let a + 1 be index of left-most leaf in the current subtree, and b be the right-most leaf in the current subtree and pj represent the persistent segment tree of leaf j.Now we need to only take two segment trees pa and pb and query if sum of values in the segment L... R is non zero. To do this we can apply the following method or say call find_sum(pa, pb, 0, |S|, L, R) Methodint find_sum(int l_tree_c, int r_tree_c, int l, int r, int qry_l, int qry_r) { if (qry_l > r || qry_r < l) return 0; if (l >= qry_l && r <= qry_r) { return seg_tree[r_tree_c] - seg_tree[l_tree_c]; } int mid = (l + r) >> 1; return find_sum(L_ptr[l_tree_c], L_ptr[r_tree_c], l, mid, qry_l, qry_r) + \ find_sum(R_ptr[l_tree_c], R_ptr[r_tree_c], mid + 1, r, qry_l, qry_r); } If returned value of the above function is non-zero then there is some value in the range L ... R. You may also like to see the find_first method in the code given in the tutorial to find the smallest value which is greater than L but less than R.So this is how we can check in O(log|S|) time whether there is some leaf in the current subtree with value in range L ... R. Let us know if something is still not clear.
•  » » » 2 years ago, # ^ |   +5 Thanks :)
 » 2 years ago, # | ← Rev. 2 →   0 Problem D. Test Case 39. Given Test Case - 2 1 2 2 1My opinion — Yes. But the checker says No. Can someone Explain to me why the answer is No?
•  » » 2 years ago, # ^ |   0 You always start from root which is 1. So it's impossible that you visit any other node before 1. Therefore, sequence must always start with 1. Here it starts with 2.
•  » » » 2 years ago, # ^ | ← Rev. 4 →   0 If I have started at 1. Then because first no is 2. I would have printed no. But here the case is opposite. Checker is saying No, and I'm saying Yes.
•  » » » » 2 years ago, # ^ |   +1 In the given input, tree has two nodes. Root is 1, and it has single child which is 2. In this case, there's actually single BFS possible which is "1 2", not "2 1". You always start with 1. If first is not 1, then just print "No", no need to check anything else.
•  » » » » » 2 years ago, # ^ |   0 Then what does this mean ??  The BFS algorithm in this problem always starts with 1, however, it is not guaranteed that a[1] = 1.
•  » » » » » » 2 years ago, # ^ |   +4 It means that correct BFS algorithm should start with 1, but we may give a sequence with a[1] != 1 which is necessarily an incorrect BFS sequence and you have to print "No" for such sequence.
•  » » » » » » » 2 years ago, # ^ |   0 Thanks. Got it. Was confused by the announcement.
•  » » » 2 years ago, # ^ |   0 lol, I can't believe that. Added a && v[0] == 1 and code passed. So stupid.
 » 2 years ago, # |   0 Can you guys write the last part of the Problem F properly, more clearly?
•  » » 2 years ago, # ^ |   -6
•  » » 2 years ago, # ^ | ← Rev. 2 →   +16 This is not clarification of the method from the tutorial, but slightly different method of calculating total count for each number.On the figure above you can see progression of b arrays for given array a and k = 3. To calculate total count for number 8 you want to calculate count of all numbers in the triangle (their count is proportional to r - l) and then subtract blue ones (their count is proportional to i - l) and green ones (their count is proportional to r - i).
•  » » 2 years ago, # ^ |   +21 Turns out, you don't really need all that case work. Here.
•  » » » 2 years ago, # ^ |   0 Yeah this is what we expect from the editorial that HOW it turns out that you don't need it.
 » 2 years ago, # | ← Rev. 4 →   0 Just do cout<<(long long)log2(n)+1 in Problem A
•  » » 2 years ago, # ^ |   0 don't do that, please
 » 2 years ago, # |   +10 About problem G. Editorial says we treat precalclulating like queries. So we iterate over character c and use two prefix/suffix dps and one range query. But yet we dont know grundy for each gap between two equal characters, we cant precalculate prefix xors. We can use segment tree, but than complexity becomes n*A*A*log(n) which is too long. So how to accomplish precalculation?
•  » » 2 years ago, # ^ |   -12
 » 2 years ago, # |   +5 Here is an O(n) solution to D :42464470
•  » » 2 years ago, # ^ |   0 Maybe this one is simpler :)42377485
 » 2 years ago, # | ← Rev. 4 →   0 In problem D we need to check if the BFS sequence is valid or not. The editorial solution is really easy to understand. I guess same approach can be used if the problem was to check for valid DFS sequence.Only change would be that a DFS will be used instead of BFS. Can anyone confirm this, I am not 100% sure about it!
•  » » 2 years ago, # ^ |   0 Yes, the editorial approach will work in that case also.
 » 2 years ago, # |   0 can anybody help me understand 1037E(Trips) problem??
•  » » 2 years ago, # ^ |   0 See this explanation from saluev
•  » » » 2 years ago, # ^ |   0 thanks:))
 » 2 years ago, # |   0 Can anyone explain the E question clearly? I dont get the author's logic
 » 21 month(s) ago, # |   0 Can anyone please tell me why my code gives wrong answer for problem B ? Here's the link:https://codeforces.com/problemset/submission/1037/48669584
 » 21 month(s) ago, # |   0 For D, I made an array par, for which, par[i]=j means that j is the parent of the node numbered i. I constructed a queue, Q that is used to imitate the BFS. Now, I add the current node (first node initially) to the queue, and check whether the next k nodes (where k is the size of the adjancency list for the current node) have the current node as their parent, while adding these nodes to the queue Q. After these k nodes are checked, I remove the current node from the queue. This will work for any order of neighbor selection for the BFS. The submission can be found here. It doesn't work for the test case 12. Any ideas? I think the implementation is correct, but there is some problem with the concept.
•  » » 9 months ago, # ^ |   0 here is my submission:69550598. I ran bfs once and stored the parents and the no.of direct children for every node. Then,i made a queue and a counter j. the no. extracted from the queue is the current parent. so i check the next children no. of nodes in the input from j. if any of them does not have p as its parent,it would not have been added by any way of dfs traversal and thus we answer No. If it is a child then add it to the queue. If the loop runs successfully,we increment j by the no. of children so that we can check for the children of the next parent. I hope this explains my code.
 » 19 months ago, # |   0 Can someone explain Dynamic Programming approach for problem C?
 » 17 months ago, # | ← Rev. 2 →   0 Can anyone please tell me whats wrong with my code for the question B #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); long long n, target, cost = 0; cin >> n >> target; vector v(n); for(auto &x : v){ cin >> x; } sort(v.begin(), v.end()); long long midValue = (long long) n / 2; if(target == v[midValue]){ cost = 0; }else if(target > v[midValue]){ auto i = midValue; while(v[i] < target){ cost += (target - v[i]); i++; } }else{ auto i = midValue; while(target < v[i] && i >= 0){ cost += (v[i] - target); i--; } } cout << cost; return 0; } 
 » 14 months ago, # |   0 Can somebody point out what is wrong with my solution? https://codeforces.com/contest/1037/submission/59094440
 » 14 months ago, # |   0 Can anyone pls explain why for F, the answer is number of subsegments of length k, 2k, 3k ... ?Shouldn't it be k, 2k-1, 3k-2...? Like for example in sample input 1, there are 1 subsegments of length 2 and one of length 3. when k=2.Thanks.
 » 5 months ago, # |   0 We can perform Problem D in $O(n)$ using two-pointers.80832291
 » 5 months ago, # |   0 Can anyone help me with my submission for problem D? 83125545 I dont understand why the output of the following test case is "NO"6 1 2 1 5 2 3 2 4 5 6 1 5 2 3 4 6Please help!