My solution : CodeChef: Practical coding for everyone
Because of weak test cases Brute force passed , out of 1000+solutions(in DIv 3) , rarely few applied good algo , this is very good question (will see editorial) , if possible then rejudge with new test case .
Yeah I realized that brute force would work the moment I saw that it’s just 1 test case.
I was scratching my head for 2 hrs trying to figure out how can i perform lazy updates on segment tree then I went to the DIV 3 page and saw the number of submissions. I knew instantly that brute force would pass.
It is a textbook question, I didn’t like it, even if we ignore the weak tests. The idea is to represent every element as a degree 2 polynomial of i and use fenwick or segment tree for O(log n) updates. Here is my submission
My bruteforce didnt pass in python
can you please elaborate more .
Yes i figured this as the problem was almost similar to CSES polynomial Queries, wish i had solved it before.
Sure, first note that (x + i - L)^2 = (x - L)^2 + 2 (x - L) * i + i^2. Assuming that you know how to perform range increment queries with a Fenwick tree, you should be immediately able to add the free term of (x - L)^2. The same technique is then applied to update the linear and quadratic coefficients.
By the way, I cover all problems in greater detail in my screencast (hd is coming soon once youtube processes it)
I tried brute force in python but it showed TLE. Then after the contest end, I saw submissions and none were accepted in python, whereas c++ submissions were accepted with the same logic. Why so?
python is too slow
It looks like you are using a different (dp) approach than I did. You can try explaining it in greater detail in my discord server and I or other server members will try to help
The c++ brute force shudnt have passed either.
link ? , my brute force passed
never knew pow will cost me this much instead of just multiplying.
