We invite you to participate in CodeChef’s Starters 157, this Wednesday, 23th October, rated upto 5 stars (i.e. for users with rating < 2200).
Time: 8:00 PM — 10:00 PM IST
Joining us on the problem setting panel are:
Contest Admin, Text Editorialist, and Statement Verifier: Nishank IceKnight1093 Suresh
Tester: Sushil SmolBrain Raaja
Setters: Nishank IceKnight1093 Suresh, Harsh harsh__h.
Problem distribution:
- Division $$$1$$$: $$$5$$$ problems
- Division $$$2$$$: $$$6$$$ problems
- Division $$$3$$$: $$$7$$$ problems, of which $$$1$$$ is a subtask
- Division $$$4$$$: $$$8$$$ problems, of which $$$1$$$ is a subtask
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.
Good luck!
Congrats to the top 5 in Div1!
Please mention the total number of problems division wise, like Dominater069 mentions in his blogs about codechef contest?
Reminder: Contest starts in 30 minutes
in normal is good. How to calculate the number of subarrays such that the frequency of 1 equals the frequency of 3 and there exists at least 2 in the subarray. I spent the entire contest trying to implement it but I wasn't able to.
let $$$ai$$$ and $$$bi$$$ are cnt of 1 and 3 till index i respectively
$$$ai - aj = bi - bj$$$
$$$ai - bi = aj - bj$$$
this trick is same as we use in two sum problem
you can replace
1 -> -1 and 2 -> 0 and 3 -> 1,You can make a queue, which holds all the prefixes in that dont have a 2 in front of them, and then empty the queue into a map each time you see a 2
Seriously I don 't see any reason why constraint on MEDIANT is so small like $$$N\le5000$$$ I mean seriously? There was clearly an easy $$$O(N)$$$ solution , I don't even know how a $$$O(N^2)$$$ solution would look like. Why such unnecessary small constraints??It nothing but created confusion
I did it with an O(n^2) maybe he considered safeguarding idiots like me
how would you check if solution is correct or not in $$$O(n)$$$.
main observation is that if the minimum number is present after the last index of the maximum number then impossible
if possible then no matter what subarrays you choose for operation you will find a sorted array in the end
i know the solution
i'm trying to say that constraints are lowered so that CHECKER can run in $$$O(N^2)$$$ or may be something better, but surely not in $$$O(n)$$$.
oh yeah you also have a point , if checker can't check in $$$O(N)$$$ then constraints have to be lowered for sure but again then it questions the fact whether the problem should exist at the first place.Because if a contestant has a straight-forward solution for larger constraints but checker can't afford that then it's not a proper problem to appear.You may ask why?Because as a contestant , when he approaches a problem constraints mean something to him , he can't think from a problem setter's viewpoint that constraints might have been lowered because of not being able to make a checker
as a problemsetter I am telling you none of your sentences make sense
I saw a problem. Due to my own reasons, i assumed it was dp. I failed to solve it. The editorial was greedy.
Such a bad problem smh. Why didn't problemsetter tell me it is solved with greedy?
Whether you think this problem is fine or not is a separate issue, but your argument is completely invalid. Constraints exist not to tell you that do this in O(N) but to deny solutions that run in O(N^3) for example. It is not to mislead you to a solution, rather to not give hints. If you do try to infer stuff from constraints, do it at your own risk
Edit: Sorry my approach had flaws, we can't keep doing both identification of median and modification of array in logarithmic time complexity.
how will you identify and remove median in range $$$L..R$$$.
oh sorry!! Since after removing any element the array is getting modified, we can't (at my level, maybe someone can) keep doing both operations at logarithmic time complexity. If the array was constant we could have identified median using kind of merge sort tree. I'm really Sorry for wasting your time.
Video Editorial for A-D with detailed explanation
D WAS really an amazing Problem
Link : YOUTUBE LINK --Click here