Keeping track of both Codeforces round and online team contest was a doozy, so this is only the best draft of the editorial I have. Missing problems will gradually be added, and existing explanations may improve over time. Hope you enjoyed the problems, and let me know if anything can be explained better!
UPD: okay, all of the problems are out, and most of the bugs are fixed (I hope). By the way, we had a nice discussion with Errichto on his stream about Div. 2 problems, which some of you may find more approachable. Be sure to check it out, as well as other stuff Errichto creates!
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
(Kudos to Golovanov399 for his neat grid drawing tool)
Tutorial is loading...
https://codeforces.net/contest/1459/submission/101773389 Why my solution fails in test case 21 . problem div2c
No clue what you're trying to do with the mod 3s. Try checking other's solutions for a simpler answer.
5 1 1 5 9 3 3 1
Try this test with your code and you'll get 4 as result, which is not correct. The reason it doesn't work is because you didn't count a[3] — a[2] while calculating the gcd of all (a[i] — a[i — 1])
Can someone explain why the property used in Problem C is also valid for multiple arguments?
We can show these properties by definition of $$$\gcd$$$.
Then we can extend our claim to multiple arguments by mathematical induction.
Therefore $$$\gcd(a_1 + b_j, a_2 + b_j, \cdots, a_{n-1} + b_j, a_n + b_j)$$$ is equal to $$$\gcd(a_1 + b_j, a_2-a_1, \cdots, a_{n-1}-a_{n-2}, a_n-a_{n-1})$$$.
Update: We do not need to choose adjacent differences. $$$\gcd(a_1, a_2, \cdots, a_{n-2}, a_{n-1}, a_n)$$$ is also equal to $$$\gcd(a_1, a_2-a_1, \cdots, a_{n-1}-a_1, a_n-a_1)$$$, which can be proved similarly. The important step is to express all but one integers as $$$a_i - a_j$$$ to negate $$$+b_j$$$.
It would be very helpful if you share your implementation..
If you're looking for good implementations, the best place to go is usually the top of the leaderboard (https://codeforces.net/contest/1458/standings). For instance, this is tourist's solution: https://codeforces.net/contest/1458/submission/101720547
why someone's submissions been skipped and receive no message
it's the case of plagiarism bruh
I didn't know the proof for problem B's solution but i solved it.
Endagorion Please add implementations to the problems as well it will be really helpful.
Solution sequence for Div2B is also available on OEIS. https://oeis.org/A241496. But I didn't understand the general formula. Can someone explain?
https://youtu.be/1OWGTQpfk5Y — recording of post-contest discussion with Endagorion with analysis of all div2 problems (so up to div1-D)
In problem D (div. 2) isn't the complexity O(n * k * n * A) where A the maximum capacity of a glass? Which in turn is 100^4 (since max n = 100 max k = 100 and max A = 100 )? 100^4 = 100 000 000 dp cells, so the solution should pass yes (with the memory optimization). But your complexity is O(n * k * n * A) I don't get how you got A^2 in there. Please someone explain, thanks.
Good point, thanks. I'll fix it soon.
That fix created some confusion.
A line above that, $$$A$$$ was used to denote the 'total capacity of the subset'. In the next line, $$$A$$$ is used to denote the 'maximum capacity of the glass'.
Thanks for pointing it out, I made it more clear now.
In Problem-B's explanation,
Last Line:
Shouldn't it be
where k=n/2 rounded up
, instead ofwhere k=n/2 rounded down
?Endagorion
Someone, do correct me if I am wrong.
Yes, thanks for pointing this out! Will fix soon.
Endagorion I think that in Problem-E's(div2) explanation
$$$p'$$$ should be equal to $$$v_0 + iv_x + jv_y + kv_z$$$ instead of $$$v_0 + xv_x + yv_y + zv_z$$$
this is part of the paragraph before the last one
Sorry if I am wrong.
You are correct! I'll be fixing all mistakes soon once I finish the editorial for div1F.
Why did the rating change again as it was? Endagorion
No idea honestly. Let's just let CF staff do their thing.
Ignoring the short contest time and difficulty gap, I think your rounds are generally of high quality.
Thanks for the round :)
Thanks a lot! There's always room to improve for the next time huh.
Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).
Is there a thought process on how to obtain the key observation of 'Latin Square'? It feels very clever and beautiful, but hard to come up with at the same time
In problem D(Glass half spilled), can anybody tell me , why we are considering taken glasses from n to 1 order.
Edit : The order of $$$k$$$ doesn't matter too, since we allocate $$$n$$$ 2D dp arrays for each glasses. Sorry!
We need to calculate $$$dp(i,k,A)$$$ from $$$k=n$$$ to $$$k=1$$$ and from $$$A=sum$$$ to $$$A=0$$$ order because if we do the opposite, 'duplication' will happen in case you use the same $$$dp$$$ table for all glasses. The order of $$$i$$$ doesn't matter, I think you can do either 1 to $$$n$$$ or vice versa.
Can someone explain this? I also dont understand the need to iterate backwards.
101822812 Saw this submission, this proceeds in forward direction. So I guess we can proceed both ways.
yeah, can anyone please explain why do we need to iterate backwards? Thanks in advance :)
Would the order of $$$A$$$ matter even if you're using $$$n$$$ 2D Arrays?
I'm able to get the solution following the correct ordering with only one 2D array, but I thought that the order wouldn't matter if I used a separate 2D array for each i (since there is nothing to duplicate / overwrite).
Can someone explain why this submission with $$$n$$$ 2D arrays gets a wrong answer? https://codeforces.net/contest/1459/submission/101994708
Never mind, figured it out by looking at the submission mentioned above.
The order indeed doesn't matter but I need to make sure that I copy over all the values from the previous array.
How is the graph structured in Flip and Reverse F? The editorial makes it look like something on a straight line, which cant be true
That's exactly what it looks like though: vertices are balance values in the real line.
Can Div2D/Div1B be solved using a top-down approach? Recursion with memoization?
Is almost the same as in the tutorial, think it like knapsack: If we fix a total capacity
A_s
, a total number of glasses that we are going to fillK_s
and a current glassi
.We have to choices:k_s
by 1, because we are including one more glass, and also decreaseA_s
by the capacity of the current glass. Then just call the recursive function adding the amount of water of the current glass (just like the dp in the tutorial).In order to find the solution for a
k
just iterate over all possible capacities (I did it from 0 to the total capacity of all glasses) and the answer will be the maximum value ofmin(current_capacity, dp[start_index][current_k][current_capacity] / 2 + total_water_of_all_glasses / 2)
. Here is my submission 102646662Finally finished my alternative solution for div1D.
Can someone please help me understand the proof why we can convert any two Eulerian pathS with the operation of reversing a cycle ?
In problem b if r = 51 and b = 61, then blue will win. But when r = 51 and b = 16 then they will end up equal. Am I missing something?
does anyone know the proof of this property of gcd?
GCD(x,y)=GCD(x−y,y)
or any resource for exlanation?http://people.cs.ksu.edu/~schmidt/301s14/Exercises/euclid_alg.html
Can anyone explain me the DP solution of div2-B...Please
105154843
You can draw the final possible answers for each step in the grid, and then you can summarize the rules.
In problem D why is the total available capacity necessary as a state ?
Maybe elaborate on why you think it shouldn't be.
For 1459D - Glass Half Spilled
When I used int for integer variables, I got a runtime error. 107625846
However, when I replaced all int's with int16_t, it gave AC. 107680750
This is the first time I've encountered something like this. Is there a way to avoid runtime error without using int16_t?
You use too much memory with
int
.Problem C can be solved using following identities
Instead $$$L$$$ write it as $$$R^{-1}$$$ and instead of $$$U$$$ write it as $$$D^{-1}$$$
Using these identities, we can reduce the whole expression to an expression where there is atmost one $$$I$$$ or $$$C$$$ and at most one transpose and rest $$$R$$$, $$$D$$$ and add operations which freely commute with each other.