copy paste
Hey guys!!
Finally, after 10 tiring days, the A̶u̶g̶u̶s̶t̶ July long concludes. Let’s share our approaches for the problems here while editorials for problems come out (at this moment none n̶o̶t̶ ̶a̶l̶l̶ of them are out)? Got any interesting approach which you can’t wait to share? The wait is over 
So, which was your favourite problem? I had the best time solving ̶I̶n̶t̶e̶r̶a̶c̶t̶i̶v̶e̶ ̶M̶a̶t̶r̶i̶x̶ ̶:̶)̶.̶ SNKAPT and MXMN (50pts) ̶T̶h̶e̶ ̶p̶r̶i̶n̶c̶e̶s̶s̶ ̶g̶a̶v̶e̶ ̶m̶e̶ ̶a̶ ̶r̶u̶n̶ ̶f̶o̶r̶ ̶m̶y̶ ̶s̶c̶o̶r̶e̶ ̶x̶D̶ ̶-̶ ̶s̶o̶ ̶I̶ ̶l̶e̶t̶ ̶h̶e̶r̶ ̶s̶t̶a̶y̶ ̶w̶i̶t̶h̶ ̶d̶r̶a̶g̶o̶n̶s̶ ̶a̶n̶d̶ ̶b̶e̶ ̶b̶y̶ ̶h̶e̶r̶s̶e̶l̶f̶ ̶t̶h̶e̶n̶ 
But on a serious note, anyone who was able to MXMN s̶a̶v̶e̶ ̶t̶h̶e̶ ̶p̶r̶i̶n̶c̶e̶s̶s̶ ̶(̶o̶r̶ ̶p̶r̶i̶n̶c̶e̶.̶.̶.̶? :p). I don’t know any approach to solve it.
P.P.S. - Maybe later I will add some small story about How much SNKAPT and MXMN (50pts) bugged me a lot despite having such an easy soln. But I’m lazy
Let the discussion begin!
/copy paste
Off Topic. A note to @admin/Moderators
What’s wrong with discuss these days. The only post I find is some private chats, plagiarism reports (without any proof.), discuss long’s problems during contest.
Should I remind moderators/admin "How to ban people?: Seems (s)he doesn’t know how to do it on discourse. And (s)he didnt bothered to read “How to manage Discourse.”
@admin @vijju123
6 Likes
My favorite problem was Hit The Coconuts ( ͡° ͜ʖ ͡°). Very cool way to solve it using CHT that I had not seen before (although it is well known).
Mysecond favorite problem was L.O.V.E.M.U.F.F.I.N ( ͡° ͜ʖ ͡°). It was nice to see such a nice sequence of numbers pop up from such a simple description (which could have been much shorter too).
1 Like
MXMN was my favourite.
I’m trying to start a new thing, I hope some people pick it up. I write my idea in a comment at the start of my last submission for the problem. I have done it for just this long challenge.
Mine is a complex approach with very little pre-requisites. Probably there are better solutions using stuff I don’t know. Time Complexity : O(n*(log(n)^3)).
I hope you find it useful.
Here you go :
CodeChef: Practical coding for everyone.
3 Likes
I did Hit the Coconuts with a simple observation, that if coconuts are sorted increasingly then optimal coconuts are either in one continuous group or in two continuous groups. So I just wrote a brute force for checking one continuous group and two separated continuous groups in sorted Coconuts and taking the best answer.
Hit the Coconuts (CCC) gave complete AC with a O(N^2*Z) algorithm. Didn’t expected
that.
Can someone tell me the approach for Circular Merging?
It’s a 2-D DP.
Logic in code below
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define f(i,a,b) for(int i(a);i<b;i++)
#define rep(i,n) for(int i(0);i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0);
//the sum function calculates the sum of n consecutive terms of an array starting
from indice i
int sum(int array[] , int prefix[] , int m , int i , int n){
int ans=0;
m = m + i - 1;
m%=n;
if(i<m)ans = prefix[m+1] - prefix[i];
else ans = prefix[n] - prefix[i] + prefix[m+1];
return ans;
}
int solve(int array[] , int n){
int dp[n][n];
//compute prefix sums
int prefix[n+1];
prefix[0] = 0;
f(i,1,n+1)prefix[i] = prefix[i-1] + array[i-1];
//starting dp
int i,j,t,ans,temp,k;
//set all i , i to 0
rep(i,n)dp[i][i] = 0;
//started computing according to
//dp[i][j] = min( dp[i][k] + dp[k+1][j] ) + sum(i,j) forall k in i to (i + n - 1)%n
//my diff variable increases the difference b/w i and j from 1 to n - 1
for(int diff(1);diff<n;diff++){
//there are n case for a difference, from i = 0 to i = n-1
rep(v,n){
//sets i and j
i = v; j = i + diff; j %=n;
//now i assume the k variable which was earlier stated on line 37
k = i;
t = diff;
ans = 1e16;
//there are "difference" number of subcases for each i , j namely k = i to k = (i+n-1)%n as in line 37
while(t--){
// main dp
ans = min(ans , dp[i][k] + dp[(k+1)%n][j]);
k++;
k%=n;
}
//set my array
dp[i][j] = ans + sum(array ,prefix , diff + 1 , i , n);
}
}
/* just debugging. couting my whole dp array
rep(y,n){
rep(x,n)cout<<dp[x][y]<<"\t";
cout<<"\n";
}
*/
//now , there are several cases for the final answer depending on the two numbers we didn't merge throughout
int ret=1e16;
rep(i,n){
ret = min(ret , dp[i][(i+n-1)%n]);
}
return ret;
}
int32_t main(){
fast;
//open;
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int array[n];
rep(i,n)cin>>array[i];
cout<<solve(array , n)<<"\n";
}
return 0;
}
2 Likes
I guessed initially there could be n! combinations. Need to improve my DP.
Thanks for that illustration.
I don’t think I have any interesting things to share on the problems I’ve worked out, but I’d probably like to know more about Chef War II’s better solution.
Yeah I was also planning to do that but first I tried with n^2*z and it worked and saved me the trouble 
I think the test cases weren’t that good.
https://www.codechef.com/viewsolution/25266620
1 Like
Can someone tell me the basic properties involved in CHFWAR and CCC?
Chfwar is just an ad-hoc problem. Required you work with test cases.
1 Like
WTH, I didn’t imagine this to work
Yeah wondering why it has low submissions, it was the easiest problem in div1…
1 Like
Can u plz share ur code link.
I’d love some more insights in CHFWAR2. The only thing that worked for me was taking all special cities, permuting them randomly and printing the resulting tour sorted by the linear cost over duration.
I wanted to do so much more here, but somehow most things I tried resulted in WA even though I thought it should be correct. Like taking above solution and adding one random edge was WA somehow.
I guess I messed something up in my code, but for the last two days I really had no idea what should could be wrong anymore.
I also started with a n! approach, improved that to zn^2 (didn’t work for me) and then some more to zn*f(z) for some apparently small enough function f in z.