CodeChef July Long Challenge 2019

#	User	Rating
1	tourist	3985
2	jiangly	3741
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3489
7	Radewoosh	3483
8	Kevin114514	3443
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	158
5	-is-this-fft-	158
7	awoo	156
8	djm03178	155
9	TheScrasse	154
10	Dominater069	153

Greetings Codeforces Community! We bring you the July Long Challenge 2019. Brace yourself for 10 intense days of non-stop coding challenge starting on 5th July.

All programmers across the globe are welcome to participate. Problems are available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

If you have some original and interesting problem ideas, and want them to be used in CodeChef's contests, you can share them with our admins here: www.codechef.com/problemsetting/new-ideas

Joining me on the problem setting panel are:

Setters: aviroop123 (Aviroop Pal), Erfan.aa (Erfan Alimohammadi), BohdanPastuschak (Bohdan Pastuschak), deadshot_sb (Sombit Bose), KMAASZRAA (Kasra Mazaheri), nqiiii (Jiang XunCi), iamabjain (Abhinav Jain), pranjalr34 (Pranjal Rai), Morphy (Alei Reyes), mayank1601 (Mayank Agrawal), mishra_tanay (Tanay Mishra)
Admin: Morphy (Alei Reyes)
Testers: Kalam (Alipasha Montaseri), KMAASZRAA (Kasra Mazaheri)
Editorialist: MazzForces (Anand Jaisingh)
Statement Verifier: Xellos (Jakub Safin)
Russian Translator: Mediocrity (Fedor Korobeinikov)
Vietnamese Translator: Team VNOI
Bengali Translator: solaimanope (Mohammad Solaiman)
Hindi Translator: Akash Shrivastava
Mandarin Translator: gediiiiiii (Gedi Zheng)

Hope you enjoy the problems!

Comments (15)

Show archived | Write comment?

Erfan.aa

5 years ago, # |

As you can see, two problem setters and two testers are from Iran!

→ Reply

starboy_jb

nice to see all the problems have been added in the starting of the contest.

dush1729

← Rev. 2 →

+17

Predictions for this contest — Div 1 and Div 2.

You can use ccrate for future predictions. Blog for the same.

Does anyone know where we can host Node JS projects for free? Currently, I'm using OpenShift. It's free but they change the project URL every two months.

solved A, C, D in but could not solve B :(

-is-this-fft-

5 years ago, # ^ |

+45

I solved A, Q and R, then had a hard time with Õ but finally managed to do it! Never could solve & though. :/

tdas

+13

Feels like the hardest question in div2 is GUESSPRM, how to prove the solution?

BohdanPastuschak

Which solution? There are many of them.

Any solution with a proof that it works is fine :)

There is proved solution in editorial: https://discuss.codechef.com/t/guessprm-editorial/30111

prodipdatta7

Can anyone help me to find out why the first one got the verdict Accepted but the second one got TLE?

Accepted

ll a[MAX];
ll dp[MAX][MAX];
const ll INF = 1e15;

int main(){
    int t;
    scanf("%d",&t);

    for(int cs=1;cs<=t;cs++){
        int n,z;
        scanf("%d %d",&n,&z);

        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        reverse(a+1,a+n+1);

        dp[0][0] = 0;
        for(int pos=1; pos<=n; pos++) dp[0][pos] = INF;

        for(int used=1; used<=z; used++){
            dp[used][0] = INF;
            for(int pos=1; pos<=n; pos++){
                ll Curr = INF;
                for(int last=0; last<pos; last++){
                    Curr = min(Curr, dp[used-1][last] - last*a[pos]);
                }
                Curr += pos*a[pos];
                dp[used][pos] = Curr;
            }
        }

        ll Ans = INF;
        for(int pos=1; pos<=n; pos++) Ans = min(Ans, dp[z][pos]);
        printf("%lld\n",Ans);
    }
}

TLE in task 5

const int N          = (int)1e3 + 5 ;
#define     Int         Int()
int dp[N][N], a[N] ;

int main(){
    int test = Int , tc = 0 ;
    while(test--){
        int n = Int, z = Int ;
        for(int i = 1 ; i <= n ; ++i){
            a[i] = Int ;
            dp[0][i] = 0 ;
        }
        sort(a + 1, a + n + 1) ;
        for(int i = 1 ; i <= n ; ++i){
            dp[1][i] = a[i] * (n - i + 1) ;
        }
        for(int i = 2 ; i <= z ; ++i){
            for(int j = i - 1 ; j <= n ; ++j){
                int x = inf ;
                for(int k = i - 1 ; k < j ; ++k){
                    x = min(x, dp[i - 1][k] + ((a[j] - a[k]) * (n - j + 1))) ;
                }
                dp[i][j] = x ;
            }
        }
        int res = inf ;
        for(int i = z ; i <= n ; ++i){
            res = min(res, dp[z][i]) ;
        }
        printf("%d\n",res);
    }
    return 0 ;
}

problem link : Hit The Coconuts