Q : DIV1
Q : DIV2
Q : DIV3
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
Solution: 48287014 | CodeChef
huh why didn’t my pass then.
by the way u got good rank in june cook off
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)
Any one will tell me what is wrong in my code Sleep cycle
Thanks in Advance
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?
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
yeah, used same approach,
My Solution : Link
The c++ brute force shudnt have passed either.
link ? , my brute force passed
pow will cost me this much instead of just multiplying.