We invite you to participate in CodeChef’s June Cook-Off, this Sunday, 21st June, from 9:30 pm to 12:00 am IST. 2.5 hours, 5 problems.
We will also be hosting a live problems discussion session for Cook-Off problems with our panelist Rajarshi RestingRajarshi Basu on 23rd June, 4 pm IST. You can register by clicking on the GOING button at the top right corner 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 us on the problem setting panel are:
- Setters: Jubayer Alpha_Q Nirjhor, Tasmeem Bruteforceman Reza, and Rezwan Rezwan.Arefin01 Arefin
- Admin: Teja teja349 Vardhan Reddy
- Tester: Raja raja1999 Vardhan Reddy
- Editorialist: Taranpreet taran_1407 Singh
- Post-Contest Streaming: Rajarshi RestingRajarshi Basu
- Statement Verifier: Jakub Xellos Safin
- Mandarin Translator: Qingchuan Zhang
- 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 participants will receive CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.
Good luck and have fun!
It would be great if we get CF rounds also from this trio.
Overlaps with SRM :(
Bump: who wants a ___ contest? Starts in ~699s ( ͡o ͜ʖ ͡o)
how to solve per capita?
DSU and some implementation stuffs , note that we will take maximum value of fraction among the nodes and all nodes with maximum fractional value can be our answer.
Just run DFS across nodes with same ratio from each node with maximal ratio and return the largest found connected component.
Editorials for all problems posted here. Hope you guys had fun!
Did anyone solve the last problem using suffix automata? If so, can anyone tell me why this code is giving tle? My solution has a complexity of O(N * K * 4).
Have shared it with tester (I'm not good in cpp). He'll have a look.
You should read the guide to auto-vectorization. Trying to vectorize/unrolling a code that isn't vectorizable will actually slow down your code.
You code gets AC in 2.17 sec without those pragmas.
Oh. I actually coded another solution without pragma, and that had an even more bad constant factor, so I added the pragma at that time. Didn't think it would slow down the code to the point of not getting AC. Nvm, thanks for informing!
Btw, I ended up not solving any problem because of this xD.
How much time does it take to receive Laddus from CodeChef? I got top10 a month ago and I still dont have it.
Keep reminding them through emails.
2-3 months.
Applied the Same Approach as in editorial for PERCAPTA, But getting TLE Please help https://www.codechef.com/viewsolution/34621506
I think it's because of recursive dfs. I did it with while loop and got AC. My submission
I was talking about PERCAPTA problem, not about CHKPTS
Check now
You've applied BFS, whereas I have applied DFS.
Other than that the logic is same
Got Accepted when changed your dfs to my bfs. Recursion works slow and I think if you had changed it to bfs or non-recursive dfs you would get AC.
Yeah, I changed it to BFS and got AC.
But Shouldnt the time complexity of BFS and DFS be the same?
Here is my solution that I have implemented using BFS. https://www.codechef.com/viewsolution/34623172 This got AC.
I implemented the same thing using DFS, but it got TLE. https://www.codechef.com/viewsolution/34621844
Can anyone please explain why? Thanks
I saw your code and I don't think its a dfs problem. You are recursively returning a vector.
In the case where all nodes have max per capita income you will end up returning an ~ n vector from each of the n function calls, which will give you a quadratic complexity.
Your DFS is $$$O(N^2)$$$ because of returning vector with current answer on each step. Just make this function
void
and it should pass, I think.Got AC by making these changes.
Thanks a lot!!
Could you also please help me debug this code https://www.codechef.com/viewsolution/34611118 I have applied BFS here, but still getting TLE.
Thanks!
The bottleneck here is too many operations with
map
which complexity is $$$O(logN)$$$. I replacedmap
withunordered_map
which complexity is amortized constant and got AC.Thanks a lot!
Could you please help. I got AC, here https://www.codechef.com/viewsolution/34623614 but WA https://www.codechef.com/viewsolution/34623659 here. The only difference is the vector sort of the key vector. Can anyone please tell me what is wrong with the second code.
By default
auto
makes copy of elements across iteration. If you need to change content of the container you should useauto&
which makes reference to element, not a copy.Thanks for this contest, it was amazing and it went amazing, I became a 4 star :)
Easter egg: carry bed —> barrycade
In problem Per Capita Income I was getting tle when i used comparator function as
an got AC when i changed >= to >.
Click
Help needed again, I am confused with how the C++ pow function works. I got AC in this https://www.codechef.com/viewsolution/34635562 (line 147) and WA https://www.codechef.com/viewsolution/34626034 (line 142). The difference between the two is only in the respective lines.
The use of pow() implies a cast to double. Double used less than 64 bytes for precission, you get precission loss.
You can instead use self written integer version of pow. Also, there is a good chance of making it work by casting the pow arguments to long double, since that uses more bits for precission, and the long double version of pow().