It turns out that randomly guessing works in Div. 1 too...
I have reached GM thanks to randomly guessing. Ask me anything!
Since I have already argued in theory how randomly guessing helps CF rating, I figured that I might as well compile a list of problems I guessed on my way to GM, to give some empirical evidence to all esteemed grandmasters before my rating falls off. So let us get started!
1975D — Paint the Tree
Just solve the problem manually and claim it is the best solution. Surely it is.
1967C — Fenwick Tree
Have you ever played the game 'find next number in the sequence?'
1965C — Folding Strip
- Just fold whenever you can!
- Wait. What if I get stuck somewhere...
- Well... You can always randomly guess that you will never get stuck! Surely that works. Source: Trust me bro
1951
By now you have seen many problems that can be randomly guessed. But have you seen an entire contest that can be randomly guessed?
Auto comment: topic has been updated by Zhtluo (previous revision, new revision, compare).
For 1951E, fair enough, I wasn't able to get the smart approach though, I proved it (inside my code, which was basically just an explicit constructive solution). But for 1951D, I think it's slightly iffy... I don't think you can call it guessing when the proof is basically immediate.
By the way, I'm kind of confused about why you didn't include 1975C, because it's also a pretty textbook example.
I didn't include everything, just a few that came to mind.
I should add more indeed.
For 1965C, if you are able to recognize it's actually taking prefix sum multiple times, then it would be quite well known that the coefficient is like that. One way to think of it is to view it as counting path on grid or if you are familiar with generating function, you will know it is actually $$$[x^{\Delta d}]\frac{1}{(1 - x)^k}$$$ then you can know it is some binomial coefficient according to binomial theorem (Replacing x with -x yields:... part).
I think this misses his point that he seems to be pushing in his last few blog posts which is that at least while taking contests guessing is faster and more optimal than proving solutions.
I am not sure I completely agree with his philosophy as the quality of my guesses tends to be directly related to the quality of samples.
Yeah, I kind of agree sometime guessing is more optimal for certain kind of problem. I just want to state for that problem it's possible to not guess (even don't need to prove) if you have some prerequisite knowledge.
No need to have prerequisites, its just a simple induction.
All of his problems are eztremely easily provable, he just avidly tries to not prove if he is being truthful in the post.
idk, I feel like proving yesterday's C would be a pretty big headache (and also Global Round E, which was a very long process to do it the rigorous way, speaking from experience here). Also, Folding Strip as well, because proving it seems kind of hard, but "I'm pretty sure this works..." is ok since this is a CF contest. I don't agree with him putting Global Round D here though, because the proof is almost obvious after "guessing" the answer.
yesterdays C is one of the easiest examples surely..... the other 2 i agree.
I assume you have reduced to maximum subarray median, say answer is x . Transform array for >= x into +1, and < x into -1. We want a subarray of length >= 2 which has positive sum (just check with binary search smh). checking subarrays of lengths 2 and 3 is sufficient because you can just make larger subarrays as sums of those subarrays. (for example split 5 into 2 + 3, split 6 into 2 + 2 + 2)
Folding strip, the only non trivial to prove but "it works" part is that the final string should be alternating. I dont think that was the hard part of the problem in any way. Once you realize that the initial string can be viewed as a walk on the final string, its essentially solved.
That E i agree.
Ok fair. I thought reducing to max subarray median was the nontrivial part, but now that I think about it it's also pretty easy, so you can remove that. But in general, I feel like the point of this blog is just "It's more efficient to guess sometimes (yes, not all the time, which this blog does not address) so don't be afraid to guess", not like "oh CF is just guessing, just improve ur guessing skill so ez"
Amazing proof for yesterday's C, thanks
Nice proof for C!
I reduced it to the max subarray median, but didn't see that proof. Instead I coded BSTA and got the max subarray sum using Kadane's algorithm after applying that reduction to 1 and -1.
Can you share your thought process(proof) for yesterday's D? why the particular solution will be the most optimal... Would love to know as you solved that question in ten minutes.
the token pA becomes useless once pA and pB meet up because it can always just move ahead of the pB.
Suppose they met up at node x, then the answer is obviously 2 * (n — 1) — max(distance from x) + max(distA[x], distB[x])
You can even directly calculate this expression by bruteforcing x from 1 to n (and using the fact that maximum distance from a node is one of the diameter endpoints), but ok if you want proof of why x = mid(a, b) call that y, works.
If you meet up at say a neighbour of y instead of y itself, max(distA[x], distB[x]) term definitely increases by 1, while max(distance from x) may or may not decrease by 1. Even if it did decrease, your gain is 0. Similarly, you can go the neighbour of neighbours of y, and apply the similiar reasoning to get an inductive proof. There is one more case when max(distA[x], distB[x]) may actually decrease, but that is just obviously bad (and also easily provable that you can instead use a or b as a meeting point and be better of)
Thanks for the explanation, super easy to understand. I think you made a typo?(The answer should be + max(distA to x,distB to x)
thanks, corrected
Goated explanation. However, in the contest, I did not prove it. I just ran on some test cases and proceeded to the implementation.
Sometimes I think when you have proved your logic, you can write the code more confidently and you implement the solution fast. But sometimes it is too hard to prove the logic. What a man can do is just believe in his gut feelings.
What are your thoughts about it?
That's true. I try to make up small examples to counter my guess instead of looking at the samples.
I tried it for an hour or so, but still didn't get it (skill issue xd). On the other hand, some people who printed the values of the coefficients with bruteforce got it in like 20 minutes, so I think at least for this problem guessing is very efficient.
Maybe it's also because I was hung up on the wrong idea for a long time (I was trying to do binary exp xd), but I'm pretty certain that if I had just tried printing the coefficients even once with bruteforce, I would have a high chance of getting it.
I guessed the coefficients, then directly used my polynomial template. I didn’t even realize that I could simply use the generalized binomial theorem to do it, but it works.
i think i should've guessed yesterday's d as well. I still can't figure out how both will collide on same vertex if distance between them is odd :P, this made me confused. for even distances I was 1000% confirmed but odd distances killed me
Proof for 1975D is fairly simple. We want to minimise (2*n-2)+(time_to_meet-maxdepth if tree was rooted from the meeting place). Since max depth increases by at most 1 while time_to_meet increases relative to the optimal meeting spot, the function is nondecreasing, so optimal is middle.
true, he just doesnt like to prove at all, im sure if he tried he would find most of these proofs easy.
It's not obvious to me at all why the two pieces should meet first...
I am not saying proving is impossible. I am saying it's inefficient. Surely you can spend 15-30 minutes on a proof and work it out, but given how much time we have in a round I don't feel it's a good use of time when we can instead be doing more guessing, coding, etc. I think I have a theory about it in my last post.
Sir, nobody is telling you to sit down and work out details of a formal proof. Nobody does that. But not having a formal proof not equals guess.
Hmm, I don't feel I am talking about formal proof but rather ideas of a proof.
Surely no one writes down a formal proof in contest...
please refer to:my comment
Thanks for the explanation.
Still, I know that there will be a proof somewhere (e.g. tutorial) but I don't feel it's optimal to work it out in the contest...
Yeah, certainly requires some extra effort. For me personally, I find coding solutions after proving easier and with less bugs because I have more confidence and have thought more about it when trying to prove it. So I always try to spend around 5 mins to proofs. If I can't find it, I get to coding directly.
How do you get the fact that moving both pieces together after they meet is always optimal? Also, how do you prove it for the odd case? There are a lot of formal details to address in a proof, and it is not practical to prove every time in a CF contest.
The first part isn't bad at all: after the first vertex is colored blue, we definitely can't do better than the hypothetical situation of "ditching the red piece and letting the blue piece color everything blue regardless if it's actually red or not". Letting the pieces move together after that is just a construction which achieves this lower bound.
Let $$$u$$$ be the first vertex colored blue in the solution, and $$$x$$$ be the step at which it's colored. The less convincing part to me is proving that if the first vertex is colored blue at step $$$x'$$$, then it can't be more than $$$x' - x$$$ distance away from $$$u$$$. This is intuitive to me but quite cancerous to think about, so I believed it to be true.
Unfortunately, sometimes proving things completely increases time penalty and makes it more unlikely to solve more problems, and you can gain rating by being more brainless! :rofl:
there will always exist a time T when the first blue cell emerges. Let's show that at that time T, having the two pieces at the same square is optimal (there can exist equally valid solutions but no better solution.) After the pieces meet, we still want to minimise the minimal time for all nodes to turn blue. The lower bound for this amount is 2*(n-1) — maxdepth as painting a tree starting from a root node is identical to the problem. Now lets show we can achieve this lower bound. First lets have the blue piece traverse all the red cells. this is clearly possible as they will form a chain. lets also have the red piece hanging around the blue piece trying to color new red cells. We can see that the red piece will always reach any uncolored square before the red cell and that the blue piece can color a new red node every time it visits a new node. So we achieve this lower bound and therefore the algorithm is optimal.
Yes, I also guessed that the answer to problem B of yesterday’s contest would be the first two numbers of the array after sorting, and I got WA#2
Yep, then guess that the answer is max of $$$min(A_i, A_{i+1})$$$ and $$$min(A_i, A_{i+2})$$$ for each $$$i$$$
I "guessed" that tests were weak on 1975E and got a bitset through the time limit, which allowed me to achieve the rank of GM.
Congratulations on reaching GM! One day you might even reach IGM like me.
Bro's intuition is on a different level