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:
Setters: Dolesh croxo Verma, Surya evilbuggy Prakash, Pratik i.am.pratik Kumar, Manuj Nanthan, Mradul bhatnagar.mradul Bhatnagar, Yaswanth YPK Phani Kommineni, Stuart cstuart Lim, Saarang saarang Srinivasan
Testers: Aryan aryanc403
Statement Verifier: Trung Đặng Kuroni Đoàn Đức
Admin: Radoslav radoslav11 Dimitrov
Head Admin: Alex Um_nik Danilyuk
Editorialists: Surya evilbuggy Prakash, Mradul bhatnagar.mradul Bhatnagar, Nandini costheta_z Kapoor, Aryan Aggu_01000101 Agarwala
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!
No prizes and/or CodeChef laddus?
you are expecting prize or laddus ??? I was expecting lunch
i am expecting bunch of cheaters
Auto comment: topic has been updated by radoslav11 (previous revision, new revision, compare).
Can someone share their dp solution for 70 points of subarray jumps?
I did Greedy. submission
Please explain your solution.
you should jump to the nearest index whose value is less than or equal to your current value.
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
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.
well dp worked for me in smaller constraints
https://www.codechef.com/viewsolution/54424577
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.
Bro ur graph suprised me.. How u improving so fast ?
You can use Convex hull dp trick (like I did) , an absolute overkill.
This was helpful Thanks!
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).
Precalculate prefix sums of
1/i. The ones remaining are the sum of1/ifor someiin[l,r].You can expand the choose, cancel some factorials, and reduce it to a sum of telescoping sequences.
This problem was more of a math test than a coding problem. I started from a different formula:
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:
1/j(j-1)can be rewritten as1/(j-1) - 1/jand that summation would reduce to1/k+1 - 1/n.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
i guessed the pattern lol!
k = n-k-1
Ans = (n-1)! *( 1/(n-1) + 2/(n-2) + 3/(n-3) +...+ k/(n-k) )
Can you explain your formula for O(N) solution ?
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)!$$$
I got the same expression.
Did you find any way to condense 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..
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}$$$
That was a brilliant explanation. Thank you!
Cool. Thanks man...
Can anyone explain solution of problem subarray jumps for 100 points??
Can check convex hull trick dp?
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
Thanks alot for such a good explanation
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.
Div1A statement is ?????????????????????????????????????????????????????
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
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
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)
Nice problems, Thanks for the contest!
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.
The answer is 8631
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.
What about after finding the period? I couldn't solve that.
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$$$.
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:
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?
Then one of these pairs which gives better result than what you said is possible
Codechef contests quality has improved drastically in the past few months! Kudos to the team.
Problem C (min-max rotations) was a masterpiece.
This probably might be the first problem in at least one year that I found really enjoyable!
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$$$.
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
Yeah I ended up reading the editorial, the $$$nsqrtn$$$ optimization is really cool.
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.
Can you please elaborate more?
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 arraykeepfor each component with a 1 only in the positions ofkeep[size(component)] = 1andkeep[0] = 1, all other elements are 0. This second array says that without removing a bridge, you only have the choice to takesize(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
keeparrays, and at most 1splitarray. 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
Div 2 second problem
can someone tell me how to approach this problem or some hints?
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$$$.
How to solve Div1 second problem link
Edit : got the solution .
Since editorial for Strange Minimization is still not out, can someone help me on how to solve this ?
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
Xwhich would makeGCD(N,X)as close toLCM(N,X)as possible. What ifXhas it's prime factorization exactly same as N, except the lowest prime factor of N?Won't there be any prizes this time? Or is it preassumed that the prize structure will remain the same?