ScarletS's blog

By ScarletS, history, 4 years ago, In English

A — Very Very Primitive Game

Solution

B — Magic 3

Solution

C — Bowls and Dishes

Solution

D — Staircase Sequences

Solution

E — Magical Ornament

Solution

F — Shift and Inversions

Solution
  • Vote: I like it
  • +116
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In F, the change should be n — 1 — 2*a[i].

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Thanks! I missed that when I was copying from my code to this editorial :S

»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

problem F was very interesting

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

For problem D, I iterated over the length of the series from 1 to 2000000. Then I binary searched the start element for the cur length and if we found the sum exactly equal to n, then add 2 to the answer.

My submission

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you explain how you figured the range will be till 2000000?

    I tried till 1000000 and didn't work.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The longest length series you can make in worst case out of natural numbers should start from 1.

      Lets say that length is $$$l$$$. Then $$$\sum_{i=1}^n l = \frac{l(l+1)}{2} = n$$$

      Here n is the sum we want.

      So $$$l \leq \sqrt{2 * n}$$$

      Hence $$$l$$$ will be less than 2000000

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give a solution for C without using bitmasking?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You can use recursion to find all the ways to pick either $$$C_i$$$ or $$$D_i$$$, but it ends up doing the exact same thing as bitmasks, only slower and messier.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ya I understood.Thank you so much.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it
      Code
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Put the code in spoiler like below

        Code
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me how to find these time complexities...I can find easy ones like O(n) and O(n^2) but not like -O(K(N+M)+2K∗K2)..how to learn that...I'm struggling with this for a week.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, sorry for the late response. I don't think you need to learn/find these non-standard complexities, rather, you should learn to recognise and break down problem statements and work on approaching unfamiliar problems. In that problem the $$$K(N+M)$$$ and the $$$2^K*N^2$$$ are essentially separate sub-problems, first to calculate distance to all nodes with BFS ($$$O(N+M)$$$), $$$K$$$ times, for each gem. From there, we can reduce it to a classic $$$O(2^K*K^2)$$$ bitmasking problem. I hope this helped! :)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hello, I'm a beginner and I want to ask you one more thing "if the jth bit is "on" (i.e. i AND 2j=2j)" what is the meaning of this? I mean if the jth bit is on then how are we deciding that we will give the ball to C[j] or d[j](what it means if the jth bit is on in the context of this problem)...I hope you know what I mean.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        It's just a technique to iterate over all combinations of $$$0$$$s and $$$1$$$s. While iterating from $$$0$$$ to $$$2^{K-1}$$$, all masks of length $$$K$$$ can be achieved. You may have seen the recursive version before, think of this as another way to do that only faster and less liable to mistakes.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ScarletS (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, thanks for the great editorial. I just wanted to ask that why there is a second If in solution of staircase sequence??

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    We can find all the divisors of $$$N$$$ in $$$O(\sqrt{N})$$$ by only checking up to $$$\sqrt{N}$$$, as every every divisor below the square root has a conjugate divisor above it. The exception to this is $$$\sqrt{N}$$$ itself if $$$N$$$ is a square number, since its conjugate divisor is also $$$\sqrt{N}$$$. We can avoid double counting by ensuring that the second addition to the answer is only done if $$$i^2 \neq N$$$.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the editorial! BTW can you explain why the sequences in F will change by moving the first element to the end?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    What do you mean?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "Now, notice that each of the resulting sequences essentially remove the first element of the previous sequence and insert it at the end of it." How is that?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

User Editorial by kostia244

kinda sus

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E,if the problem description change to “find the minimum number of distinct stones needed to form such a sequence.”,how to solve it? thx.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, my output was 2 times the number of odd divisors of N. Submission

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ScarletS (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F was an owsam one to me