Greetings Codeforces community!
CodeChef presents the April Lunchtime sponsored by ShareChat. This is a 3-hour contest designed for school students, but all programmers are welcome to participate. Don’t forget that our problems are available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.
ShareChat — India’s fastest growing social network is seeking both interns and full-time employees to join their dynamic team. Job opportunities are open to programmers across the world and internship opportunities are exclusively aimed at final year B.Tech students who have already been placed and looking forward to gaining startup experience. Don’t forget that you must participate in the contest to be eligible for internships and full-time jobs. 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:
- Setters: kingofnumbers (Hasan Jaddouh), Farhod (Farhod Khakimiyon), Kerim.K (Kerim Kochekov)
- Tester: RedNextCentury (Joud Zouzou)
- Editorialist: taran_1407 (Taranpreet Singh)
- Statement Verifier: Xellos (Jakub Safin)
- 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: 27th April 2019 (1930 hrs) to 27th April 2019 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
Contest link: https://www.codechef.com/LTIME71
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 Indian and top 10 Global school students from rank list will receive certificates and CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/t/how-do-i-win-a-codechef-goodie/7344. (For those who have not yet got their previous winning, please send an email to [email protected])
Winners of contest:
Division 1:
1) isaf27
2) uwi
3) Amoo_Safar
Division 2:
1) almogwald
2) repeating
3) ihdignite
Good Luck!
Hope to see you participating!!
Happy Programming!!
RedNextCentury is Joud Zouzou :p
Fixed :)
Can you change the timings ? Codejam is also at the same time
Isn't that tomorrow?
Sorry I got confused :P
What was the intended solution for CHEFRAMI ? I tried O(N^2) DP which passed subtask but gave TLE (and sometimes WA) on the 2 large tests.
My solution was dp[i] denotes minimum cost for cooking first i meals with stacking some of them in i. You can check the code: https://www.codechef.com/viewsolution/24106582
Can you explain why doing this is optimal?
mulsum[i][j] denotes the cost of stacking all numbers from i to j in position i. The naive coding of the line you mentioned would be:
So we optimize this with mulsum because for all k from j to (i+j)/2 that minimum function returns k-j and analogously we can say the other one.
That was smart, thanks :)
I have next solution :
$$$DP[{i,j}]$$$ — minimum amount of energy to finish first $$$i$$$ groups and last group is finished at place $$$j$$$. There is just two different option for $$$i$$$-th group:
$$$1$$$. it is first group finished at place $$$j$$$ — $$$DP[{i,j}]$$$ = $$$Best[i-1]$$$ + $$$X$$$ + $$$ENG[{i,j}]$$$.
$$$2$$$. it is not first group finished at place $$$j$$$ — $$$DP[{i,j}]$$$ = $$$DP[{i-1,j}]$$$ + $$$ENG[{i,j}]$$$
Where $$$ENG[{i, j}]$$$ is amount of energy to move all meals from place $$$i$$$ to place $$$j$$$ and $$$Best[i]$$$, optimal solution for first $$$i-1$$$ groups.
You must be careful with $$$A_i=0$$$. Total complexity $$$O(N^2)$$$ per testcase.
Try to open formula
$$$\frac{a*b}{M} = a+b$$$
$$$a*b = M(a+b)$$$
$$$a*b-M(a+b) = 0$$$
$$$a*b-Ma-Mb+M^2 = M^2$$$
$$$(a-M)*(b-M) = M^2$$$
So you have to consider all divisors of $$$M^2$$$
Bonjour! code link please?
Here it is: https://ideone.com/FM3DKv
Similar idea:
Using the condition $$$A\le B$$$ gives $$$X \le M$$$.
Finding divisors ($$$X$$$'s) of $$$M^2$$$ in the range $$$[1,M]$$$ is easy.
The problem was also solvable by using OEIS. I bruted the answer for $$$n = 1$$$ to $$$20$$$. Then put the sequence in OEIS. This is what I got: https://oeis.org/A018892. The last comment reads: $$$a(n)$$$ is the number of divisors of $$$n^2$$$ that are $$$\le n$$$. I compared that against the answer for small $$$n$$$ and it differed only by $$$n$$$. So, finally, I had to only add $$$n$$$ to the divisors of $$$n^2$$$ that are $$$\le n$$$.
How to solve The Last Droid?