tejas10p's blog

Invitation to CodeChef Starters 75 (Rated till 6-stars) — 26th January
By tejas10p, history, 21 month(s) ago, In English

We invite you to participate in CodeChef’s Starters 75, this Thursday, 26th January, rated till 6-stars Coders (ie. for users with rating < 2500).

Time: 8 PM — 11:00 PM IST

Joining us on the problem setting panel are: - Setters: Utkarsh Utkarsh.25dec Gupta, Tejas tejas10p Pandey, Divyansh dash2199 Gupta, Indresh indreshsingh Rajesh Singh, wuhudsm wuhudsm, Leung arvindf232 Arvin

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

Comments Comments (11)
| Write comment?
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

how to solve Chefs Favourite Function?

f(x)

g(x)

i try to solve by this observation but not able to solve :/

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Editorial

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    As the OEIS shows,
    $$$f(x)$$$ is the no. of $$$0's$$$ in binary representation of $$$x$$$.
    We can also observe that $$$g(x)$$$ is decreasing after powers of $$$2$$$.
    So, the best numbers for us are powers of $$$2$$$.
    Now, there arise 2 cases:

    • There is a power of $$$2$$$ between $$$L$$$ and $$$R$$$, in that case the highest of such numbers will be the most desired, and $$$f(x) + g(x)$$$ will be calculated for that.
    • There is no power of $$$2$$$ between $$$L$$$ and $$$R$$$, then $$$g(x)$$$ will be maximum for $$$x = L$$$
      But, the maximum for $$$f(x)$$$ can't be determined easily.
      One noticeable point is that the range is $$${10^9}$$$, i.e. $$$31$$$ bits.
      So, we can check the max value of $$$f(i) + g(i)$$$ for $$$i$$$ from $$$L$$$ to $$$min(L + 31, R)$$$. (This is intuition based, and I couldn't find a concrete proof behind this.)

    My Submission
    (Note that it got accepted even for checking till $$$min(L + 13, R)$$$ [perhaps due to weak test cases].)

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      in (number+32) it can always be assured that the loss in g(x) is atleast 32 when number>=32 .for the number less than 32 f(x) can never contribute 30 in the answer .hence [number+31,-1] is the fine i guess..

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Ohh, I didn't know about Oeis but I just printed the pattern for i=1 to 20 using recursion by which I concluded that the local maximas occour at perfect powers of 2. So just find the greatest power of 2 in the range [l,r] and use recursion to get the answer as it will be logarithmic in time. What's left is the case where no perfect power of 2 lies in the range [l,r] here I printed all the values till 5000 and noticed that sometimes a small peak (deviation) is observed from the decreasing pattern from the perfect power of 2's value. For this, I used the fact that it lied just close enough to l and we could brute force all the values in the range [l,min(l+500,r)]. I have no actual proof that why choosing 500 worked (did'nt have that much time left for trying to prove my solution) but the decrease from f(l)+g(l) to f(min(r,l+500))+g(min(r,l+500)) was significant enough for it to get hold of any deviation and pass.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

Here goes how I solved all problems except XOR_X

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -7 Vote: I do not like it

when do you intend to bring the editorial to the last 2 problems.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that i already saw problem minimum replacement on codeforces but i can't remember

→ Reply