Hello Codeforces!
On Sunday, February 14, at Feb/14/2021 22:00 (Moscow time), the CodeRams Algorithm Contest #2 will occur. This is the second algorithm contest of the year for the CodeRams, my school coding club. The first one was held in December, problems and results from that contest are found here
The contest will contain 9 problems, and you'll have 3 hours to solve them. The first few problems are fairly easy, designed to be solvable by anyone, while the last few are more difficult. The contest will likely be more interesting for users with a rating of under 2100, but anyone is welcome to participate.
Each problem in the contest has a point value, with harder problems being worth more points. Contestants will be sorted first by their total number of points, and then by their solve times, if there is a tie. Some of the problems will also have subtasks and partial scores.
All of the problems for the contest were created and prepared by me (plourde27).
Thanks to galen_colin, Alx, ScarletS, and eggag32 for testing the contest.
Finally, thanks to MikeMirzayanov for the great Codeforces and Polygon platforms. Being able to hold mashup contests on the Codeforces Gym has been really useful for our club, especially since the start of the COVID-19 quarantine.
UPD1: The score distribution is 6 — 9 — 15 — 23 — 24 — 38 — 42 — 58 — 73. Note that some of these problems will have subtasks and partial scores.
Also, sorry for the mistake with the contest time. The contest time currently listed (19:00 UTC) is the correct time.
UPD2: Thanks to everyone who participated in the contest! Congratulations to the winners:
Maksim1744 (solved all of the problems in under an hour!)
As a tester, I would definitely recommend this contest to Div 2 users, I enjoyed testing this round :)
As a tester, I agree :)
Contest link ?
The link will be added closer to the start of the contest.
Um am I blind or is the link still not up? I see a link to the previous contest but not the current one.
Sorry about that, the link is up now.
Link?
I think 2:00 PM EST and 16:00 UTC are different. He made a mistake.
So, he meant 17:00 UTC.
UPD: 19:00 UTC.
2:00 PM EST = 19:00 UTC
Oh! sorry for the mistake.
it's 16:00 UTC already!
Has the contest been postponed?
Thanks for ruining my already ruined valentines day :)
Auto comment: topic has been updated by plourde27 (previous revision, new revision, compare).
What approach did you guys use to include composite numbers in problem 8?
Fill every room with prime numbers including 1, i.e = [1,2,3,5,7,....]
I did the same but got a wa, can you share your solution so that I can stress test my solution ?
During testing, my code involved using Sieve of Eratosthenes to get the first $$$800 \times 800 = 640000$$$ primes (including $$$1$$$), and building a prefix sum of those. I used DSU to get connected components and their sizes, but this could have been done with a simple dfs instead of course.
Auto comment: topic has been updated by plourde27 (previous revision, new revision, compare).
Can anyone please tell why is this solution failing for problem 8
If you're going to post your code for people to debug, at least have the courtesy to remove all of the excess stuff that isn't needed. I think most people would rather gouge their eyes out than read 300+ lines of code for fun.
Sorry, my bad, I presumed that anyone who attempts to debug this solution will be smart enough to only look at the solve function, but it doesn't seem to be the case.
PS: Thanks, I removed my template and my code passed all test-cases :).
Can you explain this part from editorial for problem 9?
Isn't it just wrong? Like suppose $$$n=1000$$$, so every station can be a hub. And then you add $$$10^5$$$ random subway lines, each with 2 stations. How do you compress that so that the number of edges is $$$2000$$$?
Also, you mention that there is another approach using dfs tree and it is harder. That may be my personal opinion, but I have to disagree with that. I wrote some very unpleasant code during a contest, which did some compressing. But after a contest I realized that it is not needed and the code with dfs is really short: 107373357. What you have to do is find all articulation points such that they split $$$a$$$ and $$$b$$$. You can do this by starting dfs from $$$a$$$ and considering only those vertices who have $$$b$$$ in their subtree.
You're right, the graph will have at most 2000 vertices, not 2000 edges. I updated this in the editorial. Sorry about that. I believe the model solution still runs fast enough even when this is the case, but I'm currently working on verifying this.
The implementation of it might be easier, but I meant that it is harder in the sense that less contestants are likely to know about the dfs tree technique. Sorry if this wasn't clear
The contest is ended. Why CF doesn't allow to see participants code? It will be helpful!