We invite you to participate in CodeChef’s January Cookoff, today — 23rd January from 8:00 PM — 10:30 PM IST.
The contest will be 2.5 hours long. There will be 7 problems in Div 1/2 and 8 problems in Div 3. It will be rated for all three Divisions.
Joining us on the problem setting panel are:
Contest Admins: Ashish Ashishgup Gupta
Head Admin: Alex Um_nik Danilyuk
Tester: Takuki tabr Kurokawa
Setters: Mohammed mohammedehab2002 Ehab, Jeevan JeevanJyot Jyot, Utkarsh Utkarsh.25dec Gupta, Daniel dannyboy20031204 Chiang, Rashad Mamedov Mammadov, Nayeemul Islam DrSwad Swad, SH Raiden Rony,
Statement Verifier: Trung Kuroni Dang, Jeevan JeevanJyot Jyot
Problem Submission: If you have original problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Prizes:
- The top 10 Global Division 1 users will get $100 each.
- The top 100 Indian Division 1 will get Amazon Vouchers worth Rs. 1500 each.
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.
Good luck and have fun!
Servers down again?
Submission page not loading :(
Please try hard refreshing. (Ctrl + Shift + R)
This is so unfair, you should have made an announcement
Try switch to non ide mode
Submission page not working for me!
How come this is not working for only me and working for others?
It seems I am the only one not able to see ranklist:(
Codechef is not working for me
How to solve
ERASE
? I doubt it is DSU, but I wasn't able to implement it correctly :')And loved the problems
MERGEDLIS
andPRIMEGRAPH
.SEGDIV
was rather a puzzle problem, but it was also good, except the position.Direction of thinking is already right for you I guess. Maybe you just want to keep connected components and want to check if there is one component or more than 1 at the end. However, I didn't find how to achieve it using DSU. But, here's a way I found..
let's iterate on permutation array from end and somehow maintain components . Now how can cur element help us. If there are two connected components to the right side, and both have at least one element larger than cur, then those two components can be connected. If we repeat this process, all the connected components which have at least 1 element greater than cur, can now combine.
How do we maintain these components and combine operation ?
STACK !! Since we only need the largest element of a connected component, we will keep in stack the largest element of connected component.
How will we combine ?
Delete all elements from stack which are larger than us, except THE LARGEST!
Code
Yeah the idea is finding number of components. To avoid actually creating the graph, you can show that if the graph has $$$k$$$ components, each component must be a subarray. So, letting [i] denote the ith component, the array is like [1] [2] ... [k], where [1]>[2]>...>[k]. (By [1]>[2] I mean all elements in component 1 are greater than all elements in component 2.) Consider the first component, say it ends at index i, then $$$min_{1...i} > max_{i+1...n}$$$. This condition is necessary and sufficient, so you can just check it every $$$i$$$.
You mean to say $$$<$$$ instead of $$$>$$$, right? Because, then only the components can be merged.
Thanks, it was a nice problem too!
You can go through each number and maintain some current minimum mn (initially it is a[0]) and a vector consisting of decreasing numbers to delete.
Suppose that you are at a[i] now:
if a[i] < mn -> add mn to the vector of erasable elements and set mn := a[i];
otherwise, remove the vector elements (x) from the back while x < a[i], and after that, remove a[i] using mn;
Finally, the answer is YES if and only if the vector is empty.
The DSU approach is very interesting. It didn't even remotely come to my mind during this whole time. There hasn't been any official editorial published for this problem yet.
The answer is
YES
if and only if there is no suffix, other than the whole array, of length $$$L$$$ ($$$1 \le L < N$$$) that consists of the smallest $$$L$$$ elements.Proof of the only-if part: Let the suffix in consideration be $$$A[i \dots N]$$$. Then since all the elements in the prefix $$$A[1 \dots (i - 1)]$$$ are greater than all the elements in the suffix, we won't be able to do any operations in-between this prefix and the suffix. Thus at-least two elements must remain at the end of all the operations (one from the prefix and one from the suffix), a contradiction.
Proof of the if part: We can prove the claim using induction. The case when $$$N = 1$$$ and $$$N = 2$$$ are trivial. So let's assume that $$$N \ge 3$$$. We'll show that we can remove an element from the array with a valid operation, such that the property that no suffix of length $$$L$$$ contains the smallest $$$L$$$ numbers, still holds. Let $$$A_i$$$ be the maximum number in the array and $$$A_j$$$ be the second maximum. We consider two cases,
Case 1: If $$$i < j$$$, then removing $$$A_i$$$ from the array doesn't break the property. The operation to remove $$$A_i$$$ consists of $$$A_i$$$ and the element right before it ($$$A_i$$$ cannot be the first element, otherwise the property wouldn't hold)
Case 2: If $$$i > j$$$, then removing $$$A_j$$$ from the array doesn't break the property. The operation to remove $$$A_j$$$ simply consists of $$$A_j$$$ and $$$A_i$$$.
Implementation ideas: Since the array is guaranteed to be a permutation, checking each of the suffix-sums to see if they consist of the smallest natural numbers is enough. In other words, for a suffix of size $$$L$$$, we check if the suffix sum equals $$$\dfrac{L \cdot (L + 1)}{2}$$$.
Complexity: $$$\mathcal{O}(N)$$$
why is ranklist not visible?
Feedback on the problem set:
I really enjoyed Beautiful Permutation and therefore I really enjoyed the contest (even though I started competing half an hour late because I saw the announcement late), thanks to the authors.
It is funny that I wrongly bruteforced then produced Stirling numbers of the second kind.
Beautiful Permutation: It is easily oeis-able, I believe lol.
Yeah, Beautiful Permutaion is oeis-able, I just searched 40, 200, 280, 160
I came up with a solution which works for any N for Subsegment Divisibility, basically we can output 4 * i + (i%2).
About Erase All But One: This problem did actually originate from the problem you linked (the sample explanation section should make it obvious, I tried to keep the new statement similar to that one to respect the original problem). I missed the most important constraint in that problem when solving it, and coincidentally found the new version quite interesting too. Glad you liked the problem :)
I found it interesting that the first four problems all had simplistic solutions, although participants could get lost trying complicated ideas.
Boring trip was somewhat standard as you say, it has lesser submissions than I would expect.
Beautiful Permutation: I took the longest for this one, was thinking about two variable generating functions, etc. for long time. I saw that quite a few participants had solved this very quickly so looked for something simpler.
Later realized that answer could be derived from number of permutations in $$$n$$$ having $$$k$$$ records, and multiplying by $$$2^k$$$. This coupled with the fact that the probability of the $$$i$$$th number being a record in a permutation is $$$1/i$$$ independently of the other probabilities led to Stirling numbers of the first kind. I think this probabilistic reasoning would be much simpler than derivation from two variable generating functions.
Overall I enjoyed the contest.
There is actually bijection between number of prefix max and number of cycles in permutation. Hence that leads to Stirling number of first kind.
Aha right, you can use each record and all elements till the next record, in that order, to form a cycle.
How is Boring Trip a standard problem? Can you please elaborate? At first glance, it looks like TSP to me. Can't think of anything else. Can you give some hints about the idea to be used?
You can think on how will we arrange a fixed set of attractives (the sum of S is fixed, so only coordinates matters now). The first test in example is probably a big hint.
Thanks for the hint, Yeah the first sample test case helped a lot.
The problem would have been easier if k was odd, in that case, we just have to choose (k+1)/2 points on the right side which maximizes 2*disfrom middle point + s, and similarly for the left side. But if k is even, then the nearest point to the middle point will be traversed only once and the rest of the points will be traversed twice. I don't know how to handle this. Can someone please help as the editorial is also not published yet?
Actually it is easier when k is even. I think you get even and odd mixed up?
For example, if we take the sample test case, the middle point (or starting point) is having x=3, now I am telling the answer will be a summation of 2*dis + s, for all points except one which is just to right of it having x=5:
(2*(6-3)+4) + (2*(3-1)+7) + (1*(5-3)+7)
= 10 + 11 + 9
= 30
Finally add the s value of the middle point, i.e., 9 to get the final answer.
If k would have been odd, then each point will have 2*dis+s, and it would have been easier to handle as in this case we could have kept two multisets for left and right separately and then iterate for the middle point and update the two multisets as we shift the middle point.
I see. Even solution is pretty similar. How would you solve a task- the maximum non overlapping (prefix sum + suffix sum) of an array?
I have solved using this approach, hope it helps you in the implementation part. Although the code is quite long :(
You will have to modify a little bit and you will get the answers even when k is odd.I learned a lot from this problem and not publishing editorial has actually helped me :)
The editorial for beautiful permutation didn't appear yet, but I suppose it wouldn't contain generating functions (at least I know much easier way to prove the formula $$$2^k \cdot s(n, k)$$$), so can you please share your solution? :)
Start with one element $$$x$$$ and add others in order $$$n, n-1, \dots , x+1$$$. For every element there will be 2 positions next to $$$x$$$ that will increase the number of elements in $$$S$$$ by 1 and other positions will not increase $$$|S|$$$. Elements $$$x-1, \dots , 1$$$ also don’t increase $$$|S|$$$. So the answers will be the coefficients of
as a polynomial of $$$y$$$.
Yes! The solution is technical, but it requires fundamentally no ideas. I like when standard methods are powerful enough to replace brilliancy.
We can assume that $$$x=1$$$ (handling general values of $$$x$$$ is easy). Let $$$q(n, k)$$$ be the number of permutations of $$$1,2,\dots, n$$$ with exactly $$$k$$$ prefix maximums. The answer to the problem is
indeed we count the permutations grouping them by "$$$n_1$$$ elements before $$$1$$$ and $$$n_2$$$ elements after" and "$$$k_1$$$ maximums of good subarrays are before $$$1$$$ and $$$k_2$$$ maximums of good subarrays are after $$$1$$$". Fundamentally we are splitting the problem between the elements before and after $$$1$$$.
So, how can we compute such sum? Let us define the (exponential) generating functions (for $$$k\ge 0$$$)
This generating function is important for us because (straightforward from the definition)
Thus, we have to find a good expression for $$$Q$$$ (and then for $$$Q^2$$$). We have the following recurrence relation for $$$q(n, k)$$$ ($$$m+1$$$ represents the position of $$$n$$$ in the permutation)
which is equivalent to the following ODE for $$$Q$$$
Hence, we end up with the Cauchy-system (when $$$t$$$ is fixed):
Solving this (using that $$$\partial_s\log(Q) = \partial_s Q / Q$$$) one obtains the magical formula
Notice that this is the exponential generating function for (unsigned) Stirling numbers of the first kind (one can prove it by differentiating with respect to $$$s$$$, which is what I did during the contest). Hence, we conclude
SEGDIV: do a[i] = rng(), while array is bad, then increase i.
Simple construction for SEGDIV:
$$$a_i = 2\cdot i + i \% 2$$$
It works because $$$\sum_{i=l}^r a_i = (r-l+1)\cdot(r+l) + \sum_{i=l}^r i \% 2$$$ and the second part is strictly more than 0 and less than $$$r-l+1$$$.
fun facts from tester:
Anyway, thanks for your participation. We hope you like the contest!
An easy solution for SEGDIV.
Start with $$$1$$$ and then alternatively increase the value by $$$1$$$ and $$$3$$$.
Proof?
Refer to this : https://codeforces.net/blog/entry/99287?#comment-880655, it's similar, just the starting number is different.
Can anyone give a test case where merging the two arrays ( similar to how they are merged in merge sort) the length of the LIS would not be the sum of the lis of the smaller arrays in the problem Merged LIS.
A=[1,5,6]
B=[10,3,4]
I tried with the same approach initially and then realized that we can merge the two lis in the same way and that will be the maximum length possible.
Testcase:
1
4 3
3 2 2 2
6 1 2
One more easy solution for SEGDIV:
Just use this series. My Solution
Updated proof (previous proof was wrong):
Let us consider two $$$A.P.$$$ one with $$$a = 1$$$ and second with $$$a = 2$$$. Both have $$$d = 4$$$. Our answer consists of alternating terms of this two $$$A.P.$$$ Now, without losing generality let's assume that our subarray of length $$$N$$$ is of form : $$$1, 2, 5, 6, ...$$$
Now let's consider two cases.
$$$Case 1$$$ ($$$N$$$ is even):
$$$Case 2$$$ ($$$N$$$ is odd):
Did not receive Amazon vouchers for December Cook-Off 2021 Division 1 ;/
Did not even receive Oct ones yet :(
Ashishgup
Didn't get for October Lunchtime yet.
Dunno wth is happening with their financial team :(.
Is there any website or some extension through which our deltas in Codechef round can be predicted?
Any tips to improve in this type of contest I was only able to solve MERGEDLIS in div1. And don't have any idea about all the other problems. Thanks in advance