satyam343's blog

Invitation to CodeChef Starters 113 (Rated for All) — 20th December
By satyam343, 11 months ago, In English

We invite you to participate in CodeChef’s Starters113, this Wednesday, 20th December, rated for All.

Time: 8:00 PM — 10:30 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.

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
  • +84
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it +47 Vote: I do not like it

Omg satyam343 round,all problems of all divs!

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

As someone who has seen the problems, i regret missing the chance to participate

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

rejected a party invitation to give this contest , hopefully it goes well

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

Friendly reminder: The contest starts in less than 60 minutes. I hope you like the problems.

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

Here, we go again. Post contest solution discussion stream

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

unable to understand this counting in fun problem statement. It's too complicated.

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

    You can use the comment section on Codechef to ask questions. Also 8 participants in Div 1 have ACed the problem. So, probably, the statement isn't that bad.

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

Loved the problemset, SCORESUM7 is such a cute problem.

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

Scores and ranks (for me at least) are not up-to-date until now ...

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

    Same here, even after solving the problem i didnt got the points and its showing tick mark

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

Counting is Fun was amazing!

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

    Glad that you liked it. It is one of my best problems.

    → Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

I hope you liked the problems! I would love to hear your feedback.

By the way, do check out the intended solution for COUNTIFUN7. It is one of my favourite problems that I have authored.

Once you establish a nice bijection, the solution is just 4-5 lines of code.

Code
→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    Yes, a math problem is the best CP problems you've authored :clown:

    → Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 6   Vote: I like it +21 Vote: I do not like it

    Damn, nice solution. I solved it in a quite complicated way. This was my solution:

    Let us fix the value of prefix minimum, call it $$$x$$$. Thus $$$1$$$, $$$2$$$,..., $$$x-1$$$ all occur after $$$x$$$. If the nearest smaller element occuring after $$$x$$$ is $$$y$$$ positions ahead, then contribution to answer is $$${y+k-1 \choose k}$$$. So if we denote by $$$ans(x,l)$$$ as the sum of $$${(t_2-1)+(k-1) \choose k}$$$ over all $$$1=t_1<t_2<t_3<...<t_x<t_{x+1}=l+1$$$ ($$$t_i$$$ are the relative positions of elements $$$<x$$$ wrt $$$x$$$) , Then contribution to the final answer for $$$x<V$$$ is $$$\sum_{l=1}^{n-1} ans(x,l)(x-1)!(n-1-x)!$$$ and for $$$x=V$$$ is $$$ans(V,n)(V-1)!(n-V)!$$$.

    To determine $$$ans(x,l)$$$, we observe that $$$ans(x,l)=ans(x,l-1)+ans(x-1,l-1)$$$ for $$$x>1$$$ and $$$ans(1,l)={l+k-1 \choose k}$$$. So if we represent a generating function $$$G_x = \sum ans(x,l)z^l$$$, then $$$G_x = z(G_x+G_{x-1})\Rightarrow G_x=\frac{zG_{x-1}}{1-z}$$$ and $$$G_1$$$ is $$$z(1-z)^{-k-1}$$$. Thus $$$G_x=z^{x}(1-z)^{-k-x}\Rightarrow ans(x,l)={l+k-1 \choose l-x}={l+k-1\choose k+x-1}$$$

    Plugging this in summation gives a telescopic sum, thus contribution for each $$$x$$$ can be found in $$$O(1)$$$.

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

What is mistake in this https://www.codechef.com/viewsolution/1036038527 can any one give any counter test

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

Can anybody give me a counter testcase for MAKE ALL EQUAL problem, here is the code https://www.codechef.com/viewsolution/1036034543

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the solution to Make All Equal?

Consider the case $$$N = 8, M = 2$$$ and $$$A = [3, 4, 5, 8, 8, 8, 8, 8]$$$. How does the official solution make the array all equal in 6 steps?

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

    Do operations on index (1,2) 3 times, (1,3) 2 times and (2,3) once.

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

i think your rating is bugged, it shows -279 in last edu round

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

I loved this problemset and liked MAKEALLEQUAL and SCORESUM7 problems

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

Maximise the Min. problem can be solved without dp too , using set.

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

I was wondering what would be the solution to the MAKE ALL EQUAL problem , if we allowed exactly m operations?

→ Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Find the smallest $$$x$$$ which is greater than or equal to maximum element of initial $$$a$$$ and $$$(x \cdot n - \sum_{i=1}^{n}a_i) \mod m=0$$$. Finding $$$x$$$ is not that hard.

    Hint

    It might be the case that such $$$x$$$ doesn't exist, in which case it is impossible to make all the elements same.

    Now it might be the case that $$$\frac{(x \cdot n - \sum_{i=1}^{n}a_i)}{m} > x - a_{min}$$$. So you need to do some algebraic manipulations to find the optimal $$$x$$$.

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

Alternate method to Minimise max , using prefix sums and sets.

AC Code
→ Reply