CodeChef July Long Challenge 2019

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	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