Dominater069's blog

Invitation to CodeChef Starters 139(Rated till 5-Stars) — 19th June
By Dominater069, 6 months ago, In English

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:

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!

  • Vote: I like it
  • +34
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

domi orz

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for quality problems.

→ Reply
»
6 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Hoping for C++23

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My day is ruined by the quality of the last problem and my disappointment is immeasurable.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    18o3 I know you were competing on leetcode a lot and they like such problems there but on codechef it's just meh

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    sorry :(

    O(LB) was kind of cute to me. It isnt 18o3's fault.

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what was the idea behind B problem the divisor one problem.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    greedily choose the island and check if they can be removed from the graph

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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$$$.

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't the answer function of destroying bridges monotonic? Or else why would bs fail?

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

div2 C was cute

→ Reply