Utkarsh.25dec's blog

By Utkarsh.25dec, 3 years ago, In English

Subject: Invitation to CodeChef Starters 21 (Rated for Div 2 & 3) — 5th January

We invite you to participate in CodeChef’s Starters 21, this Wednesday, 5th January, rated for Div 2 & 3 participants.

Time: 8 PM — 11 PM IST

Joining me on the problem setting panel are:

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

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!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As an Author, I can Assure you this contest will be going to be great and is newbie-friendly.

All The Best Everyone,

Looking forward to your participation.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    Ah yes, "newbie-friendly" with last questions of either top-tier maths or DP/graph. Very friendly.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Being a newbie you should be happy solving 3-4.

      Not worrying about the questions which are out of your league as we need to take care of people who are good at coding too.

      Hope you got it.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      My man want last question in a contest to be sum of 2 numbers

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it
        yeah with 20 different condition and with complete new definition of sum.
»
3 years ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

In MEANIDIAN , for test case 4 1 1 3 3 why the ans is 4 , Can't we just add 1 to the 2nd element ==> 1 2 3 3 , therefore median = 2 and mean = 9/4 = 2

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

This is a humble request please check all the solutions for plagiarism Most of the people are cheating in the contest and to my surprise there are more than 1000 accepted submissions on the third problem within the first ~2 hours of the contest and this number will blow up to 1500+ in the next one hour Most of the participants from India have this notion in mind that the CP ratings will help them get a job and they keep cheating by literally "buying" the solutions of the problems from telegram etc.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do MEANIDIAN?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First sort the values of $$$a_i$$$, I'll assume they are sorted from now on.

    If mean < median, we clearly need to perform at least $$$sum - median$$$ increases, and we can always perform this by increasing the largest value.

    Otherwise, we increase all values from $$$a_i$$$ for all $$$\frac{n}{2} \leq i \leq n$$$ to the mean. Now the mean will also increase and we may have to perform this again, so what is the complexity of this? For median we are increasing only $$$\frac{n}{2}$$$ elements while mean considers all $$$n$$$, so for an increase of $$$x$$$ in the median, the mean increases by at most $$$\frac{x}{2}$$$, meaning the mean and the median will converge in at most $$$O(log(mean))$$$ iterations.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Couldn't get the part where mean > median

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        Hoping this helps

        Code
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Just binary search for the minimum possible median, by keeping in mind that no element should be reduced.

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Thoughts on a few of the problems:

ChefWM — Really cool idea, but wow that is a long statement. A formal statement might have worked better here even though I suspect the story does make sense for the problem. (and might have been the original formulation?)

SOS — I feel like the idea needed to solve this is too close to RGBCONST to the extent that someone who had solved that problem might have an advantage with this problem. When RGBCONST was initially suggested for the CF round we were setting I used the same compression idea needed to check it in $$$O(n)$$$ time to logically arrive at the bipartite soln for it.

MSUB121 — Fairly obvious its going to become some heavy / light node (degree > or < sqrt(n)) stuff, but its still a nice enough problem for starters. However I DO NOT LIKE the constraints on the input format, more specifically the fact that you can have pairs with $$$x_i$$$ or $$$y_i$$$ not present anywhere in $$$a$$$. There is practically no point for this when it comes to the solution or test strength as far as I can see. The only utility it probably served was trolling people like me who were using coordinate compression on the values of A using a map with seemingly magical WAs and TLEs.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Why is the maximum for ChefWM the number of prime factors of M?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    u said fairly obvious for problem MSUB121! this technique of dividing into heavy/light nodes doesn't seem intuitive. Is this some standard technique??

»
3 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Nice problemset, I loved it from beginning (And or Union onwards).

Also, how to do MSUB121? Is it dp?? I wasn't able to conclude something till the end..

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    Short answer: It is a dp where we perform operations for "heavy" nodes (more than $$$\sqrt{q}$$$ pairs) and "light" nodes (at most $$$\sqrt{q}$$$ pairs) in different ways.

    Long answer:

    Consider the naive $$$O(n ^ 2)$$$ idea, its a dp where $$$dp_{y} = max(max(dp_{x}), 1)$$$, over all $$$x \leq y$$$ for which there exists a pair $$$(a_x, a_y)$$$.

    The problem here is that the sum of the number of such "edges" for all possible $$$i$$$ can be very high, as much as $$$O(n ^ 2)$$$.

    Let us call values $$$a_x$$$ with more than $$$\sqrt{q}$$$ pairs $$$(a_x, a_y)$$$ "heavy" and those with less than $$$\sqrt{q}$$$ pairs "light".

    When we have to update the values from $$$x$$$ to $$$y$$$ as above, we can have four cases:

    • light -> light
    • light -> heavy
    • heavy -> light
    • heavy -> heavy

    For a light node $$$a_x$$$, "pushing" the answer to every possible $$$a_y$$$ such that $$$(a_x, a_y)$$$ is a pair takes at most $$$O(\sqrt{q})$$$ time since there are by the definition of a light node at most $$$\sqrt{q}$$$ pairs we can push values to so we can decide to push values in the first two cases.

    However this isn't the case for heavy nodes which may have a degree as much as $$$q$$$. However we can notice that since each heavy node has at least $$$\sqrt{q}$$$ edges, there can be at most $$$\frac{q}{\sqrt{q}} = \sqrt{q}$$$ heavy nodes. So for each $$$a_y$$$ we can "pull" the answer from every heavy $$$a_x$$$ where $$$(a_x, a_y)$$$ is a pair in at most $$$O(\sqrt{q})$$$ which handles the remaining two cases.

    So our total solution runs in $$$O(n \sqrt{q})$$$ which is fast enough.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Codechef Strategy
PS

How to solve SOS ?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    If any two blue nodes are adjacent then the answer is clearly no, otherwise:

    Lets compress all connected components of the same colour together, then if there is a path with only one colour $$$G$$$ or $$$R$$$ in them, then we will have $$$B - G - B$$$ or $$$B - R - B$$$.

    So after compressing it we can just check if there exists a single node that has two or more blue nodes adjacent to it, if so the answer is no. Otherwise the answer is clearly yes.

    Instead of compressing we can probably just do a subtree dp of some sort as well.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you share your compressing same color component solution as well as dp solution if you solved it with that idea.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I did it with even simpler method. Just don't add the edges between the red and green nodes. (Only add edges between blue — green , blue — red, red-red and green-green nodes) You will get many connected components. Run a simple dfs in every component, It's easy to see that there must be at most 1 blue node in each connected component in a valid RGB tree.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Cut all R-G edges and if there is a path from B to the other B, the answer is NO. You can use dsu or something to check this.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is this something similar to building a auxiliary tree ?
      If so please share your solution

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Nothing to do with auxiliary tree. You can view editorial and my solution here.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    (off topic)

    The generator problem will be also interesting! Here's how I generated cases whose answer are Yes.
    Firstly, I colored vertices Red and Green so that the vertices of same color aren't adjacent.
    Then I picked non-Blue vertex at random and check if the coloring remains valid after it is changed to Blue.
    You can validiate coloring in $$$O(N)$$$ each time and $$$O(N^2)$$$ total, but can you do it in $$$O(N)$$$ total?

    Spoiler

    Cases with No is easy. After creating cases with Yes, just change non-Blue vertices Blue until the coloring become invalid.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you share the generator, if you already have one ? I created one but its been running for like 1hour still couldn't find the wrong testcases.

      My approach
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm not sure but your solution seems to fail for some small $$$N$$$ cases. Here's a code of generator for small $$$N$$$.

        code