Hello Codeforces!
CodeDrills will be hosting its first team contest CodeDrills Beta Contest #3 on Sunday, 7th March, 2021 9:00 PM — 10:30 PM IST. There will be 4 or 5 problems to be solved in 1.5 hours.
Contest Details
- Contest Link — https://codedrills.io/contests/beta-contest-3
- Date & Time — 7 Mar 2021, Sunday, 21:00 IST
- Duration — 1.5 Hours
- Will follow standard ICPC scoring system (20 minutes penalty and 1 point per problem)
Registration
You will need to create a team on the contest page in order to participate. Team size can be upto 3. While creating the team, add the registered emails of other users to invite them to join your team. They will get an invite email, ask them to accept. For more details on team registration, refer this guide.
I hope you will enjoy solving the problems.
Hope to see you participating!!!
Thanks everyone for participating. Editorials are out for all the problems. Solutions wont be visible if you are not logged in.
Congratulations to the winners!
1. Unbreakable — Nishant nishant403 Shah, Taranpreet taran_1407 Singh
2. Onyan — Nishank IceKnight1093 Suresh
3. TodoMihnator — Alexandru atodo Todoran
Note:
For practice, users are not able to submit the solutions on contest page, we will fix it.
All problems after the contest will be added to competitive section — https://codedrills.io/competitive. So you can still submit from here.
Attaching all problem links for practice -
1. https://codedrills.io/problems/new-virus-spread
2. https://codedrills.io/problems/stack-of-boxes
3. https://codedrills.io/problems/relics-collection
4. https://codedrills.io/problems/phone-and-chargers
5. https://codedrills.io/problems/expected-empty-chess-squares
Reminder to register for the contest! You wont be able to register after the contest starts hence please register before 9 PM IST.
Reminder: Contest starts in 30 minutes.
How to solve "Expected Empty Chess Squares" problem?
Hi, this was just an extension of this problem — https://cses.fi/problemset/task/1726/ There was some issue with test data. I have fixed test data for now. Expected a matrix expo to pass. Our TL was too tight. I have increased it for now to pass matrix expo solutions.
What is the logic behind this?
Simulation! Author tried simulating with increasing $$$k$$$ values for same $$$n$$$ and found out that, after a bound, expected value doesn't change.
Hi, Can you allow other participants to submit the code just for practice?
Problems are now public. You can submit your solution on contest page. If that's not working then search the problem under competitive section and you should be able to submit your solution.
Can you please release the editorials or make the submissions public?
In Expected Empty chess squares, would O((N*N)^3logK) pass TL ?
Can someone share their code for "Relics Collection" ?
It's DP
For each
idx
, you can jump froma[idx]
to anywhere betweena[idx+k]
which is max 50 interation.and let
dp[i][k]
= minimum time if u start at i and have k jumps leftoverall solution works in $$$O(N*K*K)$$$
Yes, I did the same but got a WA so just wanted to stress-test my solution against an AC code, would you mind sharing it?
Sure, but it looks like i am unable to see my solution for some reason.. :(
i can't even see scoreboard.
Talking about the experience
i think the judge was a bit slow, even with such low participation. The website looked stable tho.
I was unable to view my teammate code
There was no sample output for
Phone and Chargers
If possible label problems with index based on difficulty.
Hi Makise_Kurisu, editorial have the setter iterative $$$O(n*k*k)$$$ solution. And in tester solutions, i have added my 3 solutions, $$$O(n*k*k)$$$ both iterative & recursive dp. Also $$$O(n*n*k)$$$ recursive dp. We intended to pass only $$$O(n*k*k)$$$.
But editorial is not visible yet.
Thanks for replying but for some reason I'm not able to access the editorial as of now.
Oh seems weird! I've added the solution without solution tag. Now it should be visible at the end of editorial.
Now it's accessible, thanks!!
But we always start from $$$(0,0)$$$, so how is this DP state correct?
add (0,0) to the list of coordinates in front
That means, our answer is dp[0][k]?
answer is minimum cost to reach till end, if you doing it with recursion the recursive function itself will return the answer.
so it will $$$min(dp[0][0],dp[0][1],.......dp[0][k])$$$ where you are jumping from $$$0$$$-th position to somewhere with some $$$x(<=k)$$$ skips.
But, if our state is minimum time required if we start from $$$i^{th}$$$ position with $$$k$$$ skips left, the answer has to be $$$dp[0][k]$$$.
I tried the same and got Correct Answer later.
then in that case you must be updating dp values with the previous one, isn't it?
Yes.
We have rejudged "Expected Empty Chess Squares" problem as it had some test issues and 1 wrong submission has now got accepted. Apologies for the mistake.
how to solve Phone and Chargers ?
can anyone share there code
Code is quite self-explanatory, though feel free to ping me if you don't get anything.
Please check the editorial at https://codedrills.io/contests/beta-contest-3/problems/phone-and-chargers. If any quieris feel free to ask on https://discuss.codedrills.io/t/codedrills-beta-contest-3-team-contest-announcement/50/4