Errichto's blog

CodeChef March Challenge — 10-day contest
By Errichto, 7 years ago, In English

Hello Codeforces!

I'd like to invite you to CodeChef March Challenge that has just started and will last 10 days.

Let's see a colorful bunch of names. Testers: CherryTree and Errichto. Editorialist: pkacprzak. Translators: CherryTree (Russian), Team VNOI (Vietnamese) and huzecong (Mandarin). Language verifier: arjunarul. Contest admin: PraveenDhinwa.

Problem authors are: xennygrimmato, Errichto, PraveenDhinwa, kingofnumbers, Fekete, Alex_2oo8, Ioser.

There is no registration required, anybody with a CodeChef handle can participate. Top participants can win CodeChef laddus (details on the contest page). Unusually, there are extra prizes for top 10 women programmers (irrespective of their ranks) in form of 300 Laddus for the occasion of the International Women's Day. UPD: There is also money prize 400$ for the winner and 300$ for the second place.

You will be provided 10 problems of really various difficulty. While we hope everybody will solve a few simpler problems, we also think that hardest ones will be a challenge for the best. There are 9 problems with subtasks and 1 approximation problem (I personally hope to see a lot of submissions there). We hope you will enjoy the contest and learn something new and valuable.

I wish you great fun and no frustrating bugs. See you in the leaderboard!

EDIT: Updated info about prizes.

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

»
7 years ago, # |
  Vote: I like it +57 Vote: I do not like it

Is there any reason that all 10 questions were added at the beginning of the contest itself, unlike other long contests on CodeChef?

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

    Because the problemsetters for this contest are responsible.

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

    We'll try to make adding problems on time a usual thing.

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

Problemset was interesting. First six tasks are good, also I spent a lot of time to try to solve Sum Distance task, I supposed it is Divide and Conquer solution, but simply I couldn't finish the whole idea :)

Also I enjoyed in Approximate problem. I didn't want to try Interactive task and remaining Tree problem, my goal was finding nice approache for the approximate. Here is my solution (9th overall) :

First I tried to find best placement between each pair of consecutive rows. I run DP in O(N^3) and find best placement of elements for first two rows, then for second and third row ... It gave me 300 lines of code and no more than 18% of points ( now I believe it is around 10% ). After that I realzied I can repeat this process closer to time limit (and from behind too). I do same for the first and third row, than for second and fourth and so on. Eveything was better I got 28%... I didn't see any further optimisation for one-two-three hours of thinking. After one day I started again with problem, forgot everything and tried to invent new solution. Than I found interesting greedy approache :

Very important part is property that all values in the set are distinct. Now I iterate over all elements from 1 to n2 and notice that 1 must be located on beginning of some row, placed on the best possible postion, than 2 must be at the beginning of the some row, or immediately after 1, again find the best possible postion and so on ( over n different postions for each row — normally I tried both increasing and decreasing option for that row). This gave me 40% of final points. Again I stuck what I can do next and than realized two easy steps to make my solution better :

  • Try to itearate from n2 down to 1 and use better matrix

  • Why I can not merge my two codes and for already calculated sorted matrix run DP from the beginning od the comment? And YAY, I got 51% of final score :)

It was funny to solve this task, I wrote 500 lines for the solutions and it was valuable.

At the end I would like to hear some better approaches, someone with better results than me, also if you have idea how to improve my solution tell me :)

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

Thank you for a challenge problem with short statement and with various kind of approaches which makes it much more interesting. A huge increase on numbers of participants attempted the Challenge problem compared to some of the previous contests.

Also, as mentioned in the problem statement:

There are 20 tests. If your program works incorrectly (e.g. it exceeds the time limit or rows aren't sorted) on any of 20 tests, you will get a suitable verdict (e.g. TLE or WA). Otherwise, you will get AC and your score will be decided by only 20% of tests (first 4 tests). The final score will be revealed after the contest.

I am wondering is the current score not finalized and will be rejudged? If so, when will that happen? Thanks a lot.

UPD It is updated :)

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

Can anyone explain why in the FAVGAME editorial answer is dp[0][h] and why not dp[0][0](when starting to process the root why would I have to wait for 'h' hours)?

→ Reply