### YouKn0wWho's blog

By YouKn0wWho, 5 days ago,

Hi!

I am thrilled to invite you to participate in CodeChef’s October Cook-Off, this Sunday, October $18$, from 9:30 pm to 12:00 am IST.

Followings are the basic information:

• Participants in each division will be given $6$ problems and $2.5$ hours to solve them.
• All problems have been cooked by me.
• Statements are very short unlike this announcement!
• Problems will have strong samples.
• There will be an interactive problem in this round, so, you should know how to deal with them.
• I hope your internet connection is good as some of the problems will feature awesome animations that I have created using Manim! Yeah, it means the problems will have better explanations.
• In my last contest, only $103$ div2 participants managed to solve div2C which is not good at all. So this time I have tried to maintain a more balanced difficulty distribution.
• I would like to thank cache for his brilliant coordination of this round.
• amnesiac_dusk tasted the problems(I hope they taste sweet!). I want to thank him particularly for helping me with the preparation of a few problems.
• psychik is in charge of the editorials.
• Needless to say, Xellos did the statement improvements.
• Video Editorialists: chirayu, agarwal19,darshancool25, outmanipulate, divesh2201
• Translators: Fedosik [Russian], Team VNOI [Vietnamese], solaimanope [Bengali], devils_code [Hindi], UoA_ZQC [Mandarin]

Prizes: The top $10$ Indian and top $10$ Global participants will receive CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Good luck!

• +140

 » 5 days ago, # |   -10 Clashing with CF Round 676
•  » » 5 days ago, # ^ | ← Rev. 2 →   -14 The blog has been revised, and I look like a fool...
•  » » » 5 days ago, # ^ |   -7 Can't they postpone the round to 19th?
•  » » » » 5 days ago, # ^ |   -16 They should...
•  » » » 5 days ago, # ^ | ← Rev. 2 →   -22 Please postpone the contest if possible.
•  » » 5 days ago, # ^ | ← Rev. 2 →   +104 Trust me I am the one who is more concerned about the clash. I have already discussed it with the CodeChef authority but here is the reason they stated explicitly: It's because we've been having these contests at the same slot for many years, and that predictability is pretty important for the platform. We then wrote to MikeMirzayanov explaining the situation and we are hoping that he'll get back with some good news. He usually takes time to reply to emails, so fingers crossed! That said, in the worst case, we would be having clashing contests
•  » » » 4 days ago, # ^ | ← Rev. 2 →   +97 UPD: MikeMirzayanov has just replied to the email and the div2 contest has been rescheduled. We, as a community, are thanking the CF authority for showing such a great gesture. Hopefully, now you can participate in both contests and enjoy the beauty of them.
 » 4 days ago, # | ← Rev. 2 →   0 CF round is rescheduled, now we can participate in both CC and CF, Thank you Mike
 » 4 days ago, # |   0 finally we can participate in both contest. thank you so much MikeMirzayanov.
 » 4 days ago, # |   0 Auto comment: topic has been updated by YouKn0wWho (previous revision, new revision, compare).
 » 4 days ago, # |   +12 some of the problems will feature awesome animations that I have createdThis is probably the first time a problem statement will have animations to help with the explanation. What a time to be alive!
•  » » 3 days ago, # ^ |   0
•  » » » 3 days ago, # ^ |   0 I think he meant in codechef. Btw, isn't it easy to upload gif in problem statement?
 » 4 days ago, # |   0 Auto comment: topic has been updated by YouKn0wWho (previous revision, new revision, compare).
 » 3 days ago, # |   +5 Are problems sorted by expected difficulty?
•  » » 3 days ago, # ^ |   0 codechef*
•  » » 3 days ago, # ^ |   0 CodeChef_admin, I would still like to know if problems are sorted by difficulty at the very beginning. And is it same for Longs and Lunchtimes too?
•  » » » 3 days ago, # ^ |   +6 At CodeChef, problems are not supposed to be in sorted order. But in this contest, the problems were in sorted order because I like it in this way (Yes, INVERACTIVE was supposed to be easier than XOXO). I didn't see your comment before the round, so couldn't reply to your comment :'(
 » 3 days ago, # |   0 The video editorials to the problems are uploaded on Youtube
•  » » 3 days ago, # ^ |   0 Two hardest div1 problems aren't there yet. Is there a written editorial somewhere?
•  » » » 3 days ago, # ^ |   +8
 » 3 days ago, # |   +1 How to solve C? Great contest though :)
•  » » 3 days ago, # ^ |   0 First, root the tree arbitrarily and calculate for each node its depth. Then, for each node, if its depth is even put a 1 on it. Else, put a 2. I dont have a rigurous proof of why this works, but it's easy to convince yourself once you see it.
•  » » 3 days ago, # ^ |   +1 Just Color the Nodes with 1 if their parent is 2 other wise 1
•  » » 3 days ago, # ^ |   +4 $1-2$ coloring should work.
 » 3 days ago, # |   +8 Thank you for participating! What is favourite problem from the contest?
•  » » 3 days ago, # ^ |   -18 Sir , Editorial published ? or how to solve D ?
•  » » » 3 days ago, # ^ |   +8 Editorials have been published.
•  » » 3 days ago, # ^ | ← Rev. 2 →   +8 I liked An Inveractive Problem the most. Though couldn't solve it even after a lot of submissions.
•  » » 3 days ago, # ^ |   0 I particularly enjoyed solving PATHSUMS, though I didn't fully solve it (mistake in implementation), but all three problems I managed to come up with ideas for seemed very well balanced and interesting. Great round overall, at least for me.
 » 3 days ago, # | ← Rev. 2 →   +35 Screencast with commentary, 2nd place: https://youtu.be/bDoHVOZlqCEEvery problem was nice separately (I especially liked PATHSUMS, INVERACT, MORPH) but there was too much constructive stuff. Div1 was: construct tree, construct sequence, construct sequence, discover sequence, transform sequence, unsolvable problem. The third of these (XOXO) quickly becomes dp problem but everything else was constructive/adhoc, that's just too much.I understand now why antontrygubO_o enjoyed your previous cook-off :D
•  » » 3 days ago, # ^ |   +14 I enjoyed this one too a lot, just was too bad. But amazing round!
 » 3 days ago, # |   +6 How is the checker implemented for DIANE?
•  » » 3 days ago, # ^ |   +12 Checker#include using namespace std; #include "spoj.h" const int N = 1e5 + 9, MX = 1e9; long long MIN(vector a) { long long ans = 0; int n = a.size(); vector l(n), r(n); stack> s1, s2; for (int i = 0; i < n; ++i) { int cnt = 1; while (!s1.empty() && s1.top().first > a[i]){ cnt += s1.top().second; s1.pop(); } s1.push({a[i], cnt}); l[i] = cnt; } for (int i = n - 1; i >= 0; --i) { int cnt = 1; while (!s2.empty() && s2.top().first >= a[i]) { cnt += s2.top().second; s2.pop(); } s2.push({a[i], cnt}); r[i] = cnt; } for (int i = 0; i < n; ++i) { ans += 1LL * a[i] * l[i] * r[i]; } return ans; } vector d[N]; int f[N], last[N]; long long mul[N]; long long GCD(vector a) { int n = a.size(); long long ans = 0; int ok = 1; for (int i = 1; i < n; i++) { if (a[i] == 1 || a[i - 1] == 1 || __gcd(a[i], a[i - 1]) == 1) { } else { ok = 0; break; } } if (ok) { for (int i = 0; i < n; i++) { ans += a[i]; } ans += 1LL * n * (n - 1) / 2; return ans; } memset(f, 0, sizeof f); memset(last, -1, sizeof last); memset(mul, 0, sizeof mul); int M = 0; for (int i = 0; i < n; i++) { M = max(M, a[i]); } for (int i = 0; i < n; i++) { for (auto x: d[a[i]]) { if (last[x] == i - 1) { mul[x] += f[x] + 1; ++f[x]; } else { ++mul[x]; f[x] = 1; } last[x] = i; } } for (int i = M; i >= 1; i--) { for (int j = i + i; j <= M; j += i) { mul[i] -= mul[j]; } ans += mul[i] * i; } return ans; } int main() { spoj_init(); for (int i = 1; i < N; i++) { for (int j = i; j < N; j += i) { d[j].push_back(i); } } int t; fscanf(spoj_p_in, "%d", &t); for (int tt = 1; tt <= t; tt++) { int D; fscanf(spoj_p_in, "%d", &D); int n; spoj_assert(fscanf(spoj_t_out, "%d", &n) == 1); spoj_assert(1 <= n && n <= 100000); vector a(n); for (int i = 0; i < n; i++) { spoj_assert(fscanf(spoj_t_out, "%d", &a[i]) == 1); spoj_assert(1 <= a[i] && a[i] <= 100000); } long long cur = MIN(a) - GCD(a); spoj_assert(cur == D); } char extra[100]; spoj_assert(fscanf(spoj_t_out, "%s", extra) != 1); return 0; } 
•  » » » 3 days ago, # ^ |   0 Thanks.
•  » » » 3 days ago, # ^ |   +8 Can you describe the part of not calculating all gcds and minimum for every subarray naively and getting the accurate answer code seems wonderful but I just need to know the trick used here as it seems a wonderful thing to learn.
•  » » » » 2 days ago, # ^ | ← Rev. 3 →   +3 Sum of all subarray minimums:smash me Sum of all subarray gcds:For each $d$ from $1$ to $M = 10^5$, find the number of subarrays divisible by $d$ and use a sieve-like algo to get the number of subarrays with each gcd. Complexity will be $O(M log\, M)$. To find the number of subarrays divisible by $d$, fix a $d$, then find the non-intersecting ranges $(l_1, r_1), (l_2, r_2), \ldots$ s.t. each element in that range is divisible by $d$ and then compute $\sum{\frac{(r_i - l_i + 1)(r_i - l_i + 2)}{2}}$.For this specific problem almost all of the solutions are smth like $b + 1, b + 2, 1, c + 1, c + 2, 1, \dots$. One property of this array is that every subarray with length greater than $1$ has gcd $1$. So I have initially checked if the array has this property or not; if it has, then it would be faster to compute the sum of the gcds which is $= \frac{N(N-1)}{2} + \sum_{i = 1}^{N}{A_i}$
•  » » » » » 2 days ago, # ^ | ← Rev. 3 →   0 Can you please tell why we are including 1 for every substring like p+2,p+1,1 as p+2,p+1 is also giving same answer YouKn0wWho
•  » » » » » 2 days ago, # ^ |   0 Thank you very much !
 » 2 days ago, # |   0 Can anyone find me a corner case for my solution for problem DIANE?
•  » » 43 hours ago, # ^ |   0 For D=2*10^5-1 the size of your sequence will be 10^5+3 which exceeds the given size limit.