We invite you to participate in CodeChef’s March Lunchtime, this Saturday, 19th March, rated for all.
Time: 8:00 PM — 11:00 PM IST
Bangalore-based credit management app giant CRED is on board to hire candidates from the Chef's pool.
Who can apply?
Anyone with 1-3 years of experience in product development, architecture, and design. In short, 2019/2020/2021 graduates are eligible to apply.
Where is the application form?
Visit the March Lunchtime contest page to check the JD & application form.
Joining me on the problem setting panel are:
Setters: Kishan K_B_G Gadhiya, Manuj DarkSparkle Nanthan, Jay JaySharma1048576 Sharma, Cozma tibinyte Tiberiu-Stefan, Daanish Mahajan, Voicu valeriu Mihai, Utkarsh Utkarsh.25dec Gupta, Kanhaiya notsoloud1 Mohan, Shikhar shikhar7s Sharma, Ma mazihang2022 Zihang, Nandeesh nandyboy Gupta
Head Admin: Alex Um_nik Danilyuk
Statement Verifier: Kanhaiya notsoloud1 Mohan
Contest Admin: Radoslav radoslav11 Dimitrov
Editorialists: Aman Retired_cherry Dwivedi, Prakhar prako_87 Kochar, Adithya infinitepro
Prizes:
Top 10 global Division One users will get $100 each.
Top 25 Indian Division One coders to get Amazon Vouchers worth Rs. 1500 each.
Also, announcing Scholarship for CodeChef Certification in Data Structure & Algorithms — More than 100 Indian participants in Divisions 1, 2, and 3 will win scholarships for the CodeChef Certification exam (discounted prices). Scholarship criteria can be found in the respective contest pages.
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!
How to solve Mathology for full points? I was able to solve only 2 subtasks (5+10 score).
Same..
I tried square root decomposition and segment tree ideas but they didn't work within TL.
Were you using MO's algorithm ?
Yes.
What was your idea?
You can solve it using sweep-line on an array by noting that there can be at most $$$d$$$ divisors of a number where $$$d \approx 200$$$.
I was able to cheese an $$$O(Q d \sqrt{N} \log \max_{i} a_i)$$$ solution that used Mo's algorithm and Fenwick tree, so tests were probably weak. The complexity might be better though, since I took some care to avoid adding an element to the set of possible GCDs more than once.
My solution was $$$O(dn\log(dn + Q) + Q\sqrt{N})$$$ without Mo and Fenwick, thanks to some recently published trick of -is-this-fft- (point remax in $$$O(1)$$$ and prefix max in $$$O(\sqrt{n})$$$ as there are a lot more operations of the first type than that of the second). However, it still took 1.48s.
I solved it with offline solution using sweep line using segment tree to find range maximum queries — the complexity was O(N * d * log n + q * log n) but I got TLE so I noticed that number of updates in the range maximum queries is O(N * d) while number of queries is only O(Q) so I replaced segment tree with standard sqrt decomposition which is faster to update slower to query, the complexity became O(N* d + Q sqrt N) which passed the tests.
My solution was like this:
Initialize an array $$$mx[n]$$$ with all values equal to $$$1$$$.
Iterate over the array $$$a$$$. While iterating at index $$$i$$$, iterate over all the divisors of $$$a_i$$$. Let the divisor we are iterating currently be $$$d$$$. Find the maximum index $$$j$$$ such that $$$j<i$$$ and $$$d$$$ is a divisor of $$$a_j$$$. Now, update $$$mx_j := max(mx_j, d)$$$. After processing all the divisors of $$$a_i$$$, we can process all the queries having $$$r = i$$$. The answer of each query having $$$r = i$$$ is $$$max(mx_l, mx_{l+1}, mx_{l+2}, ..., mx_r)$$$ which can be solved using segment tree.
The complexity is $$$O(n\times k \times \log{n})$$$ where $$$k$$$ is the maximum number of divisors of a number which is $$$128$$$ for $$$a_i \leq 10^5$$$.
Just use sqrt decomposition instead of segment tree to find the max, you will get better complexity, using segment tree I got TLE.
I got TLE for the first time. But, by using the bitwise operator inside the segment tree and iterating over the divisors in descending order got accepted. Iterating in ascending order over the divisors was re-updating the value of $$$mx_j$$$ for different divisors.
In Mathology, after a trivial observation, that it is optimal to choose a subsequence of size 2, the problem becomes the same as this problem
But, it's editorial is not available there ig!
I missed 100 points and 27 rank because of that :/
SPRALL has multi-testcases and i forget to clear the array :/ I only remembered 1 second after the contest
Should Have Solved SUBSEQ first :-(