### sidhant's blog

By sidhant, history, 4 years ago,

After the recently concluded January Long Challenge, I would like to invite you for some more interesting challenges to keep your coding schedule always packed!

Participate in the January Cook-Off 2018 and enjoy Chef’s tricky tests. Joining me on the panel are:

• Problem Setter and Editorialist: sidhant (Sidhant Bansal), arjunarul (Arjun Arul)

• Russian Translator: CherryTree (Sergey Kulik)

• Mandarin Translator: huzecong (Hu Zecong)

• Vietnamese Translator: VNOI Team

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.

### Contest Details:

Time: 21st January 2018 (2130 hrs — 0000 hrs Indian Standard Time — +5:30 GMT) — Check your timezone.

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.

Prizes:

• Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

According to me, the problems are very interesting and I am sure that you will have fun while solving these problems :)

Good Luck! Hope to see you participating!!

• +48

 » 4 years ago, # |   +64 PS — In this cook off, we have changed the penalty from 20 minutes to 10 minutes. Enjoy!!
 » 4 years ago, # |   +8 Gentle Reminder: Contest starts under 5 minutes !!
 » 4 years ago, # |   +5 I just loved your problems! Hope you set more contests in the future! :D
 » 4 years ago, # |   +5 How to solve far graphs when there are odd cycles. Also will the vertices always get -L/2,0,L/2 even in odd cycled graphs ??
•  » » 4 years ago, # ^ | ← Rev. 4 →   +8 There is at most one cycle of length 3. After removing them and all edges which have an end point in that cycle, the resulting graph is bipartite. (Assume answer is "Yes")
•  » » 4 years ago, # ^ |   +8 For now don't consider the equality in the condition |ai — aj| >= L/2. That is for now, there is edge if and only of |ai-aj| > L/2 Partition the nodes with values in [0, L/2] and [L/2+1, L]. Since the maximum difference achievable in each partition is at-most L/2. There can not be any edge. This is means the graph is bipartite, with the above partition. With a special property that I will describe below. Also, if we have any bipartite graph with that property, we can always assign values in such a way that the above holds. Now let's consider the equality - Partition the graph as before. But we can have a edge between the first node and last node in the first partition — if sorted according to values. If there is then. Also in that case value of first node will be 0 and the last will be L/2. Also, we can have at most one outgoing edge from the last node in first partition. This means last node of first partition must be a part of some simple odd-length cycle of the original graph and has degree 2. So to solve this problem, we need to detect that special node. And then verify the special property that I mentioned above. And assign values greedily. special property is nothing but if there is edge from a node to u and to v then there is edge from that node to every node u <= x <= v. If we consider the nodes according to sorted values. Disclaimer : I have coded this up but could not get accepted. Submission
 » 4 years ago, # |   +7 How to solve MAGA?
•  » » 4 years ago, # ^ |   +7 Simple dp, with extreme amount of case handling. Consider cases where the size of the array is even/ odd, the current index in dp you are at is even/odd and wether you performed swap in the previous step or not.States will be dp[last][idx], last indicating wether swap was performed for last index, and idx needs to move only until mid of the array.
•  » » » 4 years ago, # ^ |   +5 Yeah same here. My code exceeded 200 lines. I was wondering how people solved so fast.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +14 You just need to write a neat code :) Here's mine: #include using namespace std; int A[100009]; int D1[100009]; int D2[100009]; bool ok(int i) { if (i % 2 == 1) return A[i] < A[i + 1]; else return A[i] > A[i + 1]; } int N; int ans() { int i = (N + 1) / 2; int j = (N + 2) / 2; int id = 0; D1[id] = N + 2; D2[id] = N + 2; if (i == j) { D1[id] = 0; D2[id] = 0; } else { if (ok(i)) D1[id] = 0; swap(A[i], A[j]); if (ok(i)) D2[id] = 1; swap(A[i], A[j]); } while (true) { i--; j++; if (i < 1) break; id++; D1[id] = N + 2; D2[id] = N + 2; { if (ok(i) && ok(j - 1)) D1[id] = min(D1[id], D1[id - 1]); swap(A[i + 1], A[j - 1]); if (ok(i) && ok(j - 1)) D1[id] = min(D1[id], D2[id - 1]); swap(A[i + 1], A[j - 1]); } swap(A[i], A[j]); { if (ok(i) && ok(j - 1)) D2[id] = min(D2[id], 1 + D1[id - 1]); swap(A[i + 1], A[j - 1]); if (ok(i) && ok(j - 1)) D2[id] = min(D2[id], 1 + D2[id - 1]); swap(A[i + 1], A[j - 1]); } swap(A[i], A[j]); } return min(D1[id], D2[id]); } int main() { int T; cin >> T; while (T--) { cin >> N; for (int i = 1; i <= N; i++) cin >> A[i]; int out = N + 2; out = min(out, ans()); for (int i = 1; i <= N; i++) A[i] *= -1; out = min(out, ans()); if (out > N) out = -1; cout << out << '\n'; } } 
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 I did something similar. got WA . I don't know why. Here's my code
 » 4 years ago, # | ← Rev. 2 →   +3 For Problem B, "Multiple of 3", can it be solved using CRT?It is possible to solve because gcd(10,3)=1.I calculated 2 values, one for mod 10(a1) and other for mod 3(a2), eqn was n=(d0+d1)+(d0+d1)*(2^(k-2)-1).Combined them using this eqn from wikipedia, n3=a1m2n2+a2m1n1 where n1=10, n2=3 and m1=1,m2=-3 which is derived from extended euclid gcd.Now I just checked n3%3 and printed, but this gave a WA. Can someone please help me(show me de way)?
•  » » 4 years ago, # ^ |   0 You can calculate n3 mod 30 then check (n3 mod 30) mod 3 == 0
•  » » » 4 years ago, # ^ |   0 I tried it but getting WA. Link
•  » » » » 4 years ago, # ^ |   0 Sorry, this idea is wrong. the correct one is notice that digit[i] = digit[i-4] for all i except first few ones.
•  » » » » » 4 years ago, # ^ |   0 Can you please tell me why this idea won't work?
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +5 because ( digit[0] % 10 + digit[1] % 10 + digit[2] % 10 ... ) % 3 is not equal to ( (digit[0] + digit[1] + digit[2] ...) % 10 ) % 3
•  » » » » » » » 4 years ago, # ^ |   0 Okay! Got it, thanks!
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 We can go further than this. I noticed that the repeating digits are always on the lines "2,4,8 6". The only corner case is when d0+d1=5, for which only 0 is appended always.
•  » » » » » » 4 years ago, # ^ |   0 that is not a corner case, actually the kth digit for k>=3 is (2^(k-3)*(d0+d1))%10.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 first calculate (d0+d1)%10 and then divide into group of 4s . the pattern will repeat like ; 2,4,8,6 and lastly add those. for ex. d3 = 2*(d0+d1)%10 , d4 = 4*(d0+d1)%10 , d5 = 8*(d0+d1)%10, d6 = 6*(d0+d1)%10 , like this the pattern will repeat for K/4 groups , you have to add the remaining . here is the code: #include using namespace std; #define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pb push_back #define MP make_pair #define F first #define S second #define min(a,b) (((a)<(b))?(a):(b)) #define max(a,b) (((a)>(b))?(a):(b)) #define PII pair typedef long long ll; ll x; ll MOD = 1e9+7; #define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef long long ll; ll modexp(ll a, ll b, ll mod){ ll res = 1; while(b){ if(b&1) res = (res*a)%mod; b = b>>1; a = (a*a)%mod; } return res; } int main(){ boost; ll T,N,i,j,k,L,l,m,n,R; ll K; cin >> T; ll S; ll d0,d1; while(T--){ cin >> K >> d0 >> d1; ll sum = (d0+d1)%3; ll s2 = 0; if(K == 2){ if(sum%3 == 0) cout << "YES" << endl; else cout << "NO" << endl; continue; } K -= 2; K -= 1; s2 += (d0+d1)%10; //for(i = 0 ; i < K/4 ; i++){ s2 += K/4 * ((2*(d0+d1))%10+(4*(d0+d1))%10+(8*(d0+d1))%10+(6*(d0+d1))%10); //} K %= 4; if(K){ s2 += (2*(d0+d1))%10; K--; } if(K){ s2 += (4*(d0+d1))%10; K--; } if(K){ s2 += (8*(d0+d1))%10; K--; } if(K){ s2 += (6*(d0+d1))%10; K--; } //s2 %= 10; s2 %= 3; if((sum+s2)%3 == 0) cout << "YES" << endl; else cout << "NO" << endl; } } 
•  » » » 4 years ago, # ^ |   0 Thanks sir, I implemented this during contest but pretty late because my first approach gave a WA.
 » 4 years ago, # | ← Rev. 2 →   -7 U give wrong explanation for the SURVIVE PROBLEM. A beginner like me just confused that in the question it is saying diff thing but in ur explanation for the 1 sample task u did diff thing i was not able to get it and after recking my brain till contest problem not gets solved and problem explanation updated very last.. plzz careful for the future anyways problems were GREAT :)
 » 4 years ago, # |   0 Hints for MAGA?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 It's a straightforward DP problem :D DP1[i]=min swaps if not swapping [i, n-i+1] in interval [i, n-i+1] DP2[i]=min swaps if swapping [i, n-i+1] in interval [i, n-i+1] You can be a little clever and just count the numbers if a1>a2
•  » » » 4 years ago, # ^ |   +1 Can you elaborate a bit more on the dp states?
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 [user:__tutls__] can you please explain why do we multiply by -1 rest is clear .
•  » » » 4 years ago, # ^ |   0 okk got it just to check for the other case ??
•  » » » » 4 years ago, # ^ |   0 Yeah :D It doesn't make sense to code the same thing again :D
 » 4 years ago, # |   +5 How to solve FINDA?
 » 4 years ago, # |   0 when rating may get updated?
•  » » 4 years ago, # ^ |   0 Updated
 » 4 years ago, # |   +6 Editorial for MAGA has still not been released.