CodeChef October Mega-Cook Off 2018 starts in ~48h, (sunday 21 11:00 PET).
You will have 2.5h to solve 5 puzzles. My last contest was April Cook-off, ussually I only set one contest per year, so this year I broke the curse!
The character of the contest is Chef Ada, she is the most intuitive girl I have ever met. Sometimes she can solve a problem before I finish telling the statement!
Hope you enjoy the problems. See you in the ranklist!
Upd. This time there will be also statements in spanish. Spanish is a complex language, let's hope I didn't miss any accent mark:)
Contest log:
11:08 many WAs in PUMPWAT. MaddyThakker takes the lead in div2.
11:13 MegaBidoof ACed PUMPWAT, even tester had a couple of WAs in this problem
11:24 kingofnumbers frightened me, numbers of equal height in the tests of PUMPWAT? false alarm, only the sample had a repeated element. Actually in the original version there was hills with equal height, but I decided to made the problem easier, and forgot to fix sample input.
11:30 I just noticed zemen is in div2! with two div1 problems solved, he could be first in div1 in this moment.
11:49 user:AlexDmitriev solved PWRTREE, he is still first
12:00 zemen finally solved PWRTREE in div2
12:31 KrK and uwi solving only two problems in a cc contest after 90 minutes? that is not often seen
12:45 riadwaw solved ADASHOP, IMHO it took him too much time, there are no submissions for ADAFARM yet.
12:56 The blue coder (3 stars) zemen :) got perfect score in div2, wondering if he could get perfect score in div1.
13:22 hatter from belarus solved ADASHOP skipping PWRTREE, that was an wise decision, I think PWRTREE is harder. Now he is 4th in div2.
13:27 ADAFARM has only one submission, and unfortunately it is RE (sorry Golovanov399)
13:35 Congrats to the winners!
Div 1.
Div 2.
Is there pasta or pizza?
There’s spaghetti.
There will be 5 delicious dishes (puzzles), and for dessert the editorials and some bonus problems.
Hopefully "mega" won't bring the servers down, like the last time :)
what does "MEGA" means this time?
Auto comment: topic has been updated by Morphy (previous revision, new revision, compare).
Thanks for the PWRTREE task. I really loved it!
Without any spoilers (I'm still planning to upsolve it :) ), does one need to know some facts about tournament graphs or some fancy stuff to solve the power tree task?
No. It has completely elementary solution.
Here is my solution:
First of all the size of PT(X) is 2X. It can be shown pretty easily based on the recursive formula. As a result, if N isn't a power of 2 then the answer is - 1. Otherwise we can always remove edges to get PT(log(N)) using the following method.
Notice, that PT(X) can be constructed by taking two PT(X - 1)-s and connecting their roots. The direction of the edge between the two roots obviously don't matter. Because we have a tournament (complete directed graph) we will always find such an edge between the two roots.
We can construct PT(log(N)) using the following algorithm. Let's have a vector V containing roots of power trees. Initially we will have N PT(0)-s, so V = {1, 2, ..., N}. In each step pair up the elemnts of V and merge the two power trees. We can do this by finding the direction of the edge between the two roots. This will make V contain power trees of degree one higher than previously and the size of V will be halved. Since N is a power of 2 we can make these steps until we are left with only 1 element in V the root of a PT(log(N)). We can store the used edges during the merging, and print out the remaining
edges as the answer.
Here is my code.
What was the intended solution for BINIM2?
Editorial for some of the problems in my blog: https://aleigorithms.wordpress.com/2018/10/19/874/
What is your solution to ADASHOP if you think that it is easier than PWRTREE?
the problem can be reduced to the case when the bishop is on the first column, then is just to find the pattern and count the number of cells of a given color in a triangle. Maybe ADASHOP is longer to code, but PWRTREE required more creativity.
As for me, ADASHOP was both harder to come up with and to implement. Certainly, PWRTREE required an idea, but it was rather straightforward: it's logical that you need to create PT(n) from something smaller, and 2 PT(n — 1)s is natural candidate given the size of PT(n) is 2^n. ADASHOP, on the other hand, required some case analysis and understanding some unusual structure (btw, I actually am not sure why my solution works fine for r = 1, I thought to special case it, but it passed bruteforce)
Of course, problem difficulty is subjective, just my two cents.
What is the general difference between a regular cook-off and a mega one?
Mega CookOff is 10^6 CookOffs source
well, in this context is actually 220 CookOffs
There's a special preifx Mebi- for 2^20 in SI