Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### SPatrik's blog

By SPatrik, history, 2 years ago,

C++ code: 58307249

C++ code: 58307265

C++ code: 58307281

C++ code: 58307302

C++ code: 58307320

$O(n^4)$ complexity solution for problem E1 by KAN: 58306483

• +37

 » 2 years ago, # |   +37 Can anyone give a mathematical proof for Div 2 B, second point? It seems correct intuitively, and not able to come up with counter cases. How does everyone discover this fact?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +20 At each turn, take the maximum element and the minimum element, and reduce each by 1. At this point the second point still holds true.Consider the case when the maximum element got reduced by 1, and it became not the maximum. Then the sorted array looks like this:$....., x, x - 1.$Since the total sum is still even, there is another positive element ($\ge 1$), apart from these two. Then $x \le (x - 1) +$ "some elements, at least one of which is 1". So the second point still holds, and we continue with x as the maximum element.
•  » » 2 years ago, # ^ |   +1 I'll have a crack at a possible explanation.The problem statement instructs us to pick 2 distinct indices and reduce each element by 1. Suppose the point in consideration "The biggest element has to be less or equal than the sum of all the other elements." were to be false. Let this biggest element be at index i. For all other indices j, if we pick (i, j) as our pair and reduce their values by 1, we should be able to see that it won't be possible to reduce the largest element to 0.
•  » » » 2 years ago, # ^ |   0 Proof by contradiction. Nice.
•  » » » 2 years ago, # ^ |   0 This definately proves that if the largest element is greater than the sum of all other elements — Then all elements can never be made 0. Cool...!But if largest element is less than sum of all other elements ; how can you guarantee that it is always possible to make all elements = 0...? Could you explain this please...
•  » » » » 2 years ago, # ^ |   0 This is a great explanation.
•  » » » » » 2 years ago, # ^ |   0 Thanks
•  » » » 2 years ago, # ^ |   0 Great!
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 How this test case correct answer is YES, for problem 2? Can anyone explain that?51000000000 1000000000 1000000000 1000000000 1000000000
•  » » » 2 years ago, # ^ |   0 got it
•  » » » » 2 years ago, # ^ |   0 Can you please explain this testcase I am still not able to understand.
•  » » » » » 21 month(s) ago, # ^ |   0 In this test case we are pairing one of the element with the others one by one.1000000000 1000000000 1000000000 1000000000 1000000000will turn to 750000000 750000000 750000000 750000000 0we have deducted 250000000 from the 4 1000000000s and reduced the 5th one to 0.
•  » » » » » » 21 month(s) ago, # ^ |   +3 Thanks Brother, it really helped :)
•  » » » 2 years ago, # ^ |   +1 This is like 2 2 2 2 2 We make the following changes1 1 2 2 21 1 1 1 20 0 1 0 10 0 0 0 0
•  » » » 2 years ago, # ^ |   0 5 100 100 100 100 10050 50 100 100 100 50 0 50 100 100 50 0 0 50 100 50 0 0 0 50 0 0 0 0 0
•  » » 2 years ago, # ^ |   +5 Here is another way to think about it.Consider 2 cases: Base case: the largest element is equal to the sum of all the others: Let's say that each element of the array represents the number of marbles of a given color. We can take 2 bowls. On the 1st, we put all the marbles of the largest number, while on the 2nd we put all the remaining ones. On each operation, we can take one marble from both of them. As they contain the same number of marbles, they will become empty at the same time and we are finished! Second case: the sum is bigger than the largest element: We will try to reduce this to the above case! Again, we fill the bowls with the same way. The difference is that now the 2nd bowl has more marbles. To solve this, we can begin picking pairs from it until they are equal! Note that, as the sum is an even number, the parity of the number of marbles on each bowl is the same (ie. both odd or both even). That guarantees us that we will 100% reach a point that they are equal!
•  » » » 2 years ago, # ^ |   0 But why can't we get stuck while picking pairs from second bowl in the second case? This needs a bit of explanation.I see it differently. If one element is exactly half of all, we can easily pair it with others. But if all are less than this half, then we can pick any pair (it exists, since there are at least 2 colors, since if there were just 1 color, it would have all marbles and that is not less than half). Picking any pair reduces total count by 2 (or half by 1). As soon as this "half" gets equal to any of the values, we switch to case 1. Since it gets decremented by 1, it will be equal to some of the lower values without skipping it, sooner or later.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Thanks for your reply^-^
•  » » 2 years ago, # ^ |   +1 First you must realize that finally, in last step of reduction, the array will be of form: 1 1 0 0 0 0...... So if we backtrack from here to generate all possible arrays, at each step you increment the whole sum of array by 2, but for any element, you can only increase it by 1 in that step.So even if a single element is focused on every time, max(arr[i])<=sum/2. Hope it helps!
•  » » » 2 years ago, # ^ |   0 One of the best explanations! However, this does prove that these are the necessary conditions, but how do we know these are the only sufficient conditions?
•  » » » » 2 years ago, # ^ |   0 After this constraint is applied, the question simply reduces to : Design array with given even sum and maximum element less than equal to sum/2, by incrementing any number, which is trivial to see I think.
•  » » 2 years ago, # ^ |   0 I approached to this question from backward. I considered case when we can’t reduce it further. It should have zeros and some even number, e.g. 0 0 2. If we take one step back, there were two possibilities to reach final point (either 1 1 2 or 0 1 3). 1 1 2 can be reduced to zeros, so we left with 0 1 3. It becomes obvious that we can’t reduce ‘3’ to zero, because sum of other numbers is less than 3.
•  » » 2 years ago, # ^ |   0 One more proof:Let's make an optimal selection of pairs — we would have P pairs and U unassigned.1). If U is empty — we can zero array2). If U is odd — sum of an array was odd and the answer is NO3.1). If U is even and has more than 2 elements — all U must be coming from a single A[i] because our selection is optimal.3.2). If there is a pair in P (a, b) and both a and b are not from i — we can reassign 2 elements from U and a, b and make U lower. Which is impossible because our selection is optimal. Thus, all pairs in P has one element from A[i] and other element from somewhere else. So it means, A[i] = U + P, and sum(A) - A[i] = P. A[i] must be biggest element and it is bigger than half of sum(A)
•  » » 2 years ago, # ^ | ← Rev. 3 →   +7 Explaining the case where the maximum element is less than the sum of the remaining elements:Let's call the maximum element X, the sum of the remaining elements remSum and X+remSum is the total sum.Since X+remSum must be even, then X and remSum must both be even or odd, then for remSum to be greater than X it has to be greater by an even amount remSum = X+2*k, otherwise the total sum won't be even.Consider the case where X = 5 and remSum = 7 Notice: remSum is greater than X by 2 (an even amount)1, 1, 2, 3, 5 where X = 5 and remSum = 1 + 1 + 2 + 3decrease remSum by 2 using any pair of elements from remSum, e.g. the pair at indices 0 , 3the resulting elements are 0, 1, 2, 2, 5 Now X = 5 and remSum = 5, subtracting X from all elements of remSum will then result in an array of all 0's. Using this fact, we are sure that for any case where remSum > X and remSum+X is an even number, we can always remove the extra even amount 2*k from remSum and reach a feasible state where the sum of the remaining elements is equal to the maximum element.
•  » » » 2 years ago, # ^ |   0 How can you explain this with [3, 5, 6]
•  » » » » 2 years ago, # ^ |   0 $X = 6$, $remSum = 8$ (both numbers are even and remSum is greater than X by an even amount $8-6=2$Subtract 1 from 3 and 5, now remSum = 6 and X = 6.
•  » » » 2 years ago, # ^ |   0 Really good explanation. Thanks!
•  » » » 20 months ago, # ^ |   0 Hey. Can u pls show its working on 1,3,4,4
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   0 X=4 and remSum=8 (both numbers are even and remSum is greater than X by an even amount) 8−4=4Subtract 1 from 1 and 4 to get 0 3 3 4, now again X=4 and remSum = 6 thus, 6-4=2, so subtract 1 from 3 and 3 to get 0 2 2 4.Now we would get 0 0 0 0.
•  » » » 17 months ago, # ^ |   0 Really great explanation....
•  » » » 16 months ago, # ^ |   0 HOW is this test case make all element to zero3 4 8 10
•  » » » » 15 months ago, # ^ |   0 4 8 10 -> Subtract 1 from 4 and 8 3 7 10 -> Subtract 3 from 3 and 10 0 7 7 -> Subtract 7 from 7 and 7 0 0 0
•  » » » 15 months ago, # ^ |   0 Nice explanation, thanks man!
•  » » » 14 months ago, # ^ |   0 So,Concluding,Let's call the maximum element X, the sum of the remaining elements S. There are finally 3 cases(Considering (X+S) is even,else it will be "no") : X > S : Never Possible X == S : Easily possible ,just keep subtracting 1 from both parts X < S : Either X is even & S is even or X is odd & S is odd,Keep decreasing S by 2 till it is equal to X and after that it is Case 2.
•  » » » 13 months ago, # ^ |   0 Tell me how do you guys think in such ways...I mean how its easy to prove the conjecture but tell me how do you approach the problem...
•  » » » 13 months ago, # ^ |   0 it's really helpful.....
•  » » » 13 months ago, # ^ |   0 Thanks for this great explanation!
•  » » » 9 months ago, # ^ |   0 Really good explanation. This should be part of the Editorial. But a really interesting question and explanation. Thanks.
•  » » 8 months ago, # ^ |   0 he made the question and god knows the proof ..
•  » » 8 months ago, # ^ |   0 I am 18 months late, if anyone still has a doubt...here you go Let the elements of the array be [a,b,c,d] where d is the largest elementLet us assume d is smaller than or equal to a+b+c (sum of all other elements)d = a+b+c — delta we know that d+a+b+c is even, 2(a+b+c) — delta is even and hence delta must be even.Now, we can keep picking any 2 elements from [a,b,c] and reduce them delta/2 times so that d becomes equal to a+b+c...
 » 2 years ago, # |   0 Can someone help me? I cant find what's wrong with my code. https://codeforces.com/contest/1201/submission/58307080
•  » » 2 years ago, # ^ |   0 I am not sure, but try to swap rows "cin.tie(0)" and "iostream..."
•  » » » 2 years ago, # ^ |   0 It doesn't work. :(
•  » » » 2 years ago, # ^ |   0 He shouldn't swap them. ios_base::sync_with_stdio(false) or equivalent resets cin.ties state. So you should always have them in that order.
•  » » 2 years ago, # ^ |   0 in using colum[where[j]+k], where[j]+k is an invalid index. it is accessing an index beyond size of the vector.
•  » » » 2 years ago, # ^ |   0 I fixed it but it still doesn't work. I don't know why. And it doesn't work in test case 1 in CF but in works when I try it in Xcode... https://codeforces.com/contest/1201/submission/58320302
•  » » » » 2 years ago, # ^ |   0 ll where[m] is not initialized properly. You forgot to assign values from 0 to colum[0]. So it causes an index overflow when you try to refer to colum[where[j] + k]
•  » » » » » 2 years ago, # ^ |   0 yeah, you are right! thank you!
 » 2 years ago, # | ← Rev. 2 →   +2 Bonus: solve problem C with linear time complexity.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +9 Was binary search actually necessary? I thought that simply sorting and maintaining how many elements would require updating to increase the median for each i between n / 2 and n would suffice.For instance, if the initial median were some 'x' and the successor of 'x' were to be 'y' in the given array, it would require 'y' — 'x' updates to make 'x' = 'y'. Now, as any further increments to 'x' would yield 'y' as the median, it mandates updating both terms (equal to 'y') to their succeeding value. This can be maintained using a 'termsToUpdate' counter.
•  » » » 2 years ago, # ^ |   +8 Sorting is not linear.
•  » » » » 2 years ago, # ^ |   0 Oops, my bad. Though, I guess a similar technique could be used with quickselect. Not too sure about it.
•  » » » » » 2 years ago, # ^ |   0 I guess no because we not only want median but also number greater than median in a sorted order so I think sorting has to be done.
•  » » 2 years ago, # ^ |   0 Note that the array has to be sorted.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +10 Sorry, I didn’t notice that the array in this problem is not sorted. It was hard to notice it for me because I have the same problem with sorted array in Polygon. Of course I meant linear solution with sorted array. Sorry for misunderstanding.
•  » » » 2 years ago, # ^ |   0 Well I guess sorting of integers $<=10^9$ with $N$ equal to $1e5$ might be considered as linear [almost].. just 2 counting sorts
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 58273442 Is that what you meant?
•  » » » 2 years ago, # ^ |   +4 Yes, something like that.
•  » » » 2 years ago, # ^ |   -8 can you please explain your solution?
•  » » 2 years ago, # ^ |   -7 Well, if we ignore the complexity of sorting the array then we can just iterate from i=n/2 to i = n-1 and keep making all elements between n/2 to i. equal to A[i]. We break the loop if k goes negative. Here is code. https://codeforces.com/contest/1201/submission/58290181
•  » » 2 years ago, # ^ |   -8 why I am getting WA on test 25 submission link: div2/a
•  » » 2 years ago, # ^ |   0 Igoring sorting, my solution is pretty fast.58914655
 » 2 years ago, # |   +22 Proof for B:Claim 1: the initial sum must be evenThe operation does not change the parity of the sum. Since the sum of an array of zeros is even, the initial sum must also be even.Claim 2: assuming the initial sum is even, then it is necessary and sufficient that there is no element in the initial array that is larger than half of the initial sumTo prove necessity, consider an initial array with an element that is larger than half of the initial sum. Thus, this element is also larger than the sum of the other elements. Separate this from the other elements. Notice that, each operation either subtracts 1 from the element and subtracts 1 from the others, or subtracts 2 from the others. Thus, we can only subtract as much from the element as the sum of the others. Since the element is larger than the sum of the others, it will not reach zero.To prove sufficiency, we notice the following properties of an array of zeros: its total sum is zero and its largest element is not larger than its total sum. Since each operation decreases the total sum, we will eventually reach zero. Call an array good if it has no element larger than half of its total sum. Thus, we only have to prove that we can always perform an operation on a good array with nonzero sum such that the result array is also good. Consider a good array with nonzero sum. We claim that subtracting 1 from the two largest elements will result in a good array. Note that there is at least one nonzero element since the sum is nonzero. And there are at least two since the array is good. Thus, it is always possible to subtract from two elements. If subtracting from the two largest elements doesn't result in a good array, then there is an element distinct from the two largest elements that is larger than $\frac{s - 2}{2}$, where $s$ is the sum of the array before subtracting from the two largest elements. Since the two largest elements are at least as large as this element, the total sum before subtraction is at least $3 \cdot \frac{s}{2}$ but at most $s$. However, this leads to the inequality $s \leq 0$. Since the sum can never be less than zero, $s = 0$. However, we assumed that the sum is nonzero. This is clearly a contradiction. Thus, subtracting from the two largest elements of a good array will always result in a good array.
• »
»
2 years ago, # ^ |
0

# include <bits/stdc++.h>

using namespace std; int a[200005]; int main() {

int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>a[i];
}

sort(a,a+n);

int med=a[n/2];
long long mid;
long long l=med;
long long r=2000000009;
while(l<=r)
{

// mid=(l+r)/2;
mid = l + (r-l)/2;
//cout<<mid<<endl;
long long op=0;

for(long long i=n/2;i<n;i++)
{
if(mid>a[i])
{
op+=(mid-a[i]);
}
}

if(op==k)
break;

else if(op > k)
{
r=mid-1;
}
else
{
l=mid+1;
}

}
cout<<mid;

return 0; }

Could you explain why Binary search is giving wrong ans :)

 » 2 years ago, # |   0 can someone please explain D solution in english
•  » » 2 years ago, # ^ |   +4 Every time you reach a row that has treasure, you have to get all treasure before you go to the next row, so you will finally stop at the leftmost or the rightmost treasure. It's the same for the next now that has treasure. So you can just calculate the cost of 4 paths: L1->L2 / L1->R2 / R1->L2 / R1->R2 , and save the minimum of L2 and R2 for the next row, continue to do the same thing.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 i am not able to understand the four paths which you are talking about,can you please elaborate a little.what i am thinking is left -> leftand left -> right and right -> right and right -> left.am i thinking right
 » 2 years ago, # |   0 A minor issue for time complexity in problem C. The sorting is already O(nlogn). Or is it supposed to ignore such trivial operations in complexity analysis? Besides, a linear implementation to solve the problem after sorting is here.
•  » » 2 years ago, # ^ |   0 O(nlogn) + O(nlogn) = O(nlogn)
 » 2 years ago, # |   0 What's in the 6th testcase of Problem C?If anyone figured it out?I am unable to find the error in my code which is failing at this testcase. link to my code
•  » » 2 years ago, # ^ |   0 Never mind.Thanks
•  » » » 2 years ago, # ^ |   0 Can you share how you solved it? I am stuck at test 6 as well.
•  » » » » 2 years ago, # ^ |   0 Check on cases when the next candidate for the median does not lies in the array.You can also see the difference between my AC code and code failing at TC-6. Use this case- Input 13 11 3 3 1 2 3 3 3 5 6 9 10 3 8 Output: 7
•  » » » » » 2 years ago, # ^ |   0 Thank you so much!
•  » » » » » 15 months ago, # ^ |   0 but they mention that : The median of the odd-sized array is the middle element after the array is sorted in non-decreasing orderthen why to check for element which is not present in array?
 » 2 years ago, # |   +1 Can someone please explain C in detail, I am not able to understand it.
•  » » 2 years ago, # ^ | ← Rev. 4 →   0 So to get started, if we need to get the median of an array, we first sort that array and take the middle element (suppose the array length is always odd).Consider a median in an sorted array. It is guaranteed that all elements on the left of the median are less than or equal to the median, and all elements on the right of the median are greater than or equal to the median.The idea is to first preserve the element that is the median of the array, and by "preserve," I mean that the element would stay at its position and would not move anywhere. The only thing happens is that the element (which is also the median) gets increased.The only (valid) operation here that can be performed is +1. For the median to increase in value, while still stays where it initially is (in an sorted array), the median itself and all elements to its right side have to increase accordingly.By "accordingly," consider this sorted array:1 2 2 3 5 7 7The median here is $3$. If I am to apply +1 two times on the median, it will be $5$ and it would still be the median. However, if I apply +1 three times on the median, it will be $6$ and will not be the median anymore, so to preserve its position, I have to increase the element $5$ after the median $3$ as well, which means one more +1 operation. (If we don't keep the current median's position, we will waste some +1 operations.)The solution in the editorial uses binary search. Suppose I am to achieve a median of $x$, then a certain number of +1 operations will be applied to match everything I have mentioned above. A smaller $x$ requires fewer +1 operations, while a bigger $x$ requires more. Binary search is applied to find out the maximal $x$ that we can achieve, while still satisfy the constraint for $k$ (the number of +1 operations allowed).$\sum_{i = \frac{n+1}{2}}^{n}{max(0, x - b_i)}$ could be interpreted in this way: Go from the median position to $n$, if $x$ is greater than $b_i$ then we add $x - b_i$ to the total number of +1 operations being used(, otherwise if $x$ is not greater then we just add zero, which means no any +1 will be used on $b_i$ (because +1 operation is there to increase an element's value and in this case we try to raise elements up to $x$ using +1 operations so if $b_i$ is already greater than $x$ then we don't even need any +1 operations)).A few more observations on the sorted array, you may figure out a linear solution (on a sorted array) to find out the answer.
•  » » » 17 months ago, # ^ |   0 Could you please explain with an example? I and confused about the value of 'x'.
•  » » » » 17 months ago, # ^ |   0 $x$ here is the target value of median. The concept of binary search used here is to achieve the greatest $x$, which is the greatest target value, that is possible.Suppose the array is 1 2 2 3 5 7 7 and we can do at most $10$ +1 operations.Easily we can see that the median is 3 in that array. Suppose I go for a search for $x \in [3, 100]$ (the end value should not be $100$ actually and it should as large as possible so you can search for the largest $x$).The first round of binary search would yield $x = 3 + \lfloor\frac{100-3}{2}\rfloor = 3 + 48 = 51$. Now we test for $x = 51$. Here 3 in the array would require $48$ +1 operations to get to $51$, and when it goes to $51$, it will be greater than the 5 right after it in the array, and we will have to raise it to at least equal to $51$ which is the raised value of the previous element, which will require $46$ +1 operations, and so on to the last element of the array. Easily we see this whole test for $x = 51$ requires far more +1 operations than we are allowed. Therefore, we aim to reduce to value of $x$ in the next round of binary search. Otherwise, if we had unused +1 operations, we would aim to increase the value of $x$ in the following round of binary search. Doing this repeatedly, we get the value of $x$ satisfying the problem.
•  » » » » » 5 months ago, # ^ |   0 Thanks, for the great explanation.
 » 2 years ago, # |   0 How it's 4 possibly for every row in problem D? 1- we can go to rightmost and then left most and then to the closet safe column to the leftmost one treasure. 2- we can go left and then right and then to the closet safe column. (reverse order of 1)what possibilities im not considering?
•  » » 2 years ago, # ^ |   0 Closest safe columns right to the leftest treasure, left to the leftest treasure and same for rightest treasure.
•  » » » 2 years ago, # ^ |   0 So cant we get the minimum of the right and left safe column?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 2 23 3 3 1 19 2 22 2 1 1 16 23 correct answer: 45
•  » » » » » 2 years ago, # ^ |   0 So how we can see which one is better? Do we need to check that if we go left then at the next we have to go there? And if its then it will effect on other rows chooses ? So we need dp?
•  » » » » » » 2 years ago, # ^ |   0 of course we need dp, we must know answer for leftmost-left, leftmost-right, rightmost-left and rightmost-right. after we use that 4 numbers to calculate same thing for next line
•  » » » » » » » 2 years ago, # ^ |   0 Thank you very much :(
•  » » » » » 2 years ago, # ^ |   0 Why is the right answer $45$ and not $44$? One possible path of weight $44$ is $(1,1)\ ->\ (1,19)\ ->\ (1,23)\ ->\ (2,23)\ ->\ (2,22)\ ->\ (2,2)$.
•  » » » » » » 2 years ago, # ^ |   0 sorry, I thought that third treasure was at 2 1
 » 2 years ago, # |   0 The third problem is pretty good！
 » 2 years ago, # |   0 Can anyone please explain me the solution of 3rd problem, i am unable to understand the editorial.
•  » » 2 years ago, # ^ |   0 Take a look at my comment here.
 » 2 years ago, # |   0 In problem D if we assume that each row has atlest one treasure then does this greedy computes optimal answer?Move in zig-zag fashion i.e. In first row collect treasures in order from left to right. In second row from right to left, in third from left to right and so on.
•  » » 2 years ago, # ^ |   0 Why there must be a treasure to the left of it?
•  » » 2 years ago, # ^ |   0 That doesn't ensure minimum number of moves.
 » 2 years ago, # | ← Rev. 3 →   0 .
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 1 2 3 6 8 -> 1 2 3 0 2 -> 1 1 2 0 2 -> 0 0 0 0 0 // done
 » 2 years ago, # |   0 I have solved in this way. (div2/c) can anyone tell in what catergory my solution goes? (Binary Search, greedy, math)? submission: link
•  » » 2 years ago, # ^ |   0 What do you think? Looks greedy to me
•  » » » 2 years ago, # ^ |   0 I don't even know what does greedy means. That's why I asked.
 » 2 years ago, # |   0 Could someone tell me what's wrong with my solution for D https://codeforces.com/contest/1201/submission/58341150
 » 2 years ago, # |   0 can someone explain problem C editorial better please?
•  » » 2 years ago, # ^ |   0 Yeah, specifically the method of applying binary search in this condition.How do you realise that binary search must be done?
•  » » 2 years ago, # ^ |   0 Take a look at my comment here.
 » 2 years ago, # |   0 I'm curious if anyone has Greedy solution for Treasure Hunting (D) (Greedy tag)
•  » » 13 months ago, # ^ |   0 I think we can simply use dijkstra algorithm as this is akin to minimum cost to reach destination from source problem, where there are 4 nodes in every row58326485
 » 2 years ago, # |   0 can anyone explain me how problem one works?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 There are $m$ answers for each of $n$ students in class. To hope for the maximum score possible, for each question, ask every student in the class about which choice he/she gave on the exam, and take into account the choice that most students chose for that question. In other words, suppose the majority of students in the class chose B for question 1, then let's say B would be the correct answer. Similarly for all other questions.
 » 2 years ago, # | ← Rev. 3 →   0 Isn't time complexity of editorial's solution for problem C nlogn+log(1e9)? Someone please fix me if I'm wrong about that.My solution for problem C. Complexity: nlogn + n/2 58305249
 » 2 years ago, # |   0 Hey, I came up with an O(nlogn) + linear time complexity for Div2 C, kindly correct me if I am wrong or a similar solution has been posted! Sort the array (nlogn) Start from the middle (A[n/2]) Find the current max Change required += (curr_max — old_max) * (len-1) When change exceeds k, quit answer is (max + ((k-change)/len)) https://codeforces.com/contest/1201/submission/58301289
 » 2 years ago, # |   0 Can anyone explain me how the answer for the "B. Zero Arrays " for the 5th test case " 5 1000000000 1000000000 1000000000 1000000000 1000000000 " The answer is "YES" How ??
•  » » 2 years ago, # ^ |   0 consider 5 2 2 2 2 2
•  » » 2 years ago, # ^ |   0 And why the condition 2: The biggest element have to be less or equal than the sum of all the other elements Have to be satisfied ?
 » 2 years ago, # |   0 n,k=map(lambda n:int(n),input().split(' ')) a=list(map(lambda n:int(n),input().split(' '))) a.sort() m=(n-1)//2 add=0 i=m while(ik: break k-=a[i+1]*diff-add i=i+1 print(a[i]+k//(i-m+1)) This is my solution to div 2 1201C problem.It is showing wrong answer on test6.Can anyone tell me where is the bug.It seems pretty confusing to me.
 » 2 years ago, # |   0 Implementation of D seems hard for me. Can someone help me to implement or share an easy implementation if they feel?
 » 2 years ago, # |   0 please somebody help me,i cannot understand solution of C problem
•  » » 2 years ago, # ^ |   0 Take a look at my comment here.
 » 2 years ago, # |   0 How is the problem B different from the array partition problem, where you have to divide the array into two equal sum subsets. If yes, then are the two given condition sufficient to solve that as well?
 » 2 years ago, # |   0 In Div2 B, for n=4 and arr={2,4,4,8}. It can't be reduced to zero. But from above idea it is possible.How?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 @var_i arr={2,4,4,8} can be reduced to zero This is how it can be done 2 4 2 6, 2 2 2 4, 2 2 0 2, 2 1 0 1, 1 1 0 0, 0 0 0 0
•  » » » 2 years ago, # ^ |   0 oh, i missed. Thanks.
 » 2 years ago, # |   0 What's the problem with this submission https://codeforces.com/contest/1201/submission/59435091 and the approach? I am iterating on the sorted array from n/2 and storing the increase required for all numbers to become equal till i.
 » 2 years ago, # |   0 For Problem Cinclude using namespace std; int a[200005]; int main() {int n,k; cin>>n>>k; for(int i=0;i>a[i]; }sort(a,a+n);int med=a[n/2]; long long mid; long long l=med; long long r=2000000009; while(l<=r) {// mid=(l+r)/2; mid = l + (r-l)/2; //cout<a[i]) { op+=(mid-a[i]); } } if(op==k) break; else if(op > k) { r=mid-1; } else { l=mid+1; }`} cout<
 » 2 years ago, # |   0 In Maximum Median, 2nd example, shouldn't the correct answer be 4?We start with [1, 1, 1, 1, 2]Then [1, 1, 2, 2, 2] (2 increases)Then [1, 1, 3, 3, 3] (5 increases)
 » 17 months ago, # |   0 Can someone please take a look at this submission of mine? 77055671 I don't know why my program gives zero as the output on test 9. What could have caused the problem? Just to check, I hardcoded that testcase after the contest and the solution got accepted here 77057010
 » 15 months ago, # |   0 Can anyone please explain me the point 1 of Div2 B . Like how they have arrived at the conclusion.
 » 12 months ago, # |   0 DIV2 D is very similar to this 1066F - Yet another 2D Walking
 » 6 months ago, # |   0 In problem C, in binary search, why do we take middle element as (l + r + 1) / 2? and why does the standard l + (r — l) / 2 TLEs?