ma5termind's blog

Invitation to CodeChef January Cook-Off 2016!
By ma5termind, history, 9 years ago, In English

Hello CodeForces Community,

I have set the problems for CodeChef January Cook-Off and would like to invite you all for the same, the contest will take place at https://www.codechef.com/COOK66. There are some really interesting set of problems, hope you enjoy solving them. Please give your feedback on the problem set in the comments after the contest. You may find the rest of the details about the contest below.

Time: 24th January 2016 (2130 hrs) to 25th January 2016 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/COOK66

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

  • Problem Setter: ma5termind (Sunny Aggarwal)
  • Editorialist: pushkarmishra (Pushkar Mishra)
  • Problem Tester & Russian Translator: Antoniuk (Vasya Antoniuk)
  • Mandarin Translator:: gediiiiiii (Gedi Zheng)
  • Contest Admin: PraveenDhinwa (Praveen Dhinwa)
  • Vietnamese Translator: VNOI Team
  • Language Verifier: rarora7777 (Rahul Arora)

Prizes:

  • Top 10 performers in Global and Indian category will win a cool CodeChef T-shirt. (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

I promise all of you to deliver an interesting set of problems with something for all and you can witness this by participating.

Detail editorials will be available right after the contest.

Good Luck & Have Fun !!! Hope to see you participating!!

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ma5termind (previous revision, new revision, compare).

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

Auto comment: topic has been updated by ma5termind (previous revision, new revision, compare).

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

Auto comment: topic has been updated by ma5termind (previous revision, new revision, compare).

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

Contest will be started in less than 30 minutes. Wishing you all good luck and high rating :) :).

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

5 Minutes guys !! Brace Yourself.

UPD Contest has started safely.

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

How to solve Chef And Fibonacci Tree problem? My SQRT-decomposition approach fails :( Maybe someone can point out my bug?

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

    We consider matrix A (2 * 2) = {{1, 1}, {1, 0}}. As we know Fn equals to entry (1, 0) of matrix A^n. So, we asign each node x with a matrix A^[lev[x]]. When update, we just add matrix A^(k-lev[x]) to all children of node x. The remain task is simple, using segmenttree with propagation!

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

      Nice, but I am more interested in why my approach fails. Maybe, you can take a look... Editorial uses same idea as I used.

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

      I don't understand you solution very well ( honestly I haven't thought about it a lot ), but it isn't clear how you add A^(k-lev[x]) to all children ( it is possible to have n-1 children ).

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

        Look at my Update function. I propagate all changes times.

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

        It is typical method. See this link problem "620E — New Year Tree" to understand.

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

          I tested and suggested that task for educational round, so I know solution for it :D This task was harder I think, but I see similarity in approaches :)

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

      Could you show your code?

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

    You need to build your F array upto 2*10^5 , not 10^5

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

Good problemset ! As always I was near to solve one more task ( in my case task with sum ), but I didn't manage to do it :(

I am interested about solution for tree problem, I suppose it is something like HLD, but I don't know.

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

    One solution has been mentioned above already.

    Another possible approach: SQRT-decomposition. Store all updates which you have, for every query take result which you have in a tree plus results from all stored updates (update will affect our vertex if and only if it is ancestor of our vertex); once your updates list grows too big — apply all updates and recalculate values for all vertices with a single dfs.

    Upd. And here is an editorial.

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

      I have used just this approach, but it failed during contest. COuld you kindly help me with finding bug? Link

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

      Thanks!

      Nice solution and you coded it very fast :)

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

Why I don`t get a point for fourth task? https://www.codechef.com/viewsolution/9232579

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

Also I wish to ask about task with Maximum sum. Maybe I made mistake in my approache, but maximum sum worked for several testcases, only I had problem with number of such matrix.

My approache :

n-dimensional submatrix is equal with using one substring from each of n arrays. Now we need to find the biggest sum. We will use two 3D dp matrix DP[i][j][k] — maximum sum of submatrix made by arrays from 1 to i and used elements from j to k in the i-th array and DP1[i][j][K] — minimum sum of submatrix with array from 1 to i and from the last array we used elements j,j+1,...,k. We can calculate that conditions easily with known previous conditions.

Total complexity O(n^5).

Whether my approache correct ?

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

I felt that the problemset was a bit too skewed. The 2nd problem was solved by 380, and the 3rd by 27 shows that the level difference is too steep. Also, the 4th question was solved by 20 people. Shouldn't a contest be such that the problems are more balanced out?

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

    I feel Unless codechef has 2 divisions it can never satisfy the whole community...

    I solved 2 problems in half an hour... Thought for the 3rd for 45 minutes and then I watched TV... No need of 2.5 hourd for me atleast... And this haplens mostly unlike Codeforces where I need speed too :D

    → Reply