Morphy's blog

CodeChef June Cook-Off invitation
By Morphy, history, 7 years ago, In English

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.

  • Vote: I like it
  • +38
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is Cook off hard for Div 2 guy ? I participated in a long contest and it wasn't hard .

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Difficulty is relative, I did cook-offs when I was in div2. I think you will have fun solving the problems

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      okay I am expecting a very interesting contest just like your previous contest

      → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

"A yellow-stuffed contest" :)

I think you will all enjoy the problems, good luck!

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve A Study in Bake Street?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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]).

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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:

        4
0 30
5 10
10 5
20 40

        Convex hull up to the first point won't even include the third one and the answer will be wrong.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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" ?

→ Reply
»
7 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +60 Vote: I do not like it

      injured? is cook-off that dangerous?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        Google translate, I have a very poor english

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      i don't think they have ever made contest unrated for anyone specifically , though the damage wasn't much since the contest got extended.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Chess problem ?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it
  • Announce event as a major event on all websites.
  • Randomly put wrong test data in one question.
  • Let participants play Hide and Seek for knowing whether their submission AC or not.
  • PROFIT!
  • Further
  • Wait almost till end of the round to announce that its extended.
  • During this period let the homepage indicate that the contest has peacefully ended. :)
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Terrible.. rejudged after full AC, I did not notice my submission failed for a while.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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 ?

→ Reply
»
7 years ago, # |
  Vote: I like it -15 Vote: I do not like it

A greedy solution for KNICOV was up here: https://math.stackexchange.com/questions/1109512/minimum-number-of-knights-so-that-every-cell-is-attacked

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please elaborate more upon CENTREE

also, how n=2,b=0 gives us 'NO'

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply