2020 Canadian Computing Olympiad - Day 1 Mirror

DMOJ will host mirror contests for the Canadian Computing Olympiad.

This problem set will come from day 1 of the competition. The round will not be rated.

There will be 3 problems to solve in 4 hours. Partial scoring may be available on some problems. The maximum score on a single problem is 25.


Problems

Problem Points AC Rate Users
CCO '20 P1 - A Game with Grundy 10p 20.2% 211
CCO '20 P2 - Exercise Deadlines 15p 29.6% 286
CCO '20 P3 - Mountains and Valleys 35p 5.8% 25

Comments


  • 0
    Mamnoon_Siam  commented on May 28, 2020, 1:55 a.m.

    What is the solution for p3 (maybe even O(nm))? I could dig up only a O(nm^2) solution by iterating over all pairs of bad edges and calculating answer (check every possible ordering of them in my tour) if we use only those edges for teleportation.


    • 1
      FatalEagle  commented on May 28, 2020, 2:11 a.m. edited

      Hint: you only need to consider using 0 or 1 heavy edge.


      • 0
        Mamnoon_Siam  commented on May 28, 2020, 2:29 a.m.

        Aaa... I see... I loosely set an upper bound on #heavy of 2 if w_i \geqslant \left \lceil \frac{N}{3} \right \rceil and 1 if w_i \geqslant \left \lceil \frac{N}{2} \right \rceil during contest.


  • 20
    Tomorrow  commented on May 27, 2020, 11:02 p.m.

    Will there be editorials after the contest?


  • 16
    Xyene  commented on May 27, 2020, 6:02 p.m.

    In order to keep the scoreboard fun for everyone, we ask that you don't participate in this contest if you participated in the official CCO today. Thanks!


  • 2
    Plasmatic  commented on May 27, 2020, 3:36 a.m.

    Can the mirror be windowed?


    • 13
      FatalEagle  commented on May 27, 2020, 4:31 a.m.

      It's not a rated contest so you can just solve the problems at any time after the contest too. We think the benefit of having everyone who can start at the same time discuss the solutions at the same time after the contest will outweigh the benefits of windowing the contest time.