Brute force passed [CHEFQUER] | Codechef june 2021 Starters

Q : DIV1
Q : DIV2
Q : DIV3

My solution : Solution: 48291124 | CodeChef

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 .

3 Likes

Yeah I realized that brute force would work the moment I saw that it’s just 1 test case.

1 Like

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.

3 Likes

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

4 Likes

Solution: 48287014 | CodeChef

huh why didn’t my pass then.

by the way u got good rank in june cook off :slight_smile:

2 Likes

My bruteforce didnt pass in python

1 Like

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.

6 Likes

By the way, I cover all problems in greater detail in my screencast (hd is coming soon once youtube processes it)

1 Like

Any one will tell me what is wrong in my code Sleep cycle

Code
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?

replace pow(x,2) → x*x

https://www.codechef.com/viewsolution/48304305

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

yeah, used same approach,
My Solution : Link

The c++ brute force shudnt have passed either.

2 Likes

link ? , my brute force passed

:sob: :sob: never knew pow will cost me this much instead of just multiplying.