By radoslav11, history, 6 weeks ago,

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:

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!

• +148

 » 6 weeks ago, # |   +7 Will the cash prizes continue as usual or are they gone?
 » 6 weeks ago, # |   0 Auto comment: topic has been updated by radoslav11 (previous revision, new revision, compare).
 » 6 weeks ago, # |   +5 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!
 » 6 weeks ago, # |   +9 Contest starts in 1.5 hours.
•  » » 6 weeks ago, # ^ |   0 Reminder 2: 20 mins to go!
 » 6 weeks ago, # |   +4 Partial-Forces
 » 6 weeks ago, # |   +25 This contest is too hard for me
 » 6 weeks ago, # |   +42 Not sure if it was intended for anything, but first time I got to use 4D Mo's algorithm for anything. Nice!
 » 6 weeks ago, # |   +3 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 ?
 » 6 weeks ago, # |   0 Can anyone help me with Median Rearrangement solution of original constraints??
•  » » 6 weeks ago, # ^ |   0 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 Codebool isit(multiset mse, ll mid, ll k, ll n) { ll req = n / 2; ll arrays = 0; ll sum = 0; while(arrays < n) { ll z = 0; while(z < req) { mse.erase(mse.begin()); z ++; } if(*mse.rbegin() < mid) { break; } auto it = * mse.lower_bound(mid); mse.erase(mse.lower_bound(mid)); sum += it; arrays ++; } return arrays >= n && sum <= k; } void solve() { ll n, k; cin >> n >> k; ll start = n/2, end = n * n - 1; ll ans = -1; vector tot; for(ll i = 0; i < n; i ++) { for(ll j = 0; j < n; j ++) { ll x; cin >> x; tot.push_back(x); } } sov(tot); // sort vector multiset mse; ll t = ((n + 2) / 2) * n; for(int i = 0; i < t; i ++) { mse.insert(tot[i]); } start = n / 2; end = t - 1; while(start <= end) { ll mid = (start + end)/2; if(isit(mse, tot[mid], k, n)) { ans = tot[mid]; start = mid + 1; } else { end = mid - 1; } } cout << ans << endl; } 
•  » » 6 weeks ago, # ^ |   +6 I 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: [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 9+11+13+15 = the maximal possible cost [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 9+9+11+15 [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 8+9+9+15 [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 6+8+9+15 <= K (found the solution!) [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 5+6+9+15 [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 3+6+9+15 [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 3+6+9+15 = the minimal possible cost The 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
•  » » » 6 weeks ago, # ^ |   0 Can you provide some details on how you checked the arrangement?
•  » » » » 5 weeks ago, # ^ |   0 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 sorting a single $O(N L)$ solve function: 35 milliseconds AC $O(N L)$ prefix sum array creation and $O(N+L)$ solve function: 30 milliseconds AC I 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.
•  » » » » » 5 weeks ago, # ^ |   0 This is helpful, thank you
 » 6 weeks ago, # | ← Rev. 2 →   +20 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?
•  » » 6 weeks ago, # ^ |   +59 $O(n^2)$ using bitsets
•  » » 6 weeks ago, # ^ |   +71 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})$
•  » » » 6 weeks ago, # ^ |   +16 And you can actually add bitsets here too, getting $O(n \sqrt{n/64})$. I don't know if there is anything faster.
•  » » » » 6 weeks ago, # ^ |   +6 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.
•  » » » » » 6 weeks ago, # ^ |   +11 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.
 » 6 weeks ago, # |   +9 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
•  » » 6 weeks ago, # ^ |   +43 How to find $\text{gcd}(x, yz)$: long long g = gcd(x, y); return g * gcd(x / g, z); 
•  » » 6 weeks ago, # ^ |   +29 There is a solution without int128 and without factorization.
 » 6 weeks ago, # |   +35 Very good and balanced contest, thank you!
 » 6 weeks ago, # | ← Rev. 2 →   0 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
•  » » 6 weeks ago, # ^ |   0 You approach is correct. Did you use correct limits for binary search i.e [n / 2, (n / 2) * n] ?
 » 6 weeks ago, # | ← Rev. 2 →   0 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.
 » 6 weeks ago, # | ← Rev. 2 →   0 Spoilerll n,k; cin>>n>>k; ll a[n][n]; vll t; for(ll i=0;i>a[i][j]; t.pb(a[i][j]); } } sort(all(t)); if(n == 1){ if(t[0] <= k) print(t[0]); else cout<<-1<= n/2 and l < r){ if(done == till){ done = 0; r -= 1; } if(l < r) maxsum -= (t[r] — t[l]); if(maxsum <= k){ cout<
 » 6 weeks ago, # | ← Rev. 3 →   +14 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 ?
•  » » 6 weeks ago, # ^ |   +16 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.
 » 6 weeks ago, # | ← Rev. 2 →   0 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
•  » » 5 weeks ago, # ^ |   +16 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""
•  » » 5 weeks ago, # ^ |   +13 I have finally described my original solution here. I will add more solutions later.
 » 5 weeks ago, # |   0 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?
•  » » 5 weeks ago, # ^ |   0 Codechef mails you, I got my voucher after 3 months probably.
•  » » » 5 weeks ago, # ^ |   0 Thanks Sir
 » 12 hours ago, # | ← Rev. 2 →   0 I wasn't able to find the Editorial for MAXSEG, can someone explain the solution or share the Editorial if exist?