We invite you to participate in CodeChef’s May Lunchtime, this Monday, 31st May, from 8 PM — 11 PM IST. Note the change in date and time.
There will be 7 problems in Division 3/2 and 6 problems in Division 1.
The May Lunchtime will have Junglee Games as the official contest recruiter! They are looking for SDE II & III Backend, SDE II & III Data, and SDE II Frontend roles for their fast-paced environment.
Joining us on the problem setting panel are:
Tester & Statement Verifier: Riley Monogon Borgard
Setters: Daanish Mahajan, Akash Whiplash99 Bhalotia, Aman Retired_cherry Dwivedi, Jatin jtnydv25 Yadav, Sundar Sundar Annamalai, Alex Um_nik Danilyuk
Editorialist: Aman Retired_cherry Dwivedi
Video Editorialists: : Chirayu Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Yashodhan ay21 Agnihotri, Bharat Singla, Shivam Bohra, Radoslav radoslav11 Dimitrov, Aryan Agarwala, Meet myth_gemphir Singh Gambhir
Mandarin Translator: Huang Ying
Russian Translator: Fedor Mediocrity Korobeinikov
Bengali Translator: Sakib SakibAbrar Abrar
Vietnamese Translator: Team VNOI
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: Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which they can claim cool CodeChef goodies. Know more here.
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.
Admin Note: Special thanks to Um_nik for his help in selection/improving the problems. This Lunchtime has a replay of some of the problems used in IOITC Day 1/2 (Final Selection round of Indian IOI Team). Thanks to all the testers who tested the IOITC as well!
Good luck and have fun!
As an official participant of the IOITC, the problems are very interesting and you will enjoy solving them.
As an official IOITC participant, why did you knowingly participate in the lunchtime and submit TST problems?
Reminder 1 — Contest starts in an hour.
Reminder 2 — Contest starts in 15 minutes.
Top mysteries of the world - 1. Bermuda Triangle 2. What Interactive MST statement meant.
3) How number of submissions for K-Subarrays doubled in last 20 minutes.
the protagonists had the plot armour called the 'power of friendships'
Since the tutorial are not available yet...
I would be happy to read something about SIMARRAY How to solve the simplest case, N=2?
For N=2, what I did was I fixed my R1 and then tried to calculate R2 using it.
I looped my R1 from 0 to 1000,adding 1e-5 after each loop,now since R2<=R1, I calculated the value for which (A2-R2*B2) gives 0 which is A2/B2.
Now if R1>=(A2/B2) , we can always set R2 to be (A2/B2) which will always give the term (A2 — R2*B2) to be 0. And if R1<(A2/B2), it is optimal to take R2=R1 because that is the nearest value from (A2/B2).
Now I find the minimum from all the different R1's.
Can you share your code?
Link to the submission
It is a bit hit and trial is what I feel ,so I don't think think this is the perfect solution.
For N=2 there are just 2 cases -
R1=A1/B1 and R2=A2/B2 in this case if R1>=R2 answer is zero.
Otherwise R1=R2=r.
We can write error as (A1-r*B1)^2+(A2-r*B2)^2.
In this case, it's a quadratic equation in r. You can check on the internet how to find the minimum.
Divide into consecutive blocks of equal r values. Then for each block [L, R], its contribution assuming same r for all indices in [L, R], is a quadratic in r. Then the value of r for the block [L, R] must be the one that gives the lowest possible value for this quadratic, else we can shift to the left or right to improve the objective, while maintaining the non-increasing property.
in the last 10 min I fell down 500 ranks -_- I solved A, B, C completely in div 2
is there any way to make codechef all contest reminder in my google calender, i just missed luchtime feeling sad :(
How to solve interactive mst ?
If there is $$$>1$$$ bridge, answer is $$$-1$$$ else its possible. Query all cyclic shifts of $$${1, 2, 3, \dots, m-1, m}$$$. If $$$e$$$ is not a bridge edge, then it'll appear in the cyclic shift starting at $$$e$$$, but not in the cyclic shift starting at $$$e+1$$$.
If you query edge $$$e$$$ with weight $$$1$$$ in some query, it'll have weight $$$m$$$ in the next cyclic shift. If it was a bridge edge, it would appear in both shifts. Else using properties of an MST, it would not appear in the second shift as there would be another edge with weight $$$<m$$$ which would be more optimal.
If the weights of all edges of the graph are distinct, then MST is unique.
So I queried for the weights as 1, 2, 3...m, then m, 1, 2, ..., then m, m — 1, 1, 2...
Now just forget the first edge (in permutation), then we can see the MST for the rest of the edges is unique. Now there are two possible cases:
Case 1: The left out edge for two consecutive queries is the same, in this case, we can conclude that it's a bridge because when we assigned it the smallest weight of 1, and when we assigned the largest weight of m, in both cases it's present in MST, but we don't know which one so we just increase the counter of bridges.
Case 2: If the left out edge is different in two consecutive queries, then we know the edge in the previous query should be the element in a permutation (for the previous iteration).
Now we can also prove that there can be at most 1 bridge. Because if there are two bridges they will always be included in any query and they can appear in any order so we can never decide. But if there is 1 bridge we can assign the left out edge from 0 to m — 1 and if there are no bridges then the above algorithm will find all permutations.
My submission — https://www.codechef.com/viewsolution/47278598
If the left out edge is different in two consecutive queries, then we know the edge in the previous query should be the element in a permutation (for the previous iteration). Can you please explain this with an example 1.
Take this graph example: https://ibb.co/sRfTpyF And the permutation is 3 1 2 0 4
Now suppose I query 1 2 3 4 5, then the MST we will get will be {3, 1, 0, 2}.
In the next iteration when I query 5 1 2 3 4, then the MST will be {1, 0, 4, 2}.
Here 3 is the edge that is not present in the second query (for which we have assigned the highest weight), which means 3 was the edge in the previous iteration.
But for 5 nodes there can be atmost 10 edges right ? Is it necessary that only one edge will differ in two consecutive queries?
Notice that in two consecutive queries we are only changing the relative order of 1 of the edges(where the weight is 1 and then m). If we ignore that edge the relative order of weights for other edges is the same, and since they are distinct, MST will be unique. So at max one edge will only differ. You can try it for multiple edges.
Okkk Thanks :)
Can K-Subarrays be solved with DP Convex Hull Optimization?
No need to do that. Simple recursive dp solution works just fine. The states would be dp[index][team_num][if_last_ele_was_included].
https://www.codechef.com/viewsolution/47197481
Thanks, but I was just wondering if it was solvable with CHT.
I believe, for this problem, CHT isn't required.
For
jbeing the number of block you want thei'thelement to be in, you have to use:dp[i - 1][j]— For including the current element inj'thblock, where the(i - 1)'thelement is ofj'thblock as well.max(dp[ii][j - 1]) for all ii < i— This is for starting a new block ati'thelement.So, for 2nd type of operation, you might think you need CHT, but you can maintain
prefix maximums for all j <= k, as there is no dependence of it on any other value related to thei'thelement.Although, instead of maintaining prefix maximums, you can use CHT, but it's just adding an extra
log nfactor to overall complexity.Link of Submission
you are initialising dp with -1, won't it give TLE when all the elements of the array are -1 or there are many subarrays with sum -1 ? I thought so and initialised my dp with -1e18, but it couldn't pass subtask3.
Didn't think of that at all! Can you try to hack my submission if possible?
yep, it gives tle on n = 40 k = 3 a[] = [-1,-1,....-1].
I initialised with -1e18 and did iteratively
CHESUB is the same as this PROBLEM, but with exactly $$$k$$$ transactions and incorporation of $$$i$$$ factor in summation.
Am I the only one who still can't understand what the problem 'Interactive MST' mean.
Where can I find the editorial for TRTOKENS?
here
CodeChef_admin Where is the editorial for PARTODD? I can't find it here.
^^ Source: jtnydv25 told solution in IOITC chat after TST.
I think observation 4 isn't really necessary though. My code passes easily without using that.
https://www.codechef.com/viewsolution/47275465
Thanks!
Observation 2 is very interesting for me. I didn't notice that the latter option solves everything.