Utkarsh.25dec's blog

Invitation to CodeChef Starters 79 (Rated till 5-stars) — 01st March
By Utkarsh.25dec, 15 months ago, In English

We invite you to participate in CodeChef’s Starters 79, this Wednesday, 01st March, rated till 5-stars Coders (ie. for users with rating < 2200).

Time: 8 PM — 11: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 for all users for 1 day as soon as the contest ends, after which they 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
  • +21
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
15 months ago, # |
  Vote: I like it +31 Vote: I do not like it

As a setter, good luck everyone!

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

There are so many cheaters submitting in today's contest. I don't even want to give the contest anymore. CodeChef should do something about it.

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

For, K beautiful subarrays my approach was to make k different arrays with elements which are k distance apart and then make the element of these arrays equal to max element of each array.

and now my intuition was kind of coin change problem but constraints were high so i thought that maybe the size of the k arrays are kind of similar means the count of different (distinct) sizes of these array are very less. so this problem reduces to some kind of combinatorics problem. but i can't think any further.

was my approach wrong or was it correct? if it is correct how to count the answer?

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

    Yes. Let $$$m'$$$ to be what we left with after making them equal initially. If we increase some $$$i$$$ then we should increase all $$$j \equiv i \mod k$$$. Let $$$c_i = $$$ |{ $$$j | j \equiv i \mod k$$$ }| for $$$i \in 0..k - 1$$$. Then we need to calculate number of arrays $$$x$$$ such that $$$\sum_{i = 0}^{k - 1}c_i x_i \leq m'$$$. But let's remember that $$$c_i$$$ is not a random array. It has at most two unique values $$$\frac{n}{k}$$$ and $$$\frac{n}{k} + 1$$$. Let's iterate over the sum that we want to get with $$$c_i = \frac{n}{k}$$$. Now that $$$c_i$$$'s are equal we can calculate it with stars and bars. For all what remains we can fill with $$$c_i = \frac{n}{k} + 1$$$. You can also calculate it with stars and bars

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

      Thanks but i am a bit weak in combinatorics, i tried implementing the star and bars but it is not giving me correct output. i tried reading the editorial but it didn't help much.

      Spoiler

      can you tell the mistake please or maybe explain stars and bars.

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

        You are almost good. The thing that you missed and probably that I worded poorly in my initial explanation is that when you fill what’s left with $$$\frac{n}{k} + 1 $$$ you don’t want it to be maximum. You just want it to be less or equal than $$$rem_{op}$$$. How to solve that? The trick is to add another variable to the equation. $$$x_1 + x_2 + \ldots + x_k \leq n \iff x_1 + x_2 + \ldots + x_k + y = n$$$. TLDR just increase nk1_bars by one.

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

wuhudsm orz

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

https://www.codechef.com/viewsolution/91258913

Why is it giving RTE?

→ Reply