This time contest admin is newbie, so it will be a little bit easier than usual :)
We invite you to participate in CodeChef’s December Lunchtime, this Saturday, 25th December, rated for all.
Time: 8:00 PM — 11:00 PM IST
Setters: Jay JaySharma1048576 Sharma, Akshit akshitm16 Monga, Yuriy FairyWinx Fedorov, Manuj DarkSparkle Nanthan, Mradul bhatnagar.mradul Bhatnagar, Krupal KP1010 Patel, Alex kristevalex Kristev, Nikita vaaven Lazarev, Utkarsh Utkarsh.25dec Gupta
Testers: Nishank IceKnight1093 Suresh
Statement Verifier: Trung Đặng Kuroni Đoàn Đức
Editorialists: Taranpreet taran_1407 Singh
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!
What about October Amazon pay vouchers
Contest to begin in less than 15 minutes.
I don't know why the problem "Optimal Sorting" turned out to be very hard for me to figure out. Spent around 2 hours on solving it!
Feels great to fully solve more that 1/2 problems for a change.
Thanks for the wonderful contest.
Adding an easier problem in div 1 was a nice touch. I hope Codechef continues it.
Nice balanced contest for div-1. Thank you.
Understood, the community thinks otherwise.
I think Div1 was much easier than usual, so its not balanced imo.
I agree with you on the difficulty. Read your comment on Codechef as well and yes maybe the 5th problem was a bit too easy for D1 E but one problem being slightly easier shouldn't be too much I guess. Looking at the number of submissions I still feel it was balanced maybe could have been better with the 5th problem getting ~15 ACs and the last one ~5.
The number of ACs are not a good estimate today, the 4th problem (interactive one) was also easier for its position.
How do you solve Div. 1 C? I've only got solution for A=1, but I guess that gives no hints. :P
Good Problems. Liked the Contest.
isn't MNULS's testcase too weak?
the greedy solution: go to the largest B. once B = A + k, it'll be that all the way.
will pass the test, but 5340 93 can hack this solution. (correct:61, greedy:62)
We didn't come up with such a solution and it takes too many tests to cut off such stuff (
Okey, I don't understand how it could go, because I cut off such a solution explicitly, for ~1900k :/
This doesn't work even with n < k)))))
This provably works for N < K, because you just spend all your time squaring anyways, which the greedy does. There are ~300 values of K <= 5000 which break this solution, here are the paths that I found so far: https://pastebin.com/YLw8e13p. (The number after BAD is K, the top path is the greedy, the bottom path is optimal.)
Some of them are pretty interesting and require a few steps beyond K, like
No one has sent a normal solution for last problems behind O(k^2loglog) :/
how to do NOL_LESS? My n*sqrt*log solution with fft passes in 0.69/2seconds. But I hope you have a solution with adequate complexity.
I also passed the same, but it isn't n*sqrt(n)logn fully. I guess it's around nlog^2n or maybe even lesser.
The complexity is bounded by $$$\displaystyle \sum_{k=1}^{\sqrt{n}} k \log n + \sum_{k=1}^{\sqrt n} \dfrac{n}{k}\log n$$$. The first sum is $$$ O(n\log n)$$$ and the second one is $$$nH_{\sqrt{n}}\log n= O(n\log^2 n)$$$ where $$$H_k$$$ are harmonic numbers.
How to solve
Sleep Technique?How to solve
Optimal Sorting?We can't choose two subarrays that are intersecting for optimal solution.
WLOG assume array is a permutation. If it is not, we can convert it into permutation by replacing $$$A_i$$$ with $$$P_i$$$ where $$$P_i$$$ is its index in stable sorted array version.
Let $$$Q$$$ be sorted set of indices $$$ [ Q_1, Q_2, Q_3 \ldots Q_m ] $$$ such that $$$A[1 \ldots Q_i]$$$ contains all the elements from $$$1$$$ to $$$Q_i$$$. Then, it is optimal to choose indices of subarrays as $$$[(1 \ldots Q_1), (Q_1+1 \ldots Q_2), (Q_2+1 \ldots Q_3), \ldots ]$$$
Simple algorithm
Can you explain your logic for once?
Find the last position of every value in the sorted array then till the current index of that value in unsorted array is less than that original position we have to make at least a single operation to sort that subarray from I to that last position in between the way to that position check for other elements last position and update the current last position and finally when you reach the final last abort and. Do the operation.
It will always give you minimum no matter what is the order of array
Greatly balanced contest!!
I guess the test cases for OPTSORT are weak. My Solution which is supposed to give TLE on large test cases, passed.
are there prizes in this contest (for top 100 div-1 participants) ?
This account and This have rankings 200 and 201 and their codes are exact same for all problems . They did the same in earlier CookOff . Activities like this take down the credibility of ratings .
"Sleep Technique" looks like combining 2 very standard problems.I wonder how it got approved by CodeChef admin
What are these 2 problems?