ScarletS's blog

By ScarletS, history, 3 months 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

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    3 months 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

»
3 months ago, # |
  Vote: I like it -9 Vote: I do not like it

problem F was very interesting

»
3 months 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

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

    What are you doing your sum() function please explain that i can't understand that...

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Arithmetic series formula,

      $$$S_n = \frac {n \cdot (a + a_n)} 2$$$

      Where $$$a= a_1, d = a_{i + 1} - a_i, a_i = a + (i - 1) \cdot d, i \in Z^+$$$

      We can rewrite, $$$S_n = \frac {n \cdot (a + a + (n - 1) \cdot d)} 2 = \frac {n \cdot (2 \cdot a + (n - 1))} 2$$$ since, $$$d = 1$$$ for the desired sequence.

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

    Nice approach! The idea of using Binary Search never hit me.

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give a solution for C without using bitmasking?

  • »
    »
    3 months 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.

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

      Ya I understood.Thank you so much.

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it
      Code
»
3 months 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.

  • »
    »
    3 months 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! :)

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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.

»
3 months 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).

»
3 months 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??

  • »
    »
    3 months 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$$$.

»
3 months 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?

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

    What do you mean?

    • »
      »
      »
      3 months 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?

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

        for each $$$k$$$ in $$$[0, n - 1]$$$, $$$b_i = a_{i + k \mod n}$$$

        plug in the values figure out yourself

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

          https://ideone.com/KJFNgG I printed out all the numbers but I sill don't get it.

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

            It should be $$$num_{i+k}$$$ not $$$num_i+k$$$.

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

            $$$n = 4$$$

            Say we have a sequence $$$a_0, a_1, a_2, a_3$$$
            $$$b_i = a_{i + k \mod n}$$$

            for $$$k = 0,$$$
            $$$b_0 = a_{0 + 0 \mod 4}$$$
            $$$b_0 = a_{0 \mod 4} = a_0,$$$
            $$$b_1 = a_{1 + 0 \mod 4} = a_1,$$$
            $$$b_2 = a_{2 + 0 \mod 4} = a_2,$$$
            $$$b_3 = a_{3 + 0 \mod 4} = a_3$$$

            for $$$k = 1,$$$
            $$$b_0 = a_{0 + 1 \mod 4}$$$
            $$$b_0 = a_{1 \mod 4} = a_1,$$$
            $$$b_1 = a_{1 + 1 \mod 4} = a_2,$$$
            $$$b_2 = a_{2 + 1 \mod 4} = a_3,$$$
            $$$b_3 = a_{3 + 1 \mod 4} = a_0$$$

            for $$$k = 2,$$$
            $$$b_0 = a_{0 + 2 \mod 4}$$$
            $$$b_0 = a_{2 \mod 4} = a_2,$$$
            $$$b_1 = a_{1 + 2 \mod 4} = a_3,$$$
            $$$b_2 = a_{2 + 2 \mod 4} = a_0,$$$
            $$$b_3 = a_{3 + 2 \mod 4} = a_1$$$

            for $$$k = 3,$$$
            $$$b_0 = a_{0 + 3 \mod 4}$$$
            $$$b_0 = a_{3 \mod 4} = a_3,$$$
            $$$b_1 = a_{1 + 3 \mod 4} = a_0,$$$
            $$$b_2 = a_{2 + 3 \mod 4} = a_1,$$$
            $$$b_3 = a_{3 + 3 \mod 4} = a_2$$$

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

User Editorial by kostia244

kinda sus

»
3 months 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.

»
2 months 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

»
2 months 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).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F was an owsam one to me

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

i dont understand problem C they said there are conditions and that condition i could be satisfied with Ai and Bi have one or more balls on them. However when in the sample input there is

1 2
1 3
2 4
3 4

but the sample output is

2

all of Ai and Bi have more than 1 balls inside, why is the sample output 2, is my understanding of the question completely wrong?

and the people will put balls on Ci and Di. Where do the balls come from? Issit from A or B or somewhere else? could someone explain it to me? thanks in advance