CodeChef_admin's blog

Invitation to CodeChef Starters 118 (Rated till 5-Stars) — 24th January
By CodeChef_admin, history, 9 months ago, In English

We invite you to participate in CodeChef’s Starters118, this Wednesday, 24th January, 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.

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

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Can you make sure the editorials for the previous Starters 117 are complete? The code for Expected Diameter problem is missing.

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

Finally, here is a contest.

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

How to solve WATERBUCKETS

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

    Divide the array into blocks of size $$$O(\sqrt n)$$$. The size of the water bucket is fixed. For each $$$i$$$, compute the minimum number of buckets you need to escape the block and the amount of water left in the last bucket if you start at $$$i$$$. This you can do by Segtree walk in $$$O(log_2(\sqrt n))$$$. Now to process an update, just update the block. To process queries, you can jump from block to block using this structure fast. Total complexity $$$O(n \sqrt n * log_2(\sqrt n))$$$.

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

      I got the same approach during the contest but was thinking about whether it could give TLE or not. poor me :(

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

      Damn, that's awesome, thanks

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

      I think you can use 2-pointers for calculating the amount you can jump to the right within one bucket inside a block. When recalculating a whole block it is only $$$O(\text{size of block})$$$ work total, no log factors and no need for segment trees.

      This improves the time complexity also, because now you can change the block size and get $$$O(q \sqrt{ n \log(n) })$$$ complexity.

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

anyone has the idea how to solve "Is it uniquely decodable?"

I tried a dp solution , in this I got the idea that , all subsequences that ends with a will consist of all the subsequences of previous a only , similarly for all b it can consisit of previous b

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

Here is what i tried its wrong but what was the idea

→ Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it
    Test case
    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      okay thanks bro , can you tell me what is the correct approach ?

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

        I have solved using dp. Here $$$dp_{i, j, k}$$$ denotes the no of ways such that we have traversed till $$$i$$$ indices and $$$j$$$ ($$$0$$$ if we need not to put anything strictly here otherwise $$$1$$$ if we need to put a $$$b$$$ here) and $$$k$$$ ($$$0$$$ if the string doesn't end with a $$$ab$$$ and $$$1$$$ if it does). Transitions are pretty much intutive. submission

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

        Editorial

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

Can anyone please tell me why this solution is giving WA for this problem (Subcount).

I have used matrix exponentiation to solve it.

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

how to solve SUBCOUNT task?

→ Reply