Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### Morphy's blog

By Morphy, history, 6 years ago,

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.

• +99

 » 6 years ago, # |   0 Is there pasta or pizza?
•  » » 6 years ago, # ^ | ← Rev. 2 →   -16 There’s spaghetti.
•  » » 6 years ago, # ^ |   +17 There will be 5 delicious dishes (puzzles), and for dessert the editorials and some bonus problems.
 » 6 years ago, # |   +48 Hopefully "mega" won't bring the servers down, like the last time :)
 » 6 years ago, # |   +5 what does "MEGA" means this time?
 » 6 years ago, # |   0 Auto comment: topic has been updated by Morphy (previous revision, new revision, compare).
 » 6 years ago, # |   +18 Thanks for the PWRTREE task. I really loved it!
•  » » 6 years ago, # ^ |   0 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?
•  » » » 6 years ago, # ^ |   +10 No. It has completely elementary solution.
•  » » » » 6 years ago, # ^ |   +16 Here is my solution: SolutionFirst 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.
 » 6 years ago, # |   0 What was the intended solution for BINIM2?
 » 6 years ago, # |   +20 Editorial for some of the problems in my blog: https://aleigorithms.wordpress.com/2018/10/19/874/
 » 6 years ago, # | ← Rev. 3 →   +16 What is your solution to ADASHOP if you think that it is easier than PWRTREE?
•  » » 6 years ago, # ^ |   +8 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.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
 » 6 years ago, # | ← Rev. 2 →   +5 What is the general difference between a regular cook-off and a mega one?
•  » » 6 years ago, # ^ |   +16 Mega CookOff is 10^6 CookOffs source
•  » » » 6 years ago, # ^ |   +16 well, in this context is actually 220 CookOffs
•  » » » » 6 years ago, # ^ |   0 There's a special preifx Mebi- for 2^20 in SI