By radoslav11, history, 6 months ago,

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

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!

• +54

 » 6 months ago, # |   +25 No prizes and/or CodeChef laddus?
•  » » 6 months ago, # ^ |   -25 you are expecting prize or laddus ??? I was expecting lunch
•  » » » 6 months ago, # ^ |   +50 i am expecting bunch of cheaters
 » 6 months ago, # | ← Rev. 2 →   0 Auto comment: topic has been updated by radoslav11 (previous revision, new revision, compare).
 » 6 months ago, # |   0 Can someone share their dp solution for 70 points of subarray jumps?
•  » » 6 months ago, # ^ |   +1 I did Greedy. submission
•  » » » 6 months ago, # ^ |   0 Please explain your solution.
•  » » » » 6 months ago, # ^ |   0 Spoileryou should jump to the nearest index whose value is less than or equal to your current value.
•  » » » 6 months ago, # ^ |   +1 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, # ^ |   0 any specific proof why it always works?
•  » » 6 months ago, # ^ |   +8 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 •  » » » 6 months ago, # ^ | 0 well dp worked for me in smaller constraintshttps://www.codechef.com/viewsolution/54424577 •  » » » » 6 months ago, # ^ | 0 The constraints of the subtasks deceive people that the main idea is DP, But after the contest I was surprised that the main idea was greedy. •  » » » » » 6 months ago, # ^ | 0 Bro ur graph suprised me.. How u improving so fast ? •  » » » » » 6 months ago, # ^ | 0 You can use Convex hull dp trick (like I did) , an absolute overkill. •  » » » 6 months ago, # ^ | +2 This was helpful Thanks!  » 6 months ago, # | +15 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 → +10 Precalculate prefix sums of 1/i. The ones remaining are the sum of 1/i for some i in [l,r]. •  » » 6 months ago, # ^ | +8 You can expand the choose, cancel some factorials, and reduce it to a sum of telescoping sequences. •  » » 6 months ago, # ^ | +16 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$
•  » » » 6 months ago, # ^ |   +29 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, # ^ |   +1 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, # ^ |   +4 i guessed the pattern lol!k = n-k-1Ans = (n-1)! *( 1/(n-1) + 2/(n-2) + 3/(n-3) +...+ k/(n-k) )
•  » » 6 months ago, # ^ |   0 Can you explain your formula for O(N) solution ?
•  » » » 6 months ago, # ^ |   +6 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, # ^ |   +3 I got the same expression.Did you find any way to condense it ?
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 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 →   +11 Permutation PairSuppose $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, # ^ |   0 That was a brilliant explanation. Thank you!
•  » » » » 6 months ago, # ^ |   0 Cool. Thanks man...
 » 6 months ago, # |   +7 Can anyone explain solution of problem subarray jumps for 100 points??
•  » » 6 months ago, # ^ |   +19 Can check convex hull trick dp?
•  » » 6 months ago, # ^ |   +13 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, # ^ |   +8 Thanks alot for such a good explanation
•  » » » 6 months ago, # ^ |   0 Could you please explain how (i⋅a1)+((n−i)⋅ai−an)leads toWhile 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 aii. So clearly it is optimal to perform this for every i that satisfies ai
•  » » » 6 months ago, # ^ |   0 This equation is smaller if aii. So clearly it is optimal to perform this for every i that satisfies ai
 » 6 months ago, # |   +39 Div1A statement is ?????????????????????????????????????????????????????
 » 6 months ago, # |   +58 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, # |   0 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 →   +3 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, # |   +6 Nice problems, Thanks for the contest!
 » 6 months ago, # | ← Rev. 2 →   +11 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, # ^ |   +22 1 12 1719 4299 8716 943 3778 2499 463 6865 85 715 7852 3721 WBBWBWWBWBBW The answer is 8631
•  » » 6 months ago, # ^ | ← Rev. 5 →   +9 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, # ^ |   +9 What about after finding the period? I couldn't solve that.
•  » » » » 6 months ago, # ^ | ← Rev. 3 →   0 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 →   +16 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, # ^ |   0 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 →   +3 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, # |   +37 Codechef contests quality has improved drastically in the past few months! Kudos to the team.
 » 6 months ago, # | ← Rev. 2 →   +64 Problem C (min-max rotations) was a masterpiece.
•  » » 6 months ago, # ^ |   +14 This probably might be the first problem in at least one year that I found really enjoyable!
 » 6 months ago, # |   +3 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, # ^ |   +5 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, # ^ |   +16 Yeah I ended up reading the editorial, the $nsqrtn$ optimization is really cool.
•  » » 6 months ago, # ^ |   +3 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, # ^ |   0 Can you please elaborate more?
•  » » » » 6 months ago, # ^ |   +8 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, # |   0 Div 2 second problemcan someone tell me how to approach this problem or some hints?
•  » » 6 months ago, # ^ |   0 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 →   0 How to solve Div1 second problem link Edit : got the solution .
 » 6 months ago, # |   0 Since editorial for Strange Minimization is still not out, can someone help me on how to solve this ?
•  » » 6 months ago, # ^ |   0 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, # |   +14 Won't there be any prizes this time? Or is it preassumed that the prize structure will remain the same?