Handsome boy, your greedy way is not feasible. Try this.
4 3
5 2 1 1
The correct answer is 6.
but your is 7.
1 Like
you are saying you are newbieā¦ nice joke:joy:
you just literally raped (looted the honor) Editorialist and Setter by saying CIRMERGE can be solve in O(nlogn) and they are proposing the idea in O(n^3)ā¦
1 Like
Nope, I donāt think that problem can be solved in O (nlogn), but the linear version can.
I think Editorialist is just misguided by the data range, which is not an uncommon optimization strategy.
I only won the silver medal in the China ACM-ICPC Regional Championships, which means that most people are better than me.
1 Like
Smart people never admit they are smartā¦ 
3 Likes
I donāt think so since I was defeated by a lot of middle school students. 
1 Like
You lucky. China has a great education system.
When I was in middle school I used to eat dirtā¦
6 Likes
You guys are missing the point. Codechef is filled with 95% of beginners and intermediates. It was very necessary for them to solve it in O(n^3) so they can learn actual dynamic programming which most of them are not good at if we look at the statistics.
Many variations of this problem canāt be solved in O(n^2) or O(nlogn) for that matter.
But that was not the intended solution. No matter what platform it is, and no matter what is the motive of Codechef (whether to educate children), the first thing that a setter + tester for any CP problem has to do is make sure that intended complexity solution will only pass!
My solution here passes with O(n^3) complexity which I feel is the failure of the tester. CodeChef: Practical coding for everyone
In case the intended solution of this problem was not using a convex hull trick to optimise then the contraints must have been put up rightly.
I feel that a lot of people would not have submitted n^3 solution even after knowing it well, for the simple reason that the judge is not supposed to accept them for such constraints.
1 Like
I am extremely disappointed by Codechef, once again.
The dp is not very difficult to come up with, of course the CHT part is which means the n^3 solutions should be rejected, all of them.
Weak test cases though, once again.
1 Like
Please read things properly before commenting/replying to my comment. We are saying that O(n^3) is good enough for the CIMERGE Problem and NOT CCC!! HAVE A GOOD DAY!!
@loopfree i just came to know about the simplex technique so could u tell me how useful is it in competitive coding in generalā¦
What does your CC mean? Code Chef, or this problem. 
competitive coding maybe
1 Like
Wow, thereās a night owl.
1 Like
XD \hspace{0mm} \hspace{0mm}
1 Like
I support you, bro. If a problem makes such a mistake, I think Iāll be a little disappointed.
Its competitive coding, I changed it in the actual comment too.
Well, Iāll tell you most of what I know:
In the actual programming competition, I seldom encounter the problem of using simplex method, but I still think itās an algorithm worth learningā¦
However, I have met several times in practice. People who do not know the simplex method will try to use the network flow algorithm to solve these problem. Unfortunately, it is very difficult, but the simplex method can solve the problem easily. You only need some pre-knowledge of linear algebra to understand the algorithm.
This is a very good piece of information from my previous studies:
You can try this simple problem:
Cashier Employment
And simplex algorithm can also be used for minimum cost flow,
1 Like
I never heard of convex hull before, but I know now Gods exist, and the fairy tales are also true.
Although I donāt quite understand what you mean, Iām glad youāve learned something.
2 Likes