Блог пользователя CodeChef_admin

Автор CodeChef_admin, история, 9 месяцев назад, По-английски

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!

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
9 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
9 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Finally, here is a contest.

»
9 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve WATERBUCKETS

  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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))$$$.

    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Damn, that's awesome, thanks

    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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.

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
    Test case
    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 месяцев назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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

      • »
        »
        »
        »
        9 месяцев назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
»
9 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

I have used matrix exponentiation to solve it.

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve SUBCOUNT task?