We invite you to participate in CodeChef’s April Lunchtime, this Saturday, 25th April, from 7:30 pm to 10:30 pm IST.
3 hours, 5 problems.
We will also be hosting two live problem discussion sessions on Sunday (26th) from 5pm to 6:30pm IST (first 4 problems) and on Monday (27th) from 5pm to 6:30pm IST (last 3 problems), where our panelist, RestingRajarshi will discuss the Lunchtime problems. Find more details here.
Also, 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.
Joining me on the problem setting panel are:
- Setters:Jubayer Alpha_Q Rahman, Shahadat s_h_shahin Hossain Shahin, Md Mahamudur sajibreadd Rahaman Sajib
- Admin & Tester: Teja teja349 Vardhan Reddy
- Editorialist: Taranpreet taran_1407 Singh
- Post-Contest Streaming: Rajarshi RestingRajarshi Basu
- Statement Verifier: Jakub Xellos Safin
- Mandarin Translator: Gedi gediiiiiii Zheng
- Vietnamese Translator: Team VNOI
- Russian Translator: Fedor Mediocrity Korobeinikov
- Bengali Translator: Mohammad solaimanope Solaiman
- Hindi Translator: Akash Shrivastava
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.
Good luck and have fun!
sajibreadd , are problems in lunch time sorted according to difficulty or randomly placed ?
Initially it is random but it gets sorted according to number of people who solved that problem.
As usual as the previous lunchtimes.
Problem Statements not loading
Problems aren't visible?
Remember march lunctime?
But this month's cook off went pretty smoothly.
Last 4/10 ltimes were unrated so...
Yeah, but this is codechef xD.
Though they were surprised too how it went so smoothly.
pathetic smh
Problem are not visible.
why these type of problem always happen in lunchtime
CodeChef always finds ways to suck!
super shitty platform.
and now they suddenly load all the problems without any proper delay or announcement??!!
lol i quit
Codechef is broken, deeply broken.
even for discussion we rely on cf
*fucked
Where are the problems? xd
Problems are not opening .
I reported at bugs@codechef.com , hope ,you will resolve it soon.
Hope is good.
Has anyone actually tried to write to bugs@codechef.com? :D
At least stop the timer.
The problem is... how to find the problem...
U cant find them because the problem's name is JOHN CENA.. XD
Lunchtimes on Codechef : —
They are open now
Now Problem are visible.
Problems visible!
Will this contest be rated ???
Yes, 10 minutes extra are given
How to solve Positive Mex ?
Sort and store all the numbers with their frequency. Now, if the smallest element of them all is NOT equal to 1, then $$$\displaystyle ans\ =\ 2^{n}$$$ since all the subsequences of this array would have 1 as their mex. Else, for each element check if this element can be made as the mex of some subsequence from our input array. If it can be made, then the contribution it makes to the answer is $$$\displaystyle \ 2^{m}\prod \left( 2^{x_{i}} \ -\ 1\right)$$$ where, x is the count of each number present in the array that is smaller than the current number and m is the count of all all elements greater than this element.
It is suspicious regarding "Jumping Fever". Its first subtask is way too easy for no ACs :)
What is the intended time complexity for TRIQRY?
My O(N logN) solution TLE's for Java. Even I implemented a custom ArrayList, so ig that shouldn't be the problem.
yes the intended complexity is O(NlogN), i solved it using pbds + offline queries
How did you solve the problem?
A point (xi,yi) will be inside the triangle if xi-yi>=l and xi+yi<=r.(by find the equations of both the lines and then check condition for 2 point to be on one side of a line)
Now make the pairs of (xi-yi , xi+yi) {or vice versa} , sort them and start from backwards to do offline queries
I am not aware of offline queries yet. Can you please elaborate this statement? "sort them and start from backwards to do offline queries"
What do we achieve by doing this?
okay so in offline queries we reorder the queries depending on the situation which actually gives some benefits in finding answer of all queries rather than solving queries in the order given in input.
I dont know any tutorial but i will suggest to try this problem KQUERY. You can google its solution to know how it works
Unfortunately, TreeSet in Java comes with a heavy constant factor. Replacing it with a sorted array would probably help.
It still TLE's :(
The problems were very cool, Thanks.
Why are constraints so large for TRIQRY? My O(N*logN) solution didn't pass for 100 points. (I know PBDS — indexed set has comparatively greater constant factor but still I see no point in setting such large constraints.)
Yes, at least TL 2.5 secs would have had been fine XD.
Use Fenwick Tree
I too used Fenwick Tree, got AC on first attempt. Here is my submission.
Yeah, the time limit was quite strict. My code passed after the contest just by changing an int to a bool. Check the difference between non-ac and ac solution: Diff
And mine got accepted just by resubmitting the same code. The time limit should have been more relaxing so that one should not depend on his luck.
From setters perspective there is a point of setting large constraints is to secure the data set. Suppose I have set n <= 10^5, Then if triangles have less than 10^3 points in its region then lot of bruteforce type suboptimal solution will pass and my solution takes .83 sec, So I have set 2 sec TL(twice of it). Yeah I agree with you that 2.5 sec would be cool but using pbds for 10^6 constraints is risky for even 2.5 sec also.
Hi all I hope you guys had a nice contest. The editorials for first six problems are ready and would be available in some time.
Posting basic idea for last problem below.
Suppose we want to compute $$$f(u, v)$$$ such that the path is $$$u = a_1, a_2 \ldots a_L = v$$$ and LCA is $$$a_k$$$. $$$f(u,v) = \sum_{i = 1}^L i*W_i$$$ can be written as $$$\sum_{i = 1}^k i*W_i + k*\sum_{i = k+1}^L W_i + \sum_{i = k+1}^{L} i*W_i$$$
Consider a pair $$$(k, \sum_{i = 1}^k i*W_i)$$$ and pair $$$(\sum_{i = k+1}^L W_i, \sum_{i = k+1}^{L} i*W_i)$$$, the combination of this pair is a valid path. Also, it is of the form convex hull optimization.
Suppose we for each node $$$u$$$ in the tree, we want to find the maximum score of trip starting somewhere in subtree of $$$u$$$ and ending at $$$u$$$. Calling this $$$UP_u$$$
Similarly, we want the maximum score of the trip starting from $$$u$$$ and ending somewhere in subtree of $$$u$$$. Calling this $$$DOWN_u$$$
We can compute both using dsu on tree trick
After that, we need to use dsu on tree and convex hull trick again, while handling offsets to avoid rebuilding hull at each node and instead using heavy child's hull.
Will post detailed editorial as soon as possible.
EDIT: Solutions
EDIT: Slight mistake in original editorial, updated now. I really apologize for inconvenience.
The first 6 editorials are posted.
This problem is quite, quite similar to this one: Link. If I am correct, only changing the line equation by adding the dp value of the current node will be enough. If this is the case, then this problem is just a repeated one.
I have read this problem. This problem just tells to do make prefix sum of path from u to v and in JMPFVR you have to choose all possible way of jumping from u to v. May be solution converts to this problem after doing some stuff like "maximum cost from a node and all of its descendnts" but that doesnt mean it is repeated one.
It's obviously the quite similar. You just have to maintain a dp[u] which will store the best path to all its descendants and add a constant term of dp[u] when adding the line. I don't think it's much different. It would be possible for someone to copy the exact code submitted in the mentioned problem, do small tweaks and submit. The person doesn't have to code the majority of the part, which includes "DSU on tree" and prefix and suffix of its descendants. I think that the implementation was the real reason of no AC submission during contest.
And one more question, were the solutions rejudged after the contest? I distinctly remember that I submitted the problem just after the contest and got wa after wa even after 14-15 attempts and then gave up. Even the subtasks were not passing. But now I see that all my submissions got ac.
Here is the submission to the cf problem : Link
Here is the submission to the cc problem : Link
Here is the difference: Link
Would you now say that its quite different? Most of the difference is due to the fact that there were multiple test cases in the lunchtime problem.
I have told you that solution might be similar but there should be difference between "repeated one" and "similar solution". Then TRIQUERY should be a repeated one cz I have solved a lot of problems like "how many segments are completely enveloped by a segment" and guess what I dont need to change a single character of my code and I will get ac. So Here the thing that is wanted is different(very different) but thing is they can be found similar way. And I think I don't need to read the codes. I have read that problem and I get your point at that time. If I preprocess dp(u) = max score from node u to all of it's descendents using all possible jumps and pd(u) = max score from all of it's descendnts to u using all possible jumps, then solution is similar. Cz you need to check two cases, pd(u) + direct_jump_score(u,v) + dp(v) and pd(u) + direct_jump_score(u,lca) + direct_jump_score(lca,v) + dp(v) and this problem solves that direct_jump_score(u,v) part so we just need to change m and c of lines. More specifically we need to add dp(u) to c and may be some changes in m(according to my solution). So this can be solved in same way. So " similar solution" and "repeated one" looks different statement to me.
What I am trying to point out is that 90% of the implementation is the same? Had I read the last problem during the contest I would have surely got ac. But had I not solved this problem but knew what was the approach, I wouldn't have been able to solve this during contest. The hard part was the implementation, which could be bypassed. I guess say that it is repeated would not be correct though.
But what about the rejudging? Why were the submissions rejudged?
May be you would have got ac may be not that's not the issue. This is not repeated one surely but as a contestant perspective solution is similar but I will point out this part direct_jump_score(u, v)(which is recommended in your problem) and max(direct_jump_score(u, a1) + direct_jump_score(a1, a2) + .... + direct_jump_score(am, v))(recommended in my problem) for all possible {a1, a2, a3.....ak} looks very different to me. Yp its rejudged now.
Do you have any idea how many such problems I've solved?
I had TLEs on both TRIQRY and HXR because of bad constants. (I used pb_ds on TRIQRY and matrix expo + binary lifting on HXR). Were we expected to use bitsets instead of boolean arrays on HXR? Either way, please increase the time limits next time. I don't see the point of making us try constant factor optimization in-contest.
That said, I enjoyed the problems. Kudos!
I also used arrays instead of bitsets, got TLE, and wasted much time of the contest in optimizing it.
edit: just ignore this, this comment is wrong
There's apparently a way to do a matrix multiplication in $$$O(n^2)$$$ for HXR (which I don't really understand, but you can look at submissions), so "naive" $$$O(n^3\log{K})$$$ was probably intended to fail the second subtask.
I agree TRIQRY had too-tight limits. But you could have replaced pbds with a Fenwick tree for a much lighter constant (which I had to do)
Yp, it's expected to use bitset in HXR. For TRIQUERY I have used bit, and we have given 2 times more TL than my solution.
Need help in proceeding through different approach of the problem DOTTIME :
My approach : I maintain a segment tree seg[N], where seg[i] represents the sum of all the elements which multiplies to A[i]. (Consider A[i] to be the first element of the product pair)
I proceed to check how A[i] multiplies to the elements from j = 1 to n, by creating an array B[N][N] (Just for bruteforce), where B[i][j] represents how many times A[i] and A[j] multiplies.
I observed that B is symmetric and each row of B is a combination of 4 Arithmetic Progressions. Which first increases from 1 with difference 1 ,then some constant terms , and then decreases to 0.
(This helps me to do 4 range updates in segment tree for each query.)
It was complicated for me to find the indices where these APs start in temrs of i. Can anyone help me with a neat way to find this ??
Did the same thing using Fenwick tree, although code is not very neat.
It seems different than what I am asking for. The way I planned to update answer is simply A[i]*query(i,i).
Can someone tell me in TRIQRY, how to find number of points which satisfy x-y>=li and x+y<=ri ?
My Submission.
Maintain a fenwick tree(BIT) on (x + y). Update it for all points by 1. Maintain the queries in sorted order in terms of l.
Now for each query from left to right, all the points that have (x — y) before l, cannot be in our answer, and cannot even be for next queries, because queries are sorted in l. So remove these corresponding (x + y) from BIT, by updating these indices by -1.
Now just get the query(r + 1) from BIT to get the count of the segments which are ending at <= r. By deleting useless segments earlier, yoh have made sure, these segments have x — y >= l as well, and thus the answer follow.
Beautifully done.
Can somebody please provide a test case for which my code fails I tried to do it with segment trees I have already tried many test cases and my code passes for all. It would be great if someone could find a flaw in my solution MY WA solution: https://www.codechef.com/viewsolution/32875190