Greetings Codeforces community!
I am sure you have heard that CodeChef is celebrating 10 years of competitive programming!
I would like to invite you to compete in March Cook-Off, sponsored by ShareChat. The Cook-Off is 2.5 hours contest and offers 5 problems for you to try your hand at. And as CodeChef is celebrating its birthday, there are additional prizes up for grabs.
ShareChat- India’s fastest growing social network and sponsor of the contest is seeking talented programmers to join their team. Internships and full-time job opportunities are available for participants of the March Cook-Off. Visit the contest page for more details.
I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:
- Admin: kingofnumbers (Hasan Jaddouh)
- Tester and Editorialist: Pepe.Chess (Hussain Kara Fallah)
- Statement Verifier: Xellos (Jakub Safin)
- Setters: Erfan.aa (Erfan Alimohammadi), AminAnvari (Amin Anvari), Haghani (Ali Haghani), aliams (Ali Mirjahani), mrm_196 (Mohammad Reza Mohseni), farnasirim (Mohammad Nasirifar)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: Team VNOI
- Russian Translator: Mediocrity (Fedor Korobeinikov)
- Bengali Translator: solaimanope (Mohammad Solaiman)
- Hindi Translator: Akash Shrivastava
Contest Details:
- Start Date & Time: 24th March 2019 (2130 hrs) to 25th March 2019 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
- Contest link: https://www.codechef.com/COOK104
- Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
- Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. As CodeChef is celebrating 10 years of cooking, there are additional laddus up for grabs. Know more about the additional prizes here: https://www.codechef.com/COOK104 and about the laddus here: https://www.codechef.com/laddu
(For those who have not yet got their previous winning, please send an email to [email protected])
By the way, happy Nowruz!
Happy programming and have a great new year!
Good Luck!
Happy new year to all Iranians.
happy new year to you happy new year to all iranians we are ready for it
A good contest to kill time in norouz ‘eh?
How to solve CNVX4HUL?
Problem link:
https://www.codechef.com/problems/CNVX4HUL
$$$O(n^3*log(n))$$$ solution:
https://paste.ubuntu.com/p/CHXqfw2k3P/
Can you please explain briefly as well?
Talking about geometry, without using images is not easy, but I try!
Let's assume $$$s_{i, j}$$$ is the number of points inside triangle $$$\triangle(0, i, j)$$$. It's calculated in this solution code, in $$$O(n^3)$$$. Using $$$s_{i, j}$$$ s we can calculate the number of points inside any arbitrary triangle, in $$$O(1)$$$.
Then, we consider three points (like $$$p$$$, $$$q$$$ and $$$r$$$) on our convex hull. Consider a half-line from $$$r$$$ to $$$p$$$, and a half-line from $$$r$$$ to $$$q$$$. The fourth point of our convex hull can be in this subplane, except inside the triangle $$$\triangle(p, q, r)$$$. This subplane is a half-plane subtracted by two triangles (we can handle the subtracted parts by using two-pointers)! For each point located inside this space, some number ($$$2^{something}$$$) will be added to our final answer variable.
Please read the code to understand the solution better.
The problems are great. I suggest all the acm geeks to participate in it.
Can someone explain me the logic of SONGSHOP?? I thought of it as a knapsack problem on sets but could not get AC.
It is knapsack problem only but you have to consider one condition that if you select an album then you can't select the songs of it again. So,you can keep track of that by adding all albums and songs in list and sorting based on album number(keeping album first and all it's songs behind). Now,if you select album then you jump to next album which assures that you haven't selected any of it's songs.
Thanks a lot for your approach. I will try solving...
Problem : MARCAPS
Can anyone tell me at which test case my code gives WA.
Solution Link : 23669122
1
10
1 2 3 5 5 5 5 5 7 8
On this your code displays No.
whereas it should be Yes.
5 5 5 1 2 3 7 8 5 5
MARCAPS and CNVX4HUL tests have been changed for the practice section. Obviously, this don't affect the contest.
Test Case for SONGSHOP are weak too. During contest, I had bug in my code in that problem. After the end of contest, I had to stress test my code with Golovanov399's code and surprisingly found his code fails on following test cases.
2 2 3
2 1 7
2 1 7
3 2
Answer is 14, his code outputs 21
4 4 10
3 8 6
3 1 7
3 8 1
4 1 10
6 9 1 2
Answer is 24, his code outputs 30.
P.S : My code which gets AC on that problem.
Thanks for your feedback. It will be updated for the practice section.
For CNVX4HUL, adding assert(n <= 250) for AC code results in RE.
AC: https://www.codechef.com/viewsolution/23676490
RE: https://www.codechef.com/viewsolution/23676493
Constraints and tests have been changed after the contest for the practice section.