plourde27's blog

By plourde27, history, 4 years ago, In English

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:

  1. Maksim1744 (solved all of the problems in under an hour!)

  2. PurpleCrayon

  3. cjoa

  4. Sir_Shafi_Fan

  5. ujjwalsingh30

Editorial

  • Vote: I like it
  • +62
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

As a tester, I would definitely recommend this contest to Div 2 users, I enjoyed testing this round :)

»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Contest link ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    The link will be added closer to the start of the contest.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Um am I blind or is the link still not up? I see a link to the previous contest but not the current one.

»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Link?

»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

it's 16:00 UTC already!

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Has the contest been postponed?

»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Thanks for ruining my already ruined valentines day :)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by plourde27 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What approach did you guys use to include composite numbers in problem 8?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Fill every room with prime numbers including 1, i.e = [1,2,3,5,7,....]

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did the same but got a wa, can you share your solution so that I can stress test my solution ?

      WA code
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by plourde27 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell why is this solution failing for problem 8

WA_CODE
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :).

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you explain this part from editorial for problem 9?

Now, since there are no more than 1000 hub stations, this graph will only have around 2000 edges, and the brute force approach described above will run fast enough.

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

The contest is ended. Why CF doesn't allow to see participants code? It will be helpful!