### Ashishgup's blog

By Ashishgup, history, 4 months ago,

We invite you to participate in CodeChef’s January Cookoff, today — 23rd January from 8:00 PM — 10:30 PM IST.

The contest will be 2.5 hours long. There will be 7 problems in Div 1/2 and 8 problems in Div 3. It will be rated for all three Divisions.

Joining us on the problem setting panel are:

Problem Submission: If you have original problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Prizes:

• The top 10 Global Division 1 users will get \$100 each.
• The top 100 Indian Division 1 will get Amazon Vouchers worth Rs. 1500 each.

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.

Good luck and have fun!

• +146

 » 4 months ago, # |   0 Servers down again?
 » 4 months ago, # |   -19 Codechef sux
 » 4 months ago, # |   +2 Submission page not loading :(
•  » » 4 months ago, # ^ |   0 Please try hard refreshing. (Ctrl + Shift + R)
•  » » » 4 months ago, # ^ |   +8 This is so unfair, you should have made an announcement
•  » » » » 4 months ago, # ^ |   0 Try switch to non ide mode
 » 4 months ago, # |   +13 Submission page not working for me!
•  » » 4 months ago, # ^ |   +14 How come this is not working for only me and working for others?
•  » » » 4 months ago, # ^ |   +1 It seems I am the only one not able to see ranklist:(
•  » » » 4 months ago, # ^ |   0 from about 8:10 to 8:20 whole site wasnt working for me
 » 4 months ago, # |   0 Codechef is not working for me
 » 4 months ago, # |   +4 How to solve ERASE? I doubt it is DSU, but I wasn't able to implement it correctly :')And loved the problems MERGEDLIS and PRIMEGRAPH. SEGDIV was rather a puzzle problem, but it was also good, except the position.
•  » » 4 months ago, # ^ |   +17 Direction of thinking is already right for you I guess. Maybe you just want to keep connected components and want to check if there is one component or more than 1 at the end. However, I didn't find how to achieve it using DSU. But, here's a way I found..let's iterate on permutation array from end and somehow maintain components . Now how can cur element help us. If there are two connected components to the right side, and both have at least one element larger than cur, then those two components can be connected. If we repeat this process, all the connected components which have at least 1 element greater than cur, can now combine. How do we maintain these components and combine operation ? SpoilerSTACK !! Since we only need the largest element of a connected component, we will keep in stack the largest element of connected component. How will we combine ?Delete all elements from stack which are larger than us, except THE LARGEST!Code
•  » » 4 months ago, # ^ | ← Rev. 2 →   +3 Yeah the idea is finding number of components. To avoid actually creating the graph, you can show that if the graph has $k$ components, each component must be a subarray. So, letting [i] denote the ith component, the array is like [1] [2] ... [k], where [1]>[2]>...>[k]. (By [1]>[2] I mean all elements in component 1 are greater than all elements in component 2.) Consider the first component, say it ends at index i, then $min_{1...i} > max_{i+1...n}$. This condition is necessary and sufficient, so you can just check it every $i$.
•  » » » 4 months ago, # ^ |   0 You mean to say $<$ instead of $>$, right? Because, then only the components can be merged.Thanks, it was a nice problem too!
•  » » 4 months ago, # ^ |   +3 You can go through each number and maintain some current minimum mn (initially it is a[0]) and a vector consisting of decreasing numbers to delete.Suppose that you are at a[i] now:if a[i] < mn -> add mn to the vector of erasable elements and set mn := a[i];otherwise, remove the vector elements (x) from the back while x < a[i], and after that, remove a[i] using mn;Finally, the answer is YES if and only if the vector is empty.
•  » » 4 months ago, # ^ |   +12 The DSU approach is very interesting. It didn't even remotely come to my mind during this whole time. There hasn't been any official editorial published for this problem yet. But here's the draft solution I submitted when proposing the problem.The answer is YES if and only if there is no suffix, other than the whole array, of length $L$ ($1 \le L < N$) that consists of the smallest $L$ elements.Proof of the only-if part: Let the suffix in consideration be $A[i \dots N]$. Then since all the elements in the prefix $A[1 \dots (i - 1)]$ are greater than all the elements in the suffix, we won't be able to do any operations in-between this prefix and the suffix. Thus at-least two elements must remain at the end of all the operations (one from the prefix and one from the suffix), a contradiction.Proof of the if part: We can prove the claim using induction. The case when $N = 1$ and $N = 2$ are trivial. So let's assume that $N \ge 3$. We'll show that we can remove an element from the array with a valid operation, such that the property that no suffix of length $L$ contains the smallest $L$ numbers, still holds. Let $A_i$ be the maximum number in the array and $A_j$ be the second maximum. We consider two cases,Case 1: If $i < j$, then removing $A_i$ from the array doesn't break the property. The operation to remove $A_i$ consists of $A_i$ and the element right before it ($A_i$ cannot be the first element, otherwise the property wouldn't hold)Case 2: If $i > j$, then removing $A_j$ from the array doesn't break the property. The operation to remove $A_j$ simply consists of $A_j$ and $A_i$.Implementation ideas: Since the array is guaranteed to be a permutation, checking each of the suffix-sums to see if they consist of the smallest natural numbers is enough. In other words, for a suffix of size $L$, we check if the suffix sum equals $\dfrac{L \cdot (L + 1)}{2}$.Complexity: $\mathcal{O}(N)$
 » 4 months ago, # |   0 why is ranklist not visible?
 » 4 months ago, # | ← Rev. 2 →   +87 Feedback on the problem set: Merged LIS: Not particularly interesting; for me it is as interesting as asking to compute the LIS of a sequence. Subsegment Divisibility: Very cool easy problem. I guessed that the constraints are not hard to satisfy with a greedy and implemented it. Maybe there is a provable solution for all $n$, but I don't care and I actually think that the problem is cooler if there is not. Prime Graph: Boring problem. In general, a problem which mentions prime numbers but its solution uses only that most prime numbers are odd is not particularly interesting. Erase All But One: Nice problem. I have the vague feeling that this appeared somewhere else, but I am not sure. After first reading it, it reminded me of 1375C - Element Extermination, but the solution is completely different. Boring Trip: Standard problem with medium difficulty. I enjoyed coding it to relax the mind before the next one. Beautiful Permutation: Amazing problem. This was a pleasure to solve and I am proud of myself for solving it. My solution uses generating functions with two variables and obtains a closed formula (involving Stirling numbers of the first kind) for the answer. Since I really like my solution, if it does not coincide with the one described in the editorial I might post it later. I really enjoyed Beautiful Permutation and therefore I really enjoyed the contest (even though I started competing half an hour late because I saw the announcement late), thanks to the authors.
•  » » 4 months ago, # ^ | ← Rev. 3 →   +13 It is funny that I wrongly bruteforced then produced Stirling numbers of the second kind.Beautiful Permutation: It is easily oeis-able, I believe lol.
•  » » » 4 months ago, # ^ |   +5 Yeah, Beautiful Permutaion is oeis-able, I just searched 40, 200, 280, 160
•  » » 4 months ago, # ^ |   +1 I came up with a solution which works for any N for Subsegment Divisibility, basically we can output 4 * i + (i%2).
•  » » 4 months ago, # ^ |   +21 About Erase All But One: This problem did actually originate from the problem you linked (the sample explanation section should make it obvious, I tried to keep the new statement similar to that one to respect the original problem). I missed the most important constraint in that problem when solving it, and coincidentally found the new version quite interesting too. Glad you liked the problem :)
•  » » 4 months ago, # ^ |   +7 I found it interesting that the first four problems all had simplistic solutions, although participants could get lost trying complicated ideas.Boring trip was somewhat standard as you say, it has lesser submissions than I would expect.Beautiful Permutation: I took the longest for this one, was thinking about two variable generating functions, etc. for long time. I saw that quite a few participants had solved this very quickly so looked for something simpler.Later realized that answer could be derived from number of permutations in $n$ having $k$ records, and multiplying by $2^k$. This coupled with the fact that the probability of the $i$th number being a record in a permutation is $1/i$ independently of the other probabilities led to Stirling numbers of the first kind. I think this probabilistic reasoning would be much simpler than derivation from two variable generating functions.Overall I enjoyed the contest.
•  » » » 4 months ago, # ^ |   +37 There is actually bijection between number of prefix max and number of cycles in permutation. Hence that leads to Stirling number of first kind.
•  » » » » 4 months ago, # ^ |   0 Aha right, you can use each record and all elements till the next record, in that order, to form a cycle.
•  » » » 4 months ago, # ^ |   +14 How is Boring Trip a standard problem? Can you please elaborate? At first glance, it looks like TSP to me. Can't think of anything else. Can you give some hints about the idea to be used?
•  » » » » 4 months ago, # ^ |   +5 You can think on how will we arrange a fixed set of attractives (the sum of S is fixed, so only coordinates matters now). The first test in example is probably a big hint.
•  » » » » » 4 months ago, # ^ |   0 Thanks for the hint, Yeah the first sample test case helped a lot.
•  » » » » » 4 months ago, # ^ | ← Rev. 3 →   0 The problem would have been easier if k was odd, in that case, we just have to choose (k+1)/2 points on the right side which maximizes 2*disfrom middle point + s, and similarly for the left side. But if k is even, then the nearest point to the middle point will be traversed only once and the rest of the points will be traversed twice. I don't know how to handle this. Can someone please help as the editorial is also not published yet?
•  » » » » » » 4 months ago, # ^ |   0 Actually it is easier when k is even. I think you get even and odd mixed up?
•  » » » » » » » 4 months ago, # ^ |   0 For example, if we take the sample test case, the middle point (or starting point) is having x=3, now I am telling the answer will be a summation of 2*dis + s, for all points except one which is just to right of it having x=5: (2*(6-3)+4) + (2*(3-1)+7) + (1*(5-3)+7) = 10 + 11 + 9 = 30 Finally add the s value of the middle point, i.e., 9 to get the final answer. If k would have been odd, then each point will have 2*dis+s, and it would have been easier to handle as in this case we could have kept two multisets for left and right separately and then iterate for the middle point and update the two multisets as we shift the middle point.
•  » » » » » » » » 4 months ago, # ^ |   0 I see. Even solution is pretty similar. How would you solve a task- the maximum non overlapping (prefix sum + suffix sum) of an array?
•  » » » » » » » » 4 months ago, # ^ | ← Rev. 4 →   0 I have solved using this approach, hope it helps you in the implementation part. Although the code is quite long :( Code#include // #pragma GCC optimize("Ofast") // #pragma GCC target("avx,avx2,fma") // #pragma GCC optimization("unroll-loops") // #pragma GCC optimize("unroll-loops") // #pragma GCC optimize("fast-math") // #pragma GCC optimize("no-stack-protector") // #define ll __int128 #define ll long long // #define ll int #define f(i,a,b) for(int i=a;i=b;i--) #define sc(a) scanf("%lld",&a) #define pf printf #define sz(a) (int)(a.size()) #define psf push_front #define ppf pop_front #define ppb pop_back #define pb push_back #define pq priority_queue #define all(s) s.begin(),s.end() #define sp(a) setprecision(a) #define rz resize #define ld long double #define inf (ll)1e18 #define ub upper_bound #define lb lower_bound #define bs binary_search #define eb emplace_back const double pi = acos(-1); ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;} ll binpow(ll a, ll b, ll md){ll res=1;a%=md;if(a==0)return 0;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;} using namespace std; struct node { ll val,lazy,index; node() { val=inf,lazy=0,index=0; } }; vector t; node merge(node a, node b) { node ans; if(a.val<=b.val) ans.val=a.val,ans.index=a.index; else ans.val=b.val,ans.index=b.index; return ans; } void build(int id, int l, int r) { if(l==r) { t[id].val=inf,t[id].index=l,t[id].lazy=0; return; } int mid=(l+r)/2; build(id<<1,l,mid),build(id<<1|1,mid+1,r); t[id]=merge(t[id<<1],t[id<<1|1]); } void push(int id, int l, int r) { if(t[id].lazy==0) return; if(l==r) { t[id].val+=t[id].lazy,t[id].lazy=0; if(t[id].val>inf) t[id].val=inf; return; } t[id<<1].lazy+=t[id].lazy,t[id<<1|1].lazy+=t[id].lazy; t[id].val+=t[id].lazy,t[id].lazy=0; } void update(int id, int l, int r, int lq, int rq, ll p) { push(id,l,r); if(l>rq || r=lq && r<=rq) { t[id].lazy+=p; push(id,l,r); return; } int mid=(l+r)/2; update(id<<1,l,mid,lq,rq,p),update(id<<1|1,mid+1,r,lq,rq,p); t[id]=merge(t[id<<1],t[id<<1|1]); } node query(int id, int l, int r, int lq, int rq) { push(id,l,r); node def_val; if(l>rq || r=lq && r<=rq) return t[id]; int mid=(l+r)/2; return merge(query(id<<1,l,mid,lq,rq),query(id<<1|1,mid+1,r,lq,rq)); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("xortransform.in","r",stdin); // freopen("xortransform.out","w",stdout); // #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); // #endif int z=1; cin>>z; f(i,1,z+1) { //cout<<"Case #"<>n>>k; vector > a(n+1); a[0][0]=-inf,a[0][1]=-inf; f(i,1,n+1) { f(j,0,2) cin>>a[i][j]; } sort(all(a)); if(n==2) { cout< suf(n+1,-inf),pre(n+1,-inf); f(i,st+1,n+1) { ll dis=(a[i][1]+2*abs(cx-a[i][0])); tot+=dis,update(1,1,n,i,i,-inf+dis); } suf[st]=tot; rf(i,st-1,0) { ll dif=abs(a[i+1][0]-a[i][0]); update(1,1,n,i+1,n,2*dif); tot+=(2*dif*cnt); node cur=query(1,1,n,1,n); ll mn=cur.val,id=cur.index,dis=2*dif+a[i+1][1]; if(dis>mn) update(1,1,n,i,i,-inf+dis),tot+=(dis-mn),update(1,1,n,id,id,-mn+inf); suf[i]=tot; } t.clear(); t.rz(4*n+20); build(1,1,n); tot=0,st=cnt+1,cx=a[st][0]; f(i,1,st) { ll dis=(a[i][1]+2*abs(cx-a[i][0])); tot+=dis,update(1,1,n,i,i,-inf+dis); } pre[st]=tot; f(i,st+1,n+1) { ll dif=abs(a[i-1][0]-a[i][0]); update(1,1,n,1,i-1,2*dif); tot+=(2*dif*cnt); node cur=query(1,1,n,1,n); ll mn=cur.val,id=cur.index,dis=2*dif+a[i-1][1]; if(dis>mn) update(1,1,n,i,i,-inf+dis),tot+=(dis-mn),update(1,1,n,id,id,-mn+inf); pre[i]=tot; } st=cnt+1; ll en=n-cnt,ans=0,ind=en; tot=suf[en]+a[en][1]; rf(i,en-1,st) { ll dif=abs(a[i][0]-a[i+1][0]),cur=(suf[i+1]+a[i+1][1]+2*dif*cnt); tot+=(2*dif*cnt); if(a[i+1][0]-a[i][0]+cur>tot+a[ind][0]-a[i][0]) tot=cur,ind=i+1; ans=max(ans,a[ind][0]-a[i][0]+tot+pre[i]+a[i][1]); } cout<
•  » » 4 months ago, # ^ | ← Rev. 2 →   +10 The editorial for beautiful permutation didn't appear yet, but I suppose it wouldn't contain generating functions (at least I know much easier way to prove the formula $2^k \cdot s(n, k)$), so can you please share your solution? :)
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +10 Start with one element $x$ and add others in order $n, n-1, \dots , x+1$. For every element there will be 2 positions next to $x$ that will increase the number of elements in $S$ by 1 and other positions will not increase $|S|$. Elements $x-1, \dots , 1$ also don’t increase $|S|$. So the answers will be the coefficients of $(2\cdot y)\cdot (2\cdot y+1)\cdot\dots \cdot (2\cdot y + n-x)\cdot(n-x+2)\cdot \dots \cdot(n)$as a polynomial of $y$.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Yes! The solution is technical, but it requires fundamentally no ideas. I like when standard methods are powerful enough to replace brilliancy.We can assume that $x=1$ (handling general values of $x$ is easy). Let $q(n, k)$ be the number of permutations of $1,2,\dots, n$ with exactly $k$ prefix maximums. The answer to the problem is $ANS = \sum\limits_{k_1+k_2=k-1} \sum\limits_{n_1+n_2=n-1} q(n_1, k_1) q(n_2, k_2) \binom{n-1}{n_1,n_2} ,$indeed we count the permutations grouping them by "$n_1$ elements before $1$ and $n_2$ elements after" and "$k_1$ maximums of good subarrays are before $1$ and $k_2$ maximums of good subarrays are after $1$". Fundamentally we are splitting the problem between the elements before and after $1$.So, how can we compute such sum? Let us define the (exponential) generating functions (for $k\ge 0$) $Q(s, t) := \sum\limits_{n, k\ge 0} \frac{q(n, k)}{n!} s^nt^k .$This generating function is important for us because (straightforward from the definition) $ANS = (n-1)![s^{n-1}t^{k-1}]Q^2 .$Thus, we have to find a good expression for $Q$ (and then for $Q^2$). We have the following recurrence relation for $q(n, k)$ ($m+1$ represents the position of $n$ in the permutation) $q(n, k) = \sum_{m=0}^{n-1} q(m, k-1)(n-1)(n-2)\cdots (m+1),$which is equivalent to the following ODE for $Q$ $tQ = (1-s)\partial_sQ .$Hence, we end up with the Cauchy-system (when $t$ is fixed): $\begin{cases} Q(0, t) = 1 ,\\ \partial_sQ = \frac{t}{1-s}Q . \end{cases}$Solving this (using that $\partial_s\log(Q) = \partial_s Q / Q$) one obtains the magical formula $Q(s, t) = (1-s)^{-t} .$Notice that this is the exponential generating function for (unsigned) Stirling numbers of the first kind (one can prove it by differentiating with respect to $s$, which is what I did during the contest). Hence, we conclude $ANS = (n-1)![s^{n-1}t^{k-1}]Q^2 = (n-1)![s^{n-1}t^{k-1}](1-s)^{-2t} =$ $= 2^{k-1} (n-1)![s^{n-1}t^{k-1}](1-s)^{-t} = 2^{k-1}{n-1\brack k-1}.$
 » 4 months ago, # |   +40 SEGDIV: do a[i] = rng(), while array is bad, then increase i.
 » 4 months ago, # | ← Rev. 2 →   +85 Simple construction for SEGDIV:$a_i = 2\cdot i + i \% 2$It works because $\sum_{i=l}^r a_i = (r-l+1)\cdot(r+l) + \sum_{i=l}^r i \% 2$ and the second part is strictly more than 0 and less than $r-l+1$.
 » 4 months ago, # |   +48 fun facts from tester: AtCoder Beginner Contest 236 ends before my testing work ends. Beautiful Permutation was mod $10^9+7$ originally. I tried to put Boring Trip as second easiest problem of div1, admin stopped me and he was right. Anyway, thanks for your participation. We hope you like the contest!
 » 4 months ago, # |   +10 An easy solution for SEGDIV. SolutionStart with $1$ and then alternatively increase the value by $1$ and $3$.
•  » » 4 months ago, # ^ |   0 Proof?
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +6 Refer to this : https://codeforces.com/blog/entry/99287?#comment-880655, it's similar, just the starting number is different.
 » 4 months ago, # |   0 Can anyone give a test case where merging the two arrays ( similar to how they are merged in merge sort) the length of the LIS would not be the sum of the lis of the smaller arrays in the problem Merged LIS.
•  » » 4 months ago, # ^ |   +3 A=[1,5,6] B=[10,3,4]
•  » » 4 months ago, # ^ |   +3 I tried with the same approach initially and then realized that we can merge the two lis in the same way and that will be the maximum length possible. Testcase: 1 4 3 3 2 2 2 6 1 2
 » 4 months ago, # | ← Rev. 4 →   +5 One more easy solution for SEGDIV:Just use this series. My Solution Updated ProofUpdated proof (previous proof was wrong):Let us consider two $A.P.$ one with $a = 1$ and second with $a = 2$. Both have $d = 4$. Our answer consists of alternating terms of this two $A.P.$ Now, without losing generality let's assume that our subarray of length $N$ is of form : $1, 2, 5, 6, ...$Now let's consider two cases.$Case 1$ ($N$ is even): Sum of such subarray is $S$ $= (N* (2N - 1))/2$ Here $S$ must be an integer. Because $2N-1$ is odd, $N$ must be divided by $2$. Rewriting sum would give us: $S$ $= N/2 * (2*N - 1)$. Now, if the subarray is not good then $N$ must divide $S$. $N$ cannot divide first term because $N/2 < N$. $N$ also can't divide second term because that term is odd. Hence $case 1$ is proved. $Case 2$ ($N$ is odd): Sum of such subarray is $S$ $= (N*(2N-1))/2 + (5 - 2a)/2$ Here, $a$ is either $1$ or $2$. So, $S$ can be either $(2N^2-N+3)/2$ or $(2N^2-N+1)/2$ Now, to $S$ to be divisibly by $N$ is mut be of form $2kN$. Because, numerator must be even. We can not get that form from either of above expressions. Hence, $case2$ is proved.
 » 4 months ago, # |   +6 Did not receive Amazon vouchers for December Cook-Off 2021 Division 1 ;/
•  » » 4 months ago, # ^ | ← Rev. 2 →   +6 Did not even receive Oct ones yet :(
•  » » » 4 months ago, # ^ |   +3
•  » » 4 months ago, # ^ |   0 Didn't get for October Lunchtime yet.Dunno wth is happening with their financial team :(.
 » 4 months ago, # |   +10 Is there any website or some extension through which our deltas in Codechef round can be predicted?
 » 4 months ago, # |   0 Any tips to improve in this type of contest I was only able to solve MERGEDLIS in div1. And don't have any idea about all the other problems. Thanks in advance