Disclaimer : I just want to highlight some simple techniques used to solve Ad-Hoc tasks.
In my opinion, these are all simple techniques, but a lot of these are used even in much harder problems. I hope these will be helpful to some people.
1: Eliminate obvious cases, and see if you can simplify the problem.
How do we get to the solution here.
We eliminate any weight >w, as that is useless. We can use any weight s that is w/2 < s < w. Therefore, we essentially need to solve only for small weights. Now it is easy to see you wont "jump" over the range.
2: Ignore unnecessary information, and use it to draw the problem in new ways.
Firstly notice, numbers we will not remove are really not different at all. So we can represent them with a .. Let i be the number we will remove in the ith operation.
Now we have something like ..2...1..4..3.... This is just to illustrate our transformation.
Now notice, that .i. will give .. no matter which side you choose. Notice that i is now removable. So now its obvious to see that operations are independent.
3: Making obvious lower and upper bounds, and proving they are constructible.
Consider the fact that if there are $$$A_i$$$ people in the subtree of $$$i$$$, they will all be distributed among the leaves in the subtree equally at best. So its clear, that the answer must be at least $$$\lceil A_i / Leaves_i \rceil$$$.
Now notice that if the answer for all the subtrees of some node's children was lesser, then we can easily distribute the new people among the leaves equally.
If its not, we can still assign greedily to the leaf with the least people, and it cannot exceed the maximum, because that would imply that the minimum is $$$ \ge\lceil A_i / Leaves_i \rceil$$$, which is not possible, because that would mean all the people are used up.
4: Finding invariants
When you set all 3 to $$$a_i \oplus a_j \oplus a_k$$$, notice that the xor of the full array is an invariant. This tells us that it is impossible to make all elements equal in an even length array if the xor of the full array is not 0.
There is another Ad-Hoc observation required to complete the construction.
Notice that if $$$A_j = A_k$$$, its essentially setting the values of them to $$$A_i$$$ when you do the operation. So if we make equal pairs, we can easily solve in floor(n/2) moves. Making equal pairs is also really easy. Just do operations with all pairs with a pivot element. Clearly this will work only in an odd length array.
This proves we can construct the solution for any odd length array. Now notice that if the xor of an even length array is 0, and we make the first n-1 are equal, that means that the last element will automatically be equal, because xor of the array will remain 0.
5 : Define something that cannot change much.
Lets think of the string like links 1 — 0 — 1 — 1 — 0 — 0 — 0 — 1. We dont want any 0 — 0 link, or 1 — 1 link.
Reversing a substring breaks and creates at most 2 links. if both the ends of the substring is the same, then the number of 0-0 and 1-1 links remains the same.
I just want to clarify, that this alone does not prove that it is never optimal to do this, just that it doesn't reduce our measure.
We can also show that the number of such links is reduced by at most 2, and that is done by choosing some 0 — 0 link and some 1 — 1 link.
So a lower bound on the answer is the number of bad links/2.
So now we want a 1 — 1 and 0 — 0 link.
Now the problem is, this doesn't always exist on a string such as "1001". That means that this solution is incorrect.
Notice that the last and first characters must also be different. Lets redefine our formation and include that link. Now each 0 and 1 has 2 links, so if there is 1 — 1 link, there is a 0 — 0 link matching with it.
So now the lower bound is bad links/2, and this time we can also construct it. And therefore this is the answer.
Step 1 : Rewrite the operation as subtract the values of b from a
Step 2 : Eliminate the obvious : 2 consecutive equal elements can have the same operations performed on them to get 0 so we only care about distinct elements.
Step 3 : If we subtract too much, then the array may get unsorted, then its impossible to write it as the sum of sorted arrays, so make sure to not do that.
Step 4 : Now notice every place where we increase the value of B, can make at most 2 values equal, so we can reduce the number of distinct elements by at most k-1. We can always do this easily.
Step 5 : We need distinct elements to be 1. If we manage to do that, then we can just add that values to all elements of an operation, to not add extra moves, So they are equivalent if you do a move.
Lets redefine n to be the number of distinct elements. if n == 1, then we need one move. if k==1 and n!=1 then it is impossible. if k!=1, then answer is ceil(n-1/k-1).
What's Ad-Hoc tasks?
An Ad-Hoc task is something that doesn't fit into any specific topic. These are questions whose solution you have to come up with completely by yourself.
Ad-Hoc seems like a abbreviation,is it?
Ad-Hoc is actually a Latin phrase, that means "to this"
Google phrases it better :
great post with perfect examples.
omg thank you for this everule <3
I hope you reach LGM soon!
Nice blog!
Suggestion: Try to include the abridged problem statement within the blog for uninterrupted readability.
I'm OK without the abridged problem statements, because part of the skill is reading the problem statement and understanding the core idea (and especially people who read this blog because they struggle with As and Bs can probably benefit from practicing this skill).
I would say there's no reason to put the problem link in a spoiler block, though, since it's only 1 word/line anyway.
I just meant it in the sense that it's a little inconvenient to switch tabs repeatedly while reading a blog.
And yes I agree that there was no reason to put it in the spoiler block, but I didn't point it out because it's not a big issue anyway.
I think instead of "question", "problem" or "task" are more appropriate here.
Radewoosh loves you
Thanks for sharing the resource. I will try to use these methods!
Congrats on reaching red! That was fast! orz
that helps me a lot!