### Ashishgup's blog

By Ashishgup, 5 months ago,

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:

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!

• +132

 » 5 months ago, # |   +23 As an official participant of the IOITC, the problems are very interesting and you will enjoy solving them.
•  » » 5 months ago, # ^ |   +47 As an official IOITC participant, why did you knowingly participate in the lunchtime and submit TST problems?
 » 5 months ago, # |   +7 Reminder 1 — Contest starts in an hour.
•  » » 5 months ago, # ^ |   +3 Reminder 2 — Contest starts in 15 minutes.
 » 5 months ago, # |   +49 Top mysteries of the world - 1. Bermuda Triangle 2. What Interactive MST statement meant.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +34 3) How number of submissions for K-Subarrays doubled in last 20 minutes.
•  » » » 5 months ago, # ^ |   +42 the protagonists had the plot armour called the 'power of friendships'
•  » » » 5 months ago, # ^ |   -8 my rank in last 10 minute went from 300 to 500
 » 5 months ago, # |   +5 Since the tutorial are not available yet...I would be happy to read something about SIMARRAY How to solve the simplest case, N=2?
•  » » 5 months ago, # ^ |   +5 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.
•  » » » 5 months ago, # ^ |   0 Can you share your code?
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   0 Link to the submissionIt is a bit hit and trial is what I feel ,so I don't think think this is the perfect solution.
•  » » 5 months ago, # ^ | ← Rev. 5 →   +7 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. A hint for subtasks 3 and 4Divide 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.
 » 5 months ago, # |   +8 in the last 10 min I fell down 500 ranks -_- I solved A, B, C completely in div 2
•  » » 5 months ago, # ^ |   -6 username checks out
 » 5 months ago, # |   +2 is there any way to make codechef all contest reminder in my google calender, i just missed luchtime feeling sad :(
 » 5 months ago, # |   +3 How to solve interactive mst ?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +54 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$. ProofIf 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 $•  » » 5 months ago, # ^ | +8 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 •  » » » 4 months ago, # ^ | ← Rev. 2 → 0 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. •  » » » » 4 months ago, # ^ | ← Rev. 2 → +3 Take this graph example: https://ibb.co/sRfTpyF And the permutation is 3 1 2 0 4Now 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. •  » » » » » 4 months ago, # ^ | 0 But for 5 nodes there can be atmost 10 edges right ? Is it necessary that only one edge will differ in two consecutive queries? •  » » » » » » 4 months ago, # ^ | ← Rev. 2 → +3 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. •  » » » » » » » 4 months ago, # ^ | 0 Okkk Thanks :)  » 5 months ago, # | 0 Can K-Subarrays be solved with DP Convex Hull Optimization? •  » » 5 months ago, # ^ | ← Rev. 2 → +1 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]. Link to submissionhttps://www.codechef.com/viewsolution/47197481 •  » » » 5 months ago, # ^ | +3 Thanks, but I was just wondering if it was solvable with CHT. •  » » » » 5 months ago, # ^ | ← Rev. 5 → +3 I believe, for this problem, CHT isn't required. For j being the number of block you want the i'th element to be in, you have to use: dp[i - 1][j] — For including the current element in j'th block, where the (i - 1)'th element is of j'th block as well. max(dp[ii][j - 1]) for all ii < i — This is for starting a new block at i'th element. 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 the i'th element.Although, instead of maintaining prefix maximums, you can use CHT, but it's just adding an extra log n factor to overall complexity.Link of Submission •  » » » 5 months ago, # ^ | ← Rev. 2 → +3 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. •  » » » » 5 months ago, # ^ | 0 Didn't think of that at all! Can you try to hack my submission if possible? •  » » » » » 4 months ago, # ^ | 0 yep, it gives tle on n = 40 k = 3 a[] = [-1,-1,....-1]. •  » » » » 5 months ago, # ^ | ← Rev. 2 → 0 I initialised with -1e18 and did iteratively Codevoid solve() { int n, k; cin >> n >> k; vector a(n); for (auto& it:a) { cin >> it; } long long dp[n][k + 1][2]; for(int i = 0; i < n; ++i) { for(int j = 0; j < k + 1; ++j) { dp[i][j][0] = -1e18; dp[i][j][1] = -1e18; } } // dp[i][j][0] -> we have j subarrays so far and we donot select ith element // dp[i][j][1] -> we have j subarrays so far and select ith element dp[0][0][0] = 0; dp[0][1][1] = a[0]; for(int i = 1; i < n; ++i) { dp[i][0][0] = 0; for(int j = 1; j < k + 1; ++j) { dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]); dp[i][j][1] = max({dp[i-1][j-1][0] + 1ll*a[i]*j, dp[i-1][j-1][1] + 1ll*a[i]*j, dp[i-1][j][1] + 1ll*a[i]*j}); } } cout << max(dp[n-1][k][0], dp[n-1][k][1]) << "\n"; }   » 5 months ago, # | ← Rev. 2 → 0 CHESUB is the same as this PROBLEM, but with exactly$k$transactions and incorporation of$i\$ factor in summation.
 » 5 months ago, # |   +19 Am I the only one who still can't understand what the problem 'Interactive MST' mean.
 » 5 months ago, # |   0 Where can I find the editorial for TRTOKENS?
•  » » 5 months ago, # ^ |   0
 » 4 months ago, # |   +1 CodeChef_admin Where is the editorial for PARTODD? I can't find it here.
•  » » 4 months ago, # ^ |   +28 ^^ 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
•  » » » 4 months ago, # ^ |   +13 Thanks!Observation 2 is very interesting for me. I didn't notice that the latter option solves everything.