Hello Codeforces!
I’d like to invite you to CodeChef June Cook-Off that will start at 21:30 IST of 18th June 2017 (check your time zone here). There will be 5 problems and it will last 2.5 hours.
This is my second Cook-off, my previous round was on august 2016 — at this rate my rounds are going to be called Alei yearly contests!
- Problem Setter: Alei Reyes Morphy
- Primary Tester and editorialist: Hussain Kara Fallah Pepe.Chess
- Secondary Tester: Kacper Walentynowicz kpw29
- Mandarin Translator: Hu Zecong huzecong
- Vietnamese Translator: Team VNOI
- Russian Translator : Sergey Kulik CherryTree
No registration is required, anybody with a CodeChef handle can participate.
Hope you enjoy the puzzles!
UPD. I'm really sorry for the inconvenient with problem KNICOV. Testers also arrived to the same greedy solution and I was overconfident since it was an easy problem.
UPD. Hints, comments, solutions
ADACRA: Group Us and Ds in blocks, what happens with the number of blocks after performing one operation?
SNACKUP: I came up with this problem while doing research on the double cycle cover conjecture. The problem is about finding a set of cycles such that every edge is in exactly two cycles.
CENTREE
KNICOV: This was expected to be the easiest problem of the round, I underestimated it and now you can see the consequences.
For n=2 the answer is
..**.. ..**.. ..**..
..**.. ..**.. ..**..
For n=3 I thought that the same patterns produce the correct answer but it turns out that fewer knights are required. I had a proof, but it was incorrect :(
I missed the dp solution which is the bulletproof
ADADET: ~10 minutes before the round I generated new test data, but solutions of testers didn't match! I got very nervous, it turns out that I was comparing files with diff and the testers output were in differente format (spaces, line breaks). Hint: Think in the structure of the convex hulls.
Is Cook off hard for Div 2 guy ? I participated in a long contest and it wasn't hard .
Difficulty is relative, I did cook-offs when I was in div2. I think you will have fun solving the problems
okay I am expecting a very interesting contest just like your previous contest
"A yellow-stuffed contest" :)
I think you will all enjoy the problems, good luck!
How to solve A Study in Bake Street?
you basically have to maintain a upper convex hull going downwards while going from N to 1
notice that if you have the convex hull maintained for an interval [a..b] , then it can be extended to [a-1,b] or [a,b+1] easily if its stored in a deque , so sort the values according to height and keep a dsu and do small to large merging to merge deques.
Why does solution like this fail?
Let's process the buildings in reverse order and maintain convex hull of used buildings. Then find the last building to shoot with binary search. If ch[mid] is to the left from the point with maximum y value in convex hull then just check if a[i].y > ch[mid].y, otherwise check if the angle to ch[mid] is smaller then the angle to ch[mid + 1] (the point to the right from ch[mid + 1]).
Damn, it's hard to be blue! Why am I being downvoted to oblivion?
I guess it's obvious why my approach is wrong. Like on this case:
Convex hull up to the first point won't even include the third one and the answer will be wrong.
My submission for KNICOV become WA from AC by rejudge.
Does the announcement "Problem KNICOV had wrong testdata." mean "Judge's solution was wrong." ? or "We added testcases" ?
how is it that a lot of cookoff's have wrong testdata initially :/
i submitted the knights problem initially and then got WA and spent a lot of time trying to find a bug and couldn't and at about 1.8 hours into the contest i see that it became AC after a rejudge.
Same thing, do you know if they can make the contest unrated for who was injured due to issue? I made a comment asking to admin during the contest, but I had no response until now.
injured? is cook-off that dangerous?
Google translate, I have a very poor english
i don't think they have ever made contest unrated for anyone specifically , though the damage wasn't much since the contest got extended.
How to solve Chess problem ?
Any ideas to approach Knight Covering?
I did some cases on paper for n=2 and n=3 to find a pattern, but was unable to do so.
dp(mask of 2nd last column , mask of last column , mask of current column , mask of next column , column), to calculate try all masks for the current column , complexity is 25 * n * M.
Could you elaborate on how the transitions are made?
Terrible.. rejudged after full AC, I did not notice my submission failed for a while.
I tried to find pattern in KNICOV and submitted this solution but I kept getting wa Can anyone help me by giving counter case where my solution fails ??
UPD I didnt saw the updated blog, I also found the same pattern for n = 2, and for n = 3 I thought if m is greater than 4 than we can put all the knights at the middle row and thus covering all the cells, I thought it might be correct bcoz each knight can atmost cover 5 cells so by these position its doing same. Am I missing something ?
should be 4
A greedy solution for KNICOV was up here: https://math.stackexchange.com/questions/1109512/minimum-number-of-knights-so-that-every-cell-is-attacked
can someone please elaborate more upon CENTREE
also, how n=2,b=0 gives us 'NO'
In that case, both vertices are both center and centroid. We are asked to take maximum among all possible pairs, hence the beauty should be 1.
Even my correct solution was then wrong. I couldn't figure out what was wrong in the pattern in the contest, since I had written a bruteforce which was giving correct values for small values of n,m.
The test data initially had wrong answers for the cases, (3,14) , (3,20), (3,26) ,... , (3,146) . In these cases, the initial answer was one more than the correct answer.
Initial AC solution: Code
Final AC solution: Code