We invite you to participate in CodeChef’s July Lunchtime, this Saturday, 31st July.
Time: 6 PM — 9 PM IST.
The contest will be rated for all three Divisions. We also have a new prize structure for global & Indian participants. More details are given below.
Joining us on the problem setting panel are:
Setters: Soumyadeep Slayer_21, Souradeep Paul, Piyush present_sir Mittal, Vansh kvansh Kaul, Ayush Singh, Tianyi, Rahim Nots0fast Mammadli, Prasant prasant21 Kumar
Head Admin: Alex Um_nik Danilyuk
Contest Admin: Radoslav radoslav11 Dimitrov
Tester: Riley Monogon Borgard
Statement Verifier: Jakub Xellos Safin
Editorialists: Aman Retired_cherry Dwivedi & Istvan iscsi Nagy
Video Editorialists: Chirayu Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Yashodhan ay21 Agnihotri, Shivam Bohra, Aryan Agarwala, Meet myth_gemphir Singh Gambhir, Rajarshi RestingRajarshi Basu
Mandarin Translator: Huang Ying
Russian Translator: Fedor Mediocrity Korobeinikov
Bengali Translator: Sakib SakibAbrar Abrar
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!
ICPC Amritapuri Mock round also at 6 pm today. Why CodeChef always changes the time for its monthly contests.
Unfortunately there is also a Topcoder Open contest today which was clashing with our usual time slot. After speaking with both TopCoder and Codedrills, we have decided to have the Lunchtime at 6pm. The clash with the ICPC Practice Contest is unfortunate and sadly unavoidable.
The clash with ABC was not known till a few hours back, and we have reached out to them to see if they can reschedule it. But it is too late for us to reschedule the Lunchtime now.
Clashes with ABC :(
Please shift it to 8:30 pm or 9 pm .
It will benefit most people here.
As ICPC mock test is also from 6 PM.
Ashish_gup clarified it here
Moni moni
$$$‿$$$Is nlogn DP intended for div2D? How to avoid map then? I kept receiving TLE on one test.
changing to unordered_map worked for me
Unfortunately, for me it didnt help. Can't wait to see official solution :)
same
One trick would have worked. use mp.count() to avoid adding unnecessary elements to map. Unfortunately realized this after contest :)), it passed. Kept getting TLE throughout the contest.
After a lot of sub, adding 2 things worked for me:
1) instead of a map for each bit, save 1 map only. For number i and bit j, store result in i*100+j.
2) Use PBDS hashmap instead of unordered_map.
I'm interested in knowing how these time limits got approved.
Please tell your approach.
For me, an array of size O(log(A[i])) is enough.
Dp[i][j] <-> number of sequences in prefix [1...i] if we formed exactly j groups (and the end of the last one is at point i). To transition I need to ask about sum of previous DP's with particular XOR of prefix, or I need to get last index of particular prefix xor modulo $$$2^{j-1}$$$ for j <= 60. How is small array sufficient for you?
The transitions become much harder this way.
Instead of prefix,use suffix because : If group j starts from index i, then xor of suffix [i...n] is multiple of 2^j. and (j+1)th group can start from any index k > i without disturbing jth group.
Then, DP[i][j] => Number of sequences in suffix [i...n] where $$$j_{th}$$$ group start from $$$i_{th}$$$ point.
For transitions,
1) suffix[i...n] is the last group : 1 way
2) next group starts at index k > i : DP[k][j+1] ways.
So we can just store sums of DP[i][j] for each j. Ideally we would have to maintain it for j <= n (when xor is 0,we can have many groups), but again all values after j >= log(A[i]) will be same.
I've always wanted to ask that CodeChef is based in India and in India, the time at which CodeChef Lunchtime happens is more like dinner time than lunchtime. So why this contest is named Lunchtime?
Because chef eats his lunch in the evening
https://blog.codechef.com/2016/02/09/lunchtime-moves-away-from-lunch-time/ https://www.codechef.com/LTIME01
Btw for div1 are the prizes for all indian participants who are in global top 100 or top 100 indians? I mean there are not even 100 Indians who solved a single problem.
How to solve Ancient Magic ?
There is 2 ways : a) Have a good graph and run max flow min cost on it. By good graph i mean, graph with not too many edges, not too many nodes. There s multiple ways to contruct such a graph with n logn nodes, n log n edges, one of them is described in the editorial on codechef. b) Use a modified version of the RSK algorithm to account for weights.
ABC and Lunchtime clash
Tourist: Let me quickly AK ABC fast so I can make it in time to win Codechef Lunchtime
Can someone clarify rest top 100 refers to the Indian ranklist or Global? As of today, less than 80 Indian participants were there. So, will everyone be getting amazon vouchers?
Very subtask, much wow
In problem BADLUCK, I lost 15 points because of an interesting TLE, and need help understanding why it happened.
AC: 20pts solution
TLE: 5pts solution
The difference between them: in the TLE code, I am maintaing a separate permutation vector and indexing into the original vector using the permutation indices. And in the AC code, I am directly permuting the input array.
The AC code passes in 0.4sec whereas TLE code fails in 1.01 sec, so I think the difference is huge. I would expect TLE code to be slower but not by a factor of 2.5.
I know that this might have something to do with locality of reference while caching, but the vector size is only 11 or less. Why would caching effects be so pronounced in such a tiny vector?
Or is there some other issue here? I've used permutation arrays frequently in the past in such situations so I'm sad and surprised that it failed today :(
Ah.. that was BADLUCK for sure :(
Testcases might be weak where array might contain duplicates. In that case, your AC will cover only distinct permutations while your TLE code generates all permutations.
Example — array is [5,5,5,5,5,5,5] then your AC code generates only 1 permutation while your TLE code generates 7! permutations.
Thanks, it seems tests are indeed weak. I ran my 20 points code for this test:
and it ran in 6seconds on my machine. So during contest it should have clearly failed and gotten 5 points only.
My solution to Matrix Permutations was quite different from editorial.
The idea is similar to GCJ2017 Round 3 problem D. First observations are the same as in editorial: we only need to find array $$$cnt$$$ such that $$$cnt[i]$$$ is the number of cells with distance to closest cannon being exactly $$$i$$$. Let's fix some cannon $$$A$$$ and calculate $$$cnt$$$ for all cells such that the closest cannon to them is $$$A$$$. And to make it easier, let's split plane around cannon $$$A$$$ into four quarters and process each one independently. Without loss of generality I will assume it's upper right quarter.
Let's choose some cannon $$$B$$$ and find all cells in this quarter such that they are closer to the $$$A$$$ than to the $$$B$$$. There are 4 possible cases (I will not consider equal coordinates):
1) $$$x_B < x_A$$$, $$$y_B < y_A$$$, then all points are closer to $$$A$$$
2) $$$x_B < x_A$$$, $$$y_B > y_A$$$, then either all points are closer to $$$A$$$, or there exists some $$$y$$$ such that points below $$$y$$$ are closer to $$$A$$$ and others are closer to $$$B$$$
3) $$$x_B > x_A$$$, $$$y_B < y_A$$$, this is similar to previous case, only now we have vertical border
4) $$$x_B > x_A$$$, $$$y_B > y_A$$$, this is the most interesting case, and there are two possibilities
And we need to find this blue area for each cannon $$$B$$$ and then find intersection of all of this. I won't go much into details, but if you look at the border as a function $$$f(x)$$$, then you have some horizontal segments and some diagonal segments. Then there are at most $$$2k$$$ interesting points and between each consecutive pair you can find lowest diagonal segment and lowest horizontal segment and then intersect them again if needed. This all can be done in $$$O(k \log k)$$$
After that you end up with pieces of two types:
Each one you can split into two or three more parts as shown above. And then for each part you have to add some linear function to a segment of array $$$cnt$$$, which can be done offline in $$$O(1)$$$.
The total complexity is $$$O(K^2 \log K + N + M)$$$
thanks Maksim1744 for sharing your approach. It will help a lot of people see the problem from a different perspective. Congratulations on being the only person to solve this problem.
Thanks for sharing your approach. I also tried to approach it the same way. I considered all cannons at the same time and marking cells nearest to one particular cannon, trying to build Voronoi diagram with Manhattan distance as distance function instead of euclid distance.
Didn't manage to solve it.