Mackenzie New Year's Challenge '17
Welcome to the Mackenzie New Year's Challenge. This contest will take place from January 7th at 12:00pm to January 8th midnight.
You will have a total of 36 hours to attempt the problems. This round is unrated. There are 6 problems in approximately increasing difficulty, varying from CCC Senior to CCO difficulty. Full test data is used, meaning no systests. The score you see is the score you have. The problem setters for this round are and .
All problems are guaranteed to be solvable in C++.
Tips for this contest
- Take your time. You have 36 hours. That's more than enough time to partake in the challenge. Although you may not be coding during the whole time, if you read the problems, you'll be thinking about them subconsciously.
- Read the problems carefully. Misreading questions can lead to a lot of frustration and time wasted on debugging.
- Read all the problems. They may not be as hard as they seem.
- Attempt all the problems. You may get partial points! Some subtasks may not be as hard as they seem.
- Feel free to learn and search things up while trying to solve a problem, this challenge is meant as an educational experience to improve your programming for 2017!
- Have fun! Don't fret about how you do on this contest, (it's not rated) just have fun. Feel good about every single point that you get.
Introduction to DMOJ for New Users
DMOJ is an online judge, meaning that you can submit your code for a problem and the servers will run it! Magic, right? It will give you feedback on how your program did. Use standard I/O. (For Turing, use get and put, no file I/O needed; for Java, use System.in and System.out). See here for more details.
Sample A + B program in Turing.
Given integers and
, find the sum of
and
.
var A, B : int
get A, B
put A + BSee, no file I/O needed! It's as easy as the code above.
To participate in the challenge, just login or register if you don't have an account. Once you've entered the contest, click the Problems tab at the top to access the problems.
GOOD LUCK AND HAPPY HOLIDAYS!
Problems
| Problem | Points | AC Rate | Users |
|---|---|---|---|
| MNYC '17: 2048 | 5 | 29.4% | 83 |
| MNYC '17: ASCII Art II | 5 | 42.4% | 62 |
| MNYC '17: Hurontario | 10p | 14.1% | 264 |
| MNYC '17: Removing Christmas Trees | 15p | 21.4% | 50 |
| MNYC '17: Skiing Competition | 15p | 4.4% | 7 |
| MNYC '17: Bells | 17p | 18.4% | 64 |
Comments
I spent a long time trying to figure out P5. I don't know how to find the path lengths from shortest to longest and keep track of the nodes in each path at the same time. Hope I could get some hints.
No official editorials will be provided. I'll provide the P5 editorial here.
SPOILER ALERT
The problem is finding the kth shortest path, with the extra query of shortest edge.
There are a few algorithms for this on wikipedia, such as Yen's algorithm. Up to you if you want to use it
I used SPFA (I think?) to solve this. Basically, running priority queue Dijkstra's until the maximum query has been answered. The magic of SPFA is that you keep on finding solutions; store these in an array. To make sure that they don't revisit a node, store visited nodes in a bitset (or boolean array). There is no "dist" array involved unlike in artskjid.
This solution has a best case complexity of Dijkstra's and a worst case complexity of searching all the possible paths.
I will spend some time and learn the algorithm you suggested. I used SPFA too. After reading your response I thought of creating another array to store the shortest edge, then I could find the shortest path and the shortest edge.(so only works for the subtasks that ask for Q=k=1) and it worked! (though only for batch 3, I guess that's the simplest) Thank you >w<