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 [email protected])
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!!
Auto comment: topic has been updated by ma5termind (previous revision, new revision, compare).
Auto comment: topic has been updated by ma5termind (previous revision, new revision, compare).
Auto comment: topic has been updated by ma5termind (previous revision, new revision, compare).
Contest will be started in less than 30 minutes. Wishing you all good luck and high rating :) :).
5 Minutes guys !! Brace Yourself.
UPD Contest has started safely.
How to solve Chef And Fibonacci Tree problem? My SQRT-decomposition approach fails :( Maybe someone can point out my bug?
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!
Nice, but I am more interested in why my approach fails. Maybe, you can take a look... Editorial uses same idea as I used.
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 ).
Look at my Update function. I propagate all changes
times.
It is typical method. See this link problem "620E — New Year Tree" to understand.
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 :)
Could you show your code?
https://www.codechef.com/viewsolution/9228222
You need to build your F array upto 2*10^5 , not 10^5
stupid mistake! Thanks a lot!
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.
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.
I have used just this approach, but it failed during contest. COuld you kindly help me with finding bug? Link
Thanks!
Nice solution and you coded it very fast :)
Why I don`t get a point for fourth task? https://www.codechef.com/viewsolution/9232579
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 ?
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?
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