radoslav11's blog

By radoslav11, history, 6 months ago, In English

We invite you to participate in CodeChef’s November Lunchtime, this Saturday, 27th November, rated for all.

Time: 7:30 PM — 10:30 PM IST

Joining me on the problem setting panel are:

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

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

»
6 months ago, # |
  Vote: I like it +25 Vote: I do not like it

No prizes and/or CodeChef laddus?

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

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

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

Can someone share their dp solution for 70 points of subarray jumps?

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

    I did Greedy. submission

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

      Please explain your solution.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Spoiler
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      You can actually make the implementation even simpler by noticing the minimum equation effectively reduces to $$$a_{1}$$$ + $$$\sum_{i = 2}^{n} min(a_1, a_2, \ldots, a_{i - 1}) - a_{n}$$$.

      Submission

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

      any specific proof why it always works?

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

    I don't think it's dp. $$$d\cdot a[i]-a[j]$$$ is like adding $$$a[i]$$$ when visiting $$$i$$$, and subtracting $$$a[j]$$$ when stopping at $$$j$$$. When you stop at some cell (that's not n), the contribution of starting and stopping cancels. So you can initialize the answer to $$$a[1]-a[n]$$$ and iterate over $$$i$$$. Each non-endpoint cell contributes $$$a[k]$$$ to the answer, for some $$$k<i$$$. We can greedily choose each cell's contribution as the smallest $$$a[k]$$$ passed so far.

»
6 months ago, # |
  Vote: I like it +15 Vote: I do not like it

How to get 100 on Permutation Pairs? I could figure out we can solve it in $$$O(n)$$$ time as $$$\sum_{i=k+1}^{n - 1} {n - k \choose n - i + 1} \cdot i! \cdot (n - i)!$$$, but I can't think of how to do this in $$$O(1)$$$ or precalculate this independent of $$$k$$$ (the numerator factorial can be can taken common and removed, but an $$$n - i + 1$$$ will still remain in the denominator).

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    Precalculate prefix sums of 1/i. The ones remaining are the sum of 1/i for some i in [l,r].

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

    You can expand the choose, cancel some factorials, and reduce it to a sum of telescoping sequences.

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

    This problem was more of a math test than a coding problem. I started from a different formula:

    $$$ \sum_{j = k+2}^{n} (n-j)! (j-2)! (j-k-1) \sum_{x = j-1}^{n} (n-x) {{x-1}\choose{j-2}} $$$

    The interpretation is that for every $$$j$$$, I let $$$a[i] = x$$$. Then, every other element at a position $$$<j$$$ has a value $$$<x$$$, so choose and permute that. Then the value after $$$j$$$ can also be permuted. This is the contribution to the sum of every pair $$$(i,j)$$$. Then use Hockey Stick Identity and a bunch of boring reductions to get to:

    $$$ \sum_{j = k+2}^{n} \frac{1}{j-1} - (k+1)\sum_{j = k+2}^{n} \frac{1}{j(j-1)} $$$
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      1/j(j-1) can be rewritten as 1/(j-1) - 1/j and that summation would reduce to 1/k+1 - 1/n.

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

    You can manipulate the expression to get O(1) solution. It turn out answer is simply factorial[n] * (sum_inv(n-1) — sum_inv(k) — (n — k — 1)/n). here sum_inv(i) = 1/1 + 1/2 + 1/3 ... 1/i. my soln

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

    i guessed the pattern lol!

    k = n-k-1

    Ans = (n-1)! *( 1/(n-1) + 2/(n-2) + 3/(n-3) +...+ k/(n-k) )

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

    Can you explain your formula for O(N) solution ?

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

      First of all, there is a typo in my initial comment, it should be $$$\sum_{i=k+1}^{n - 1} {n - k \choose n - i + 1} \cdot (i - 1)! \cdot (n - i)!$$$.

      Basically my intuition was to fix the second largest element $$$i$$$ and figure out the number of ways of achieving the required gap between $$$i$$$ and some $$$j \gt i$$$.

      So clearly, all $$$j \gt i$$$ must lie to the right of $$$i$$$ for the condition in the problem to be satisfied.

      Now we have have some ordered values $$$i, x_1, x_2, \ldots, x_{n - i}$$$ where $$$x$$$ is some permutation of $$$i + 1, i + 2, \ldots, n$$$. Since the larger values can be in any order, there are $$$(n - i)!$$$ ways of doing this for a given $$$i$$$.

      Now we can place the remaining $$$i - 1$$$ smaller values among these $$$n - i + 1$$$ existing values in any possible way such that there to be at least $$$k$$$ of them between $$$i$$$ and $$$x_1$$$.

      This can be transformed into a bars and stars problem where $$$y_1 + y_2 + \ldots + y_{n - i + 2} = i - 1$$$ with $$$y_2 \geq k$$$ and $$$y_l \geq 0$$$ for all $$$l \ne 2$$$.

      Using bars and stars, we can obtain the number of ways of doing this to be $$$n - k \choose n - i + 1$$$. However we have to remember our objects aren't actually identical here and can be internally permuted in $$$(i - 1)!$$$ ways.

      Noting that $$${n - k \choose n - i + 1} = 0$$$ for any $$$i \leq k$$$, the number of ways of having $$$i$$$ as the second largest value of the prefix of some permutation is $$$\sum_{i=k+1}^{n - 1} {n - k \choose n - i + 1} \cdot (i - 1)! \cdot (n - i)!$$$

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

        I got the same expression.
        Did you find any way to condense it ?

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

    Hey, could you give a brief explanation on how to solve this problem ? Is the editorial available ?

    And similarly for next one (min, max rotation) I was able to think only 2 cases. If the white & blace form a pattern i.e. (BWBWBW or BBWWBBWWBBWW or BWWWBWWW, etc... ), then the diffenence is not available for the length of the pattern i.e (if pattern is BWWBWW, pattern length 3 etc.. then from 1, we cant choose elements at 4, 7, etc... similarly at other positions). Else if there are 2 patterns eg (BBWWBBWWBWBWBBWW, ...), then just prinnt the max — min of the array. I could not find a case where it will go wrong. Could you give a case... Actually only for cases like these, I would like codechef to provide test cases, but it seems that they dont provide as per discussion forums..

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      Permutation Pair

      Suppose $$$g(i,j)(j>i+K)$$$ is the number of permutations in which pair $$$(i,j)$$$ is counted. Notice that answer is $$$\sum_{j=K+2}^{n}\sum_{i=1}^{j-K-1} g(i,j)$$$.

      Now $$$g(i,j)={n \choose j} \cdot (j-2)! \cdot (n - j)!$$$. Why? First select $$$j$$$ elements for subarray $$$[1,j]$$$. Now for subarray $$$[1,j]$$$ elements at positions $$$i$$$ and $$$j$$$ are fixed because they are second largest and largest element (of subarray $$$[1,j]$$$) respectively. You can permute $$$j-2$$$ remaining elements of subarray $$$[1,j]$$$ in $$$(j-2)!$$$ ways. Also you can permute $$$n-j$$$ elements of subarray $$$[j+1,n]$$$ in $$$(n-j)!$$$ ways.

      On simplifying, we get $$$g(i,j)=\frac{n !}{j \cdot (j-1)}$$$. As you can see $$$g(i,j)$$$ doesn't depend on $$$i$$$.

      At last we get $$$\sum_{j=K+2}^{n}\sum_{i=1}^{j-K-1} g(i,j)=n! \cdot \sum_{j=K+2}^{n} \frac{j-K-1}{j \cdot (j-1)}$$$.

      $$$\frac{1}{j \cdot (j-1)} = \frac{1}{(j-1)} - \frac{1}{j}$$$

      Now it's trivial to compute the expression in $$$O(1)$$$ if you precompute the $$$ \sum_{i=1}^{n} \frac{1}{i}$$$

»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Can anyone explain solution of problem subarray jumps for 100 points??

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

    Can check convex hull trick dp?

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

    So clearly we must start at $$$1$$$ and end at $$$n$$$, so the simplest possible process has cost:

    $$$(n \cdot a_1 - a_n)$$$

    Lets suppose we make a single jump at position $$$i$$$, the equation will then become:

    $$$(i \cdot a_1 - a_i) + ((n - i + 1) \cdot a_i - a_n)$$$

    Rewriting this, it becomes:

    $$$(i \cdot a_1) + ((n - i) \cdot a_i - a_n)$$$

    This equation is smaller if $$$a_i \lt a_1$$$, and we can repeat this process for some $$$j \gt i$$$. So clearly it is optimal to perform this for every $$$i$$$ that satisfies $$$a_i \lt a_{i - 1}$$$.

    While it isn't necessary to get AC, we can notice that this effectively means the answer is equivalent to $$$a_1 + \sum_{i = 2}^{n} min(a_1, a_2, \ldots, a_{i - 1}) - a_{n}$$$ which is even easier to implement.

    Submission

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

      Thanks alot for such a good explanation

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

      Could you please explain how

      (i⋅a1)+((n−i)⋅ai−an)

      leads to

      While it isn't necessary to get AC, we can notice that this effectively means the answer is equivalent to a1+∑ni=2min(a1,a2,…,ai−1)−an which is even easier to implement.

      I can only understand

      This equation is smaller if ai<a1, and we can repeat this process for some j>i. So clearly it is optimal to perform this for every i that satisfies ai<ai−1.

      this part.

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

      This equation is smaller if ai<a1, and we can repeat this process for some j>i. So clearly it is optimal to perform this for every i that satisfies ai<ai−1.

      I cannot understand what you are trying to say here can you please explain

»
6 months ago, # |
  Vote: I like it +39 Vote: I do not like it

Div1A statement is ?????????????????????????????????????????????????????

»
6 months ago, # |
  Vote: I like it +58 Vote: I do not like it

I'm the setter of the problem Ghost Chase (CHASE)! Here is the solution to the problem: https://drive.google.com/file/d/1HQfYZ9Bg4HpSPHim-XM2Ih8nyuBDR45z/view?usp=sharing

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

how is ans for i/p -> 3 0 is 5 not 3 in Permutation Pairs.??

[1]->[1,2,3] [2]->[1,3,2] [3]->[2,1,3] [4]->[2,3,1] [5]->[3,1,2] [6]->[3,2,1]

only 1, 3 & 4 should be selected in my opinion

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

    You count good pairs over all permutations(not permutations).

    Permutation [1, 2, 3] adds 2 to the answer: pairs (1, 2) (2, 3)

    Permutation [1, 3, 2] : (1, 3)

    Permutation [2, 1, 3] : (2, 3)

    Permutation [2, 3, 1] : (2, 3)

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

Nice problems, Thanks for the contest!

»
6 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Is test case $$$4$$$ of Min-Max Rotations some special edge case or general small cases? I have a solution that passes everything else but fails this case.

My idea was:

  • Consider the largest (cyclic) subarrays of equal elements.

  • If we place one of our two choice elements in one such subarray, it can only be blocked by a subarray of the same color of the exact same maximum length.

  • So consider all such subarrays of either color (can be pre-calculated by a single O(n) pass and sorting a tuple of $$$(length, colour, end position)$$$).

  • If all the subarrays are at equal distance, then any pair $$$(i, j)$$$ that is a multiple of this distance is impossible. Otherwise any pair is possible. Note that for this equal distance to exist, it must be a divisor of the length of the array (and this was the intended $$$O(n \sqrt n)$$$ subtask approach I suspect).

  • So in the equal distance case just find max / min for each position modulo this distance and find the best pair from different values under mod (use prefix / suffix min or max to do this in O(n)).

I ran several thousand rounds against the obvious $$$O(n ^ 2)$$$ brute but I can't find a counter-case to the idea. I suspect the counter case exists at $$$n \gt 20$$$ or larger and the probability of a random string with those exact properties being generated is miniscule.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it
    1
    12
    1719 4299 8716 943 3778 2499 463 6865 85 715 7852 3721
    WBBWBWWBWBBW
    

    The answer is 8631

  • »
    »
    6 months ago, # ^ |
    Rev. 5   Vote: I like it +9 Vote: I do not like it
    • That was not the intended n.root(n) solution for the subtask.
    • Test case — 4 is not a special one (random generator).

    Regarding intended solutions

    Let's call a value 'p' periodic if rotating array by p doesn't change the array. The least periodic value divides all other values. If we find this value, we can easily find the answer

    • $$$O(n\sqrt{n})$$$: Find the least periodic value by naive checking for every divisor. (It's not actually nrootn)

    • $$$O(nlogn)$$$: As n is also a periodic value, converge to the least periodic value from n by dividing with appropriate prime factor every time.

    • $$$O(n)$$$: Use Z-algo/KMP to check whether a value is periodic.

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

      What about after finding the period? I couldn't solve that.

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

        Let $$$T=S+S$$$, $$$S$$$ has period $$$1<=p<=n$$$ if and only if $$$T[0:n-1] == T[p:p+n-1]$$$.

        One can find kmp array and check if length of proper prefix (definiton in cp-algorithm article) of $$$T[0:p+n-1]$$$ is atleast $$$n$$$.

        Similarly using z function and check $$$p$$$ is period if and only if $$$Z[i]$$$ (definiton in cp-algorithm article) is at least $$$n$$$.

        Also for this particular case of binary string one can count no of pairs $$$i,j$$$ such that $$$j-i$$$ mod $$$n == p$$$ and $$$s[i]!=s[j]$$$. The binary string has period $$$p$$$ if and only if no such pairs exist. People have calculated this using FFT/NTT on the binary array of $$$T$$$.

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it +16 Vote: I do not like it

        Let's take some index $$$i$$$, if you shift $$$a_i$$$ to some White index then what all values can be in the Black-colored index?. For some $$$k$$$ ($$$ 1 \le k \le n-1$$$) which is not divisible by the least periodic value, if there is at least one $$$j$$$ such that $$$col_j = 'W'$$$ and $$$ col_{(j+k)\%n} = 'B'$$$. Then, we can say that for every i ($$$ 0 \le i \le n-1$$$), $$$a_i$$$ can be in a White-colored index and $$$a_{(i+k)\%n}$$$ can be in a Black-colored index. Now, the result will be the maximum of these two values:

        • $$$max(a_{(k+t)\%n} \forall \ k \% least periodic value \neq 0) - a_{t}$$$. Where $$$t$$$ is the index of minimum value in the array $$$a$$$.
        • $$$a_{t} - min(a_{(t-k+n)\%n} \forall \ k \% least periodic value \neq 0)$$$. Where $$$t$$$ is the index of maximum value in the array $$$a$$$.
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          how did you figure out, atleast one of max,min elements has to be involved. it can also be the 2nd max and 2nd min values' difference.no?

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

            Then one of these pairs which gives better result than what you said is possible

            • 2nd max and min
            • 2nd min and max
            • max and min
»
6 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Codechef contests quality has improved drastically in the past few months! Kudos to the team.

»
6 months ago, # |
Rev. 2   Vote: I like it +64 Vote: I do not like it

Problem C (min-max rotations) was a masterpiece.

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

    This probably might be the first problem in at least one year that I found really enjoyable!

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

Hints on D? Didn't make much progress, just noticed that the edge you take has to either be an existing bridge or an edge that you add. Seems hard to find a subset of connected component sizes that add up to near $$$n/2$$$.

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

    My solution ( I upsolved ) : Find all the bridges in a connected components , and no. of elements visitable by that node .Notice even though graph is not a tree , but for a bridge the elements can be treated in a subtree of v , where (u,v) is a bridge . We can choose the v which has greater in value to find no. of nodes in its subtree. So the connected component can be divided into x,m-x , where x is size of component visitable by v and m-x is size of component visitable by u . Now I used bitset (U can use dp as well) , notice that a component can be divided into many ways , so make 3 bitsets , one which will store which sizes are possible , 2nd one will.store which sizes are possible not considering this component , and last one will store which sizes are possible taking x and m-x in account . Transitions are in the code ( I think it's simple enough to understand ) . BTW Editorial is out . My solution

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

      Yeah I ended up reading the editorial, the $$$nsqrtn$$$ optimization is really cool.

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

    You can also store the DP for each connected component as a polynomial and use FFT to get an $$$O(n * log(n) ^ 2)$$$ solution.

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

      Can you please elaborate more?

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

        Sure, as a background the idea here is similar to Lucky Tickets.

        For each connected component imagine a boolean array split[x] = 1 if is it possible to split this component into 2 components so that one of them has x nodes in it, else 0. The size of this array is equal to the size of the connected component, and you can calculate it during the dfs to find all the bridges. Also, you have another array keep for each component with a 1 only in the positions of keep[size(component)] = 1 and keep[0] = 1, all other elements are 0. This second array says that without removing a bridge, you only have the choice to take size(component) or not in the knapsack.

        Now, you want to answer the question, "What are all the sums of some subset of sizes of components I can get if I am allowed to remove at most 1 bridge from the graph?". Thinking in terms of FFT and polynomials, this looks like convolving some subset of keep arrays, and at most 1 split array. Since the sum sizes of all arrays is $$$O(n)$$$, you can multiply them all together in $$$O(n*log(n)^2)$$$.

        I hope that helps, here's my submission: Code

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

Div 2 second problem

can someone tell me how to approach this problem or some hints?

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

    Pick a random sorted array $$$A$$$ of distinct nos. Generate B using it. Then look at properties of B. Then try to see how can one get back $$$A$$$ the array you started with using this $$$B$$$.

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

How to solve Div1 second problem link
Edit : got the solution .

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

Since editorial for Strange Minimization is still not out, can someone help me on how to solve this ?

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

    The video should help you out.

    You have to minimize the absolute difference between GCD and LCM. This implies you should try to make GCD and LCM as equal to each other as possible.

    From my understanding, it generally helps to think in terms of prime factorization when dealing with GCD/LCM. You can prime factorize N. Now you want to choose X which would make GCD(N,X) as close to LCM(N,X) as possible. What if X has it's prime factorization exactly same as N, except the lowest prime factor of N?

»
6 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Won't there be any prizes this time? Or is it preassumed that the prize structure will remain the same?