Editorials of Procon 2018 ?

editorial
,
1

Please share the editorials of Procon 2018 which was held on 16 Aug 2018.

2 Likes
2

Awkward Pairs was fun…

Contest
Practice

Author: meetsid20

The main challenge as I saw it was getting the counts of different digit sums over a large range, potentially 10^{18} numbers. It probably wasn’t feasible to get those individually in general. Clearly a consecutive decade of numbers [\text{xyz}0..\text{xyz}9] share the digit sum of the numbers above the units, so a recursive approach is possible, accounting for the detail of the ends of each level:

  • Find the digit sums in the first and last part-decades directly
  • if there is a middle part, recursively find the digit sums in the non-unit part and then add these totals to each of the 0,1,2,3...,9 bigger digit sum counts.

Then the number of awkward couples represented by each coprime pair of digit sums is the product of the two counts. Since we are only going to have 162 different digit sums at most, this can be done quite straightforwardly.

There is also the chance that there are several digit counts of 1, which will be coprime to each other in the sense of \gcd=1. These pair up in n(n-1)/2 ways.

my solution

1 Like
3

The answer to Algebra Score
First learn Matrix chain multipication It is a dp of O(n^3)
We have to do the same here

  1. We will maintain two 2-D dps. At [l][r] One will have the maximum sum we can get in the range.Other will have the minimum sum we can have in that range.

  2. We will find the solution for range [0…n-1]

  3. We will just iterate over the all possible combinations, i.e.

    for(lo i=0;i<n;i++)dp[i][i]=dp2[i][i]=a[i];
    for(lo L=2;L<=n;L++){//length of segment
    for(lo i=0;i<n-L+1;i++){
    lo j=i+L-1;
    for(lo k=i;k<=j-1;k++){
    //debug5(i,j,k,L,b[k]);
    if(b[k]==’+’){
    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
    dp2[i][j]=min(dp2[i][j],dp2[i][k]+dp2[k+1][j]);
    }
    else{
    dp[i][j]=max(dp[i][j],dp[i][k]-dp[k+1][j]);
    dp[i][j]=max(dp[i][j],dp[i][k]-dp2[k+1][j]);
    dp2[i][j]=min(dp2[i][j],dp2[i][k]-dp2[k+1][j]);
    }
    }
    }
    }

  4. dp[l][r] is storing the maximum for the range [l…r]

  5. dp2[l][r] is storing the minimum for the range [l…r]

1 Like
4

yes, where are editorials? 3 days gone after contest still no editorial… please @admin look at this matter