Let x be # of wins, y be # of draws, z be # of losses.

We need to prove that if there is a solution where y >= w, there will be a solution where y < w.

When y >= w, we exchange w draws with d wins. The total points remains the same (from the observation), and we do not overshoot the limit as x'+y' = (x+d)+(y-w) = x+y-w+d < x+y <= n. Thus this will also be a solution.

So if we keep exchanging w draws for d wins, we will eventually end up with a solution where y < w and we cannot exchange further.

Now that it is proven, we can say that if a solution exists, a solution will exist where y < w. Similarly if there are no solutions where y < w, there are no solutions.

Thus, we search y from 0 to w-1 to find a solution, and if we cannot then there is no solution.

I don't know if it would still be relevant for you but I solved this problem completely as an abstract number theory problem: Given non-negative integers $$$n, p, w, d$$$, find non-negative $$$x, y, and$$$ $$$z$$$ satisfying $$$x⋅w+y⋅d=p$$$ $$$x+y+z=n$$$ with $$$w>d$$$. Now, express $$$p$$$ and $$$w$$$ as $$$k_1*d+c_1$$$ and $$$k_2*d+c_2$$$. This means $$$y=k_1-x*k_2+(c_1-x*c_2)/d$$$. Now again express $$$x$$$ in terms of $$$d$$$ as, say, $$$k_3*d+c_3$$$. Now you can iterate over all possible $$$c_3$$$ from $$$0$$$ to $$$d-1$$$ and find the maximum $$$k_3$$$ such that $$$y$$$ is still non-negative: This is true because it turns out that $$$x+y$$$ decreases with increasing $$$k_3$$$, so we have more options for $$$d$$$ (greedy approach).

I think you should put all the codes in a spoiler. That will reduce the size of the comments.

I'm not really able to see why E is greedy.

Suppose k was 20 and we have the following frequency table

1 -> 16 2 -> 1 3 -> 1 4 -> 1 5 -> 50 6 -> 10 7 -> 10

Wouldn't greedily first reducing 7 and then reducing 6 be worse than increasing 1, 2, 3 and 4

I tried something similar during the contest but failed. My idea was to compare which side was cheaper, but it did not work. Can somebody point out what is wrong with this logic?

62484346

Я так понимаю, что-то такое:

Заметим, что чтобы уменьшить ответ на $$$1$$$, нам либо нужно увеличить все минимумы на $$$1$$$, либо уменьшить все максимумы на $$$1$$$. При этом всегда выгодно менять именно те элементы (минимумы или максимумы), количество которых меньше.

Теперь будем делать следующее: пока у нас есть операции и массив не состоит из одинаковых значений, будем либо брать минимумы в массиве и повышать их все одновременно до второго минимума, либо брать все максимумы и понижать их одновременно до второго максимума, пока хватает операций.

I had come up with something similar, and it seemed to work on whatever examples I could find, but I can't prove correctness. Could you prove intuition on how I would go about proving this is always optimal? Thank you.

is this a usual way to code or something?

like after taking examples i understood why your code works

but did u think of this approach? how this performs on an array like 1 2 3 16 25 36 (say k = 5) is very interesting(for me)...

I'm trying to figure out how your solution works. If you are going to be sharing a code at least make it readable and name variables meaningfully, been trying to understand what the "p" variable is doing for 30 min.

I'd appreciate it if you could explain it further or resubmit something better for explanation purposes.

From extended gcd we get (x0, y0) such that ax0 + by0 = g = gcd(a, b). We then scale this to satisfy ax + by = p; x = (p/g)x0; y = (p/g)y0

We can now shift our obtained solution to (x + kb', y - ka') where a' = a/g and b' = b/g [you can verify this]

Now we have 3 inequalities:

• x >= 0 or k >= -x/b'
• y >= 0 or y/a' >= k
• x + y <= n or k >= (x + y - n)/(a' - b')

Just pick a k which satisfies all the inequalities or return -1.

---
Keep in mind that scaling will lead to an overflow in cpp. We can overcome this using the fact that there's a solution with y < w' from the editorial.

if you are using c++ then tree/undirected acyclic graph can be represented as array of vectors. if tree contains n nodes represent it as vectorvec[n+1]. to make the n-1 connections in the tree number=n-1; while(number--) { ll int a,b; cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } for more basic info refer to hackerearth theory section regarding graph.

consider sample:

10 12
1 2 3 6 7 8 9 13 14 15

2nd paragraph tells you that if there is answer that reach $$$(min, max) = (4, 12) = (L, R)$$$ then there are same amount of numbers that you need to increase, so there are also answers $$$(3, 11)$$$ and $$$(5, 13)$$$ but among them are those with $$$L$$$ or $$$R$$$ from input array. Now, other sample:

9 11
1 2 6 7 8 9 13 14 15

Think of $$$(L, R) = (4, 12)$$$ again. It require $$$5+6 = 11$$$ to make it. It's not optimal because there are two numbers that we increase, and three that we decrease, so we can move $$$L$$$ and $$$R$$$ up by one to $$$(L+1, R+1) = (5, 13)$$$, so each decreasing number will need one step less, and each increasing number will need one step greater. So, total difference will be $$$\# L - \#R$$$, where $$$\#L$$$ is number of increasing numbers, and $$$\#R$$$ is number of decreasing numbers. And, because $$$\#L < \#R$$$ this difference is negative, so result will be better. It was requiring 11 and $$$\#L - \#R = 2 - 3$$$ so it will require $$$10$$$. By anology, if $$$\#L > \#R$$$ you can change to $$$(L-1, R-1)$$$.

And... of course in this case $$$(4, 12)$$$ is not answer, because this is reason why answer must have one of bounds if amount of increasing and decreasing numbers are not equal. If they equal, then answer may have bounds from initial array or not, but there is always answer that has $$$L$$$ or $$$R$$$ from initial array.

Ingenious! I was looking for such a solution for a long time, thanks! Btw, could you please explain why you're checking p%__gcd(w,d)==0 why if this is false, then the solution doesn't exist?

I made two submissions, the first one was this -without this p%__gcd(w,d)==0 condition, got TLE

the second one was this -with this p%__gcd(w,d)==0 condition, got AC

Thank you very much. It was really helpful