Блог пользователя plourde27

Автор plourde27, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +62
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Contest link ?

»
4 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Link?

»
4 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

it's 16:00 UTC already!

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Has the contest been postponed?

»
4 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

Thanks for ruining my already ruined valentines day :)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      WA code
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

WA_CODE
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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