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%	224
CCO '20 P2 - Exercise Deadlines	15p	30.0%	300
CCO '20 P3 - Mountains and Valleys	35p	5.2%	26

0

Mamnoon_Siam commented on May 28, 2020, 1:55 a.m. ← edited →

What is the solution for p3 (maybe even $\mathcal{O}(NM)$ ~\mathcal{O}(NM)~)? I could dig up only an $\mathcal{O}(NM^2)$ ~\mathcal{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$ ~2~ if $w_i \geqslant \left \lceil \frac{N}{3} \right \rceil$ and $1$ ~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!

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.