We invite you to participate in CodeChef’s October Lunchtime, this Wednesday, 27th October.

Time: 7:30 PM — 10:30 PM IST.

PS: Note the change in the date. The contest will be on a Wednesday this month instead of the usual Saturdays. The contest will be rated for all three Divisions. Joining us on the problem setting panel are:

Setters: Soumyadeep palsoumyadeep Pal, Sandeep dazlersan1 V, Akshat iamakshat01 Mangal, Saarang saarang123 Srinivasan, Manan mexomerf Grover, Shivam, Bhavya pseudocoder10 Girotra, Alex Um_nik Danilyuk, Chaithanya Dragonado Shyam

Statement Verifiers: Soumyadeep palsoumyadeep Pal, Trung Kuroni Dang

Editorialists: Nishank IceKnight1093 Suresh, Ritesh rishup132 Gupta

Contest Admins: Radoslav radoslav11 Dimitrov, Yahor kefaa2 Dubovik

Head Admin: Alex Um_nik Danilyuk

Video Editorialists: Chirayu Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Yashodhan Molotov Agnihotri, Shivam Bohra, Aryan Agarwala, Meet mithh_gemphir Singh Gambhir, Bharat Singla

Mandarin Translator: Huang Ying

Russian Translator: Kostia lkosten Yarmash

Bengali Translator: Mohammad solaimanope Solaiman

Vietnamese Translator: Team VNOI

**Prizes:**

**Global Rank List:**

Top 10 global Division One users will get $100 each. Non-Indians will receive the prize via money transfer to their account. Indian users will receive Amazon vouchers for the amount converted in INR.

**Indian Rank List:**

Top ten Indian Division One coders to get Amazon Vouchers worth Rs. 3750 each. The rest in the top 100 get Amazon Vouchers worth Rs. 1500 each. First-time winners in Div 2 who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each. First-time winners in Div 3 players who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each.

However, everything else about our previous Laddu system for Lunchtime will continue without any change. To call out specifically, the top 10 school students in Div 1 of Lunchtime will continue to get Laddus as well as the cash/Amazon vouchers as per the new system. 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.

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!

Will the cash prizes continue as usual or are they gone?

Auto comment: topic has been updated by radoslav11 (previous revision, new revision, compare).Number of problems in each division? Is there some specific reason why the number of problems in each division are published in cookoff, but not in lunchtime and starters? Thank you!

Contest starts in 1.5 hours.

Reminder 2: 20 mins to go!

Partial-Forces

This contest is too hard for me

Not sure if it was intended for anything, but first time I got to use 4D Mo's algorithm for anything. Nice!

I think that the testcases for 35pts subtask on MAXSEG is weak. My $$$O(n^2)$$$ solution still passed. The problemset is actually great. Btw did anyone else also use counting sort in KTHGRID ?

Can anyone help me with Median Rearrangement solution of original constraints??

It is a binary search-based problem. We need to find the n elements optimally lets binary search over the answer and find if the current element can be our required maximum of minimums and check the other condition with the help of an auxiliary function which can be simulated by below algorithm easily.

Easy to Understand CodeI solved it as a greedy construction:

SpoilerIf each row is sorted, then the whole thing looks like this (S — some small values, M — row median values, B — some big values): ~~~~~ S1 S2 M1 B1 S3 S4 M2 B2 S5 S6 M3 B3 ~~~~~ With infinite $$$K$$$, the optimal median can be found in the following way. We can sort all values. Then the biggest values are assigned to B. The biggest among the remaining values are assigned to M. And S values are whatever is left. So that $$$S_x <= M_y <= B_z$$$ for any x, y, z.

Now if we want to also consider $$$K$$$, then we can safely throw away $$$B_z$$$ and look only at the combined set of $$$S_x$$$ and $$$M_y$$$ values. The problem is reduced to constructing a matrix, where each row is sorted and the sum of the largest values from each row does not exceed K.

As an example, let's look at sorted list of values [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15] from the testcase 2 (the largest values [16, 17, 24, 32] are thrown away). And then a recursive greedy algorithm checks the following arrangements, using a prefix sum array to calculate cost in constant time:

9,11,13,15], cost = 9+11+13+15 = the maximal possible cost9,9,11, 13,15], cost = 9+9+11+158,9,9, 11, 13,15], cost = 8+9+9+156,8, 9,9, 11, 13,15], cost = 6+8+9+15 <= K (found the solution!)5,6, 8, 9,9, 11, 13,15], cost = 5+6+9+153, 5,6, 8, 9,9, 11, 13,15], cost = 3+6+9+153, 3, 5,6, 8, 9,9, 11, 13,15], cost = 3+6+9+15 = the minimal possible costThe rearranged matrix looks like this (6, 8, 9, 15 are on the median, the thrown away values 16, 17, 24, 32 are appended to the right): ~~~~~ 1, 2, 6, 16 3, 3, 8, 17 5, 9, 9, 24 11, 13, 15, 32 ~~~~~

A link to my submission: https://www.codechef.com/viewsolution/53224037

Can you provide some details on how you checked the arrangement?

The codechef's editorial video provides a nice visualization for various things. My solution is similar in many aspects, but does processing in the reverse direction (starting from the maximum cost) and gets the answer directly. Instead of having it as a single step of a binary search.

I have also submitted a simplified C++ version, which should be much easier to understand. It's possible to add debug prints for tracing updates of the p1 and p2 indexes to see how it works.

Bonus: racer editions with faster i/o and faster sortingI suspect that right now these are the fastest available submissions for the MEDMAX problem on the codechef platform. Unless somebody uses better i/o and array sort code, which are the real bottlenecks here.

This is helpful, thank you

In TreeUps how do you find the minimum?

As far as I can see:

Any node at odd depth (considering root to be depth 1) will contribute abs(childCount — 1) nodes of a given color.

Each node at odd depth is independent of any other odd depth node and all even depth nodes are decided by their parent nodes.

So this becomes a problem of splitting these odd depth nodes into two sets with minimum difference of sum.

I can't think of any way to do this faster than $$$O(n ^ 2)$$$ so likely one or more of these points are wrong, but which?

$$$O(n^2)$$$ using bitsets

Sum of numbers is $$$n$$$, so there are at most $$$O(\sqrt{n})$$$ different numbers and you can do knapsack in $$$O(n\sqrt{n})$$$

And you can actually add bitsets here too, getting $$$O(n \sqrt{n/64})$$$. I don't know if there is anything faster.

How to do it using bitsets in $$$O(n \sqrt{n/64})$$$? $$$O(n \sqrt{n})$$$ soln editorial mentioned needs int in dp state instead of bool.

You only need int for small numbers, where you want to do sliding window. For big numbers add them one by one, even is they are equal, and use bitset.

Problems are nice but what was the point of making people use bignum/int128 in MAXIMGCD.Having ai<=1e9 would have been much better imo

How to find $$$\text{gcd}(x, yz)$$$:

There is a solution without int128 and without factorization.

Very good and balanced contest, thank you!

For C, I did something like this but i don't understand why it is wrong,

SpoilerAdded all elements of 2D vector into the single vector let say $$$T$$$ and sorted it.

applied binary search on indices of that single vector.

checked if the distribution is possible with minimum median as $$$T[mid]$$$. basically we need some elements to the left (to be precise $$$n/2$$$) and some elements to the right of the chosen median, i applied greedy approach to calculate cost for such distribution that goes like this -> we first take all possible elements which can be put to the left side of the medians, and then simply calculated the sum of all median. if the $$$sum<=k$$$ then returned 1 else 0.

I am sure the above statement is hard to understand, so the example is: $$$T = [1,2,3,4,5,6,7,8,9]$$$

let's just say mid is index = 3, we need 1 element to the left and 1 to right. 1 can go with first row, 2 can go with second row and 3 with third. our cost will be 4 + 4 + 5 (as these are medians) and other elements are distributed to the right side of medians.

the rest is simple binary search algorithm.

Please help me to figure out what is wrong with this approach

You approach is correct. Did you use correct limits for binary search i.e [n / 2, (n / 2) * n] ?

Can someone please tell me what's wrong in my code to the problem MEDMAX ? It shows the solution is partially correct. I am not able to identify the test case that my code gives wrong answer to. Here's the link to my submission(My code). Thanks in advance.

Never mind, I debugged my code.

SpoilerWhy last testcase is failing Help please !

Um_nik,radoslav11 there is no editorial for last two problems in div1, neither for the last month too, I just checked. Why is it so ?

Editorials for the last two problems of last month Lunchtime, I don't know what you just checked. We are working on editorials for the last two problems of this contest, they will be published soon.

What is the intended solution for kth grid?My O(n^(5/2)+q*n^(3/2)) got 95 points.Edit:got 98 points after optimizing block size

Also Um_nik — ""both 100 solutions from contestants are different and not present in this list 98 solution from contestant is also not present in this list, but our tester had it implemented yesterday""

I have finally described my original solution here. I will add more solutions later.

First-time winners in Div 3 players who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each.I Got global rank of 129 in October Lunch Time Div3 for the first time in top 200. How do I redeem the prize?

Codechef mails you, I got my voucher after 3 months probably.

Thanks Sir