We invite you to participate in CodeChef’s Starters139, this Wednesday, 19th June, rated for till 5-Stars(ie. for users with rating < 2200).
Time: 8:00 PM — 10:00 PM IST
Joining us on the problem setting panel are:
Setters: Shreyan Dominater069 Ray, Rangey 18o3 Raghav, Pratham prathamshalya, tushar lazywitt Gupta.
Tester: Takuki tabr Kurokawa.
Text Editorialists:Nishank IceKnight1093 Suresh.
Statement Verifier:Kanhaiya notsoloud1 Mohan.
Contest Admin : Shreyan Dominater069 Ray.
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.
The following is the number of problems in each division :-
- Division 1 : 5 problems
- Division 2 : 6 problems
- Division 3 : 6 problems
- Division 4 : 7 problems
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!
Congratulations to Top 5!
- 1st : liympanda
- 2nd : GOTKAKO
- 3rd : fuppy
- 4th : SmolBrain
- 5th : tyr0Whiz
domi orz
Hoping for quality problems.
Hoping for C++23
My day is ruined by the quality of the last problem and my disappointment is immeasurable.
18o3 I know you were competing on leetcode a lot and they like such problems there but on codechef it's just meh
sorry :(
O(LB) was kind of cute to me. It isnt 18o3's fault.
what was the idea behind B problem the divisor one problem.
greedily choose the island and check if they can be removed from the graph
Partition the set of vertices $$$V$$$ into two sets $$$A$$$ (in which vertex $$$1$$$ is present) and another set $$$B$$$. Now, if you want to disconnect vertex $$$1$$$ from all the vertices in set $$$B$$$, you shall not remove any edges which have both endpoints in either $$$A$$$ or $$$B$$$. So to disconnect them you would only remove edges between $$$A$$$ and $$$B$$$. Let the sum of $$$a[i]$$$ in set $$$B$$$ be $$$S$$$, and let the total sum of $$$a[i]$$$ be $$$T$$$. Then the cost is $$$(T - S) \times S$$$. For $$$S \leq \frac{T}{2}$$$, this formula achieves minima at small $$$S$$$, so you would one by one add smaller $$$a[i]$$$ to set $$$B$$$, until its $$$cost \le C.$$$ For $$$ S \gt \frac{T}{2} $$$, the minima is achieved when $$$S$$$ is as large as possible, so in such a case set $$$A$$$ contains the single vertex $$$1$$$. Check whether its $$$cost \leq C$$$, and then output the answer which has the minimum size of set $$$A$$$.
iam down
Isn't the answer function of destroying bridges monotonic? Or else why would bs fail?
Its not monotonic actually
Let sumc be sum of Ais of chosen islands which will not be connected to 1 and sum be sum of all Ais
Then our cost is (sum-sum1)(sum1)<=c
There is an interval where sum1 is not allowed
div2 C was cute